Project

General

Profile

Actions

Feature #18809

closed

Add Numeric#ceildiv

Added by kyanagi (Kouhei Yanagita) about 1 year ago. Updated 10 months ago.

Status:
Closed
Priority:
Normal
Assignee:
-
Target version:
-
[ruby-core:108724]

Description

pull request: https://github.com/ruby/ruby/pull/5965

I have needed to implement "rounding up division" several times.

("rounding up division" means getting a quotient of division which is rounded up to the nearest integer.)

Typically, this is implemented as follows:

# notice that b > 0 is assumed
def rounding_up_division(a, b)
  (a + b - 1) / b
end

But for me, this is difficult to write without careful consideration.
Every time I implement this, I need to think for a few minutes on paper.

So I propose to add a new method Numeric#ceildiv.

Typical examples where this is necessary are counting groups and pagination.

e.g. There are 123 items. If you display 10 items on each page, how many pages are there?

123.ceildiv(10) # => 13

We can find several examples of this division also in the Ruby's source code. (Try grep -r -E -e '([^ ]+) *- *1\) */ *\1' .)

./internal.h:#define roomof(x, y) (((x) + (y) - 1) / (y))
./array.c:    len = (len + ustep - 1) / ustep;
./include/ruby/internal/memory.h:    const size_t cnt = (total_size + sizeof(VALUE) - 1) / sizeof(VALUE);
./ext/bigdecimal/missing/dtoa.c:#define PRIVATE_mem ((PRIVATE_MEM+sizeof(double)-1)/sizeof(double))
./ext/bigdecimal/bigdecimal.c:  nc += (nc + mc - 1) / mc + 1;
./ext/bigdecimal/bigdecimal.c:    mx = (mx + BASE_FIG - 1) / BASE_FIG;    /* Determine allocation unit. */
./ext/bigdecimal/bigdecimal.c:                mf = (mf + BASE_FIG - 1) / BASE_FIG + 2; /* Needs 1 more for div */
./ext/bigdecimal/bigdecimal.c:    nalloc = (ni + nf + BASE_FIG - 1) / BASE_FIG + 1;    /* set effective allocation  */
./ext/bigdecimal/bigdecimal.c:    size_t const round_limit = (VpGetPrecLimit() + BASE_FIG - 1) / BASE_FIG;
./ext/bigdecimal/bigdecimal.c:    if ((ix + BASE_FIG - 1) / BASE_FIG > ixDigit + 1) return 0;
./ext/bigdecimal/bits.h:#define roomof(x, y) (((x) + (y) - 1) / (y))
./internal/numeric.h:    VALUE values[(SIZEOF_DOUBLE + SIZEOF_VALUE - 1) / SIZEOF_VALUE];
./regcomp.c:  OnigDistance str_len = (byte_len + mb_len - 1) / mb_len;
./bignum.c:    size_t num_bdigits = (num_bits + BITSPERDIG - 1) / BITSPERDIG;
./missing/dtoa.c:#define PRIVATE_mem ((PRIVATE_MEM+sizeof(double)-1)/sizeof(double))
./numeric.c:    char buf[float_dig + (decimal_mant + CHAR_BIT - 1) / CHAR_BIT + 10];
./gc.c:#define CEILDIV(i, mod) (((i) + (mod) - 1)/(mod))

Naming:

I was not sure whether to name it ceildiv or divceil because there are both divmod and fdiv.
Since divmod is a method that returns two elements, the quotient and the remainder,
while fdiv is a method that performs Float division, I decided to follow fdiv.

Updated by nobu (Nobuyoshi Nakada) about 1 year ago

I'm positive.
It may be nice to alias div as floordiv too?

Updated by mrkn (Kenta Murata) about 1 year ago

Julia provides cld and fld for the ceiling and flooring division, respectively. They are implemented as aliases of div with rounding mode argument, like cld(a, b) = div(a, b, RoundUp). It may be good to introduce an optional rounding mode argument in div in addition to adding these divisions.

Updated by Dan0042 (Daniel DeLorme) 12 months ago

Why not simply use a.fdiv(b).ceil ?
It expresses the intent of the code clearly, and I doubt there would be a measurable difference in performance except in the tightest of tight loops.

Actions #4

Updated by sawa (Tsuyoshi Sawada) 12 months ago

Dan0042 (Daniel DeLorme) wrote in #note-3:

Why not simply use a.fdiv(b).ceil ?
It expresses the intent of the code clearly, and I doubt there would be a measurable difference in performance except in the tightest of tight loops.

a = 99999999999999999
b = 1
(a + b - 1) / b # => 99999999999999999
a.fdiv(b).ceil # => 100000000000000000

Updated by matz (Yukihiro Matsumoto) 11 months ago

Let's add Integer#ceildiv.

Matz.

Updated by mame (Yusuke Endoh) 11 months ago

Additional information.

  • We do introduce only Integer#ceildiv.
  • We do not introduce Numeric#ceildiv until we see the need. There is already Numeric#div, but a consistency with it is not a sufficient reason to introduce it.
  • We do not introduce Numeric#floordiv.
  • 3.ceildiv(-2) should return -1, which is ceil(-(3/2)). Note that the naive implementation of (a + b - 1) / b, which returns (3 + (-2) - 1) / (-2) = 0. (As far as we glanced at the PR, it is implemented correctly.)

Updated by kyanagi (Kouhei Yanagita) 11 months ago

Thank you for accepting.
I updated the PR. The PR contains only Integer#ceildiv.

Updated by kyanagi (Kouhei Yanagita) 10 months ago

Are there any blocking issues?
If exist, I will work to resolve them.

Actions #9

Updated by nobu (Nobuyoshi Nakada) 10 months ago

  • Status changed from Open to Closed

Applied in changeset git|0617cba197cdff626ee9c74cece480df31d384ef.


[DOC] Add the link to [Feature #18809]

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0