Add Integer#ceildiv

[kyanagi]

ticket: https://bugs.ruby-lang.org/issues/18809

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 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.

[kyanagi]

I removed Numeric#ceildiv. The PR contains only Integer#ceildiv.

[nobu]

Or, class Integer; def ceildiv(other) = -div(-other); end in numeric.rb. This may be faster due to method caches.

[kyanagi]

I tried benchmarking. As shown below, nobu-san's suggestion is faster. Thank you!

require 'benchmark'

n = 10 ** 7

Benchmark.bm do |x|
  x.report("Fixnum/Fixnum") { a, b = 5, 2; n.times { a.ceildiv(b) } }
  x.report("Bignum/Bignum") { a, b = 10**100, 10**99 - 1; n.times { a.ceildiv(b) } }
  x.report("Bignum/Fixnum") { a, b = 10**100, 3; n.times { a.ceildiv(b) } }
end

Original:

       user     system      total        real
Fixnum/Fixnum  3.340009   0.043029   3.383038 (  3.384022)
Bignum/Bignum  8.229500   0.118543   8.348043 (  8.349574)
Bignum/Fixnum  8.328971   0.097842   8.426813 (  8.426952)

Improved:

       user     system      total        real
Fixnum/Fixnum  0.699140   0.000961   0.700101 (  0.700199)
Bignum/Bignum  5.076165   0.083160   5.159325 (  5.159360)
Bignum/Fixnum  5.548684   0.115372   5.664056 (  5.666735)