Project

General

Profile

Actions

Feature #18809

closed

Add Numeric#ceildiv

Added by kyanagi (Kouhei Yanagita) over 2 years ago. Updated about 2 years ago.

Status:
Closed
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) over 2 years ago

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

Updated by mrkn (Kenta Murata) over 2 years 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) over 2 years 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) over 2 years 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) over 2 years ago

Let's add Integer#ceildiv.

Matz.

Updated by mame (Yusuke Endoh) over 2 years 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) over 2 years ago

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

Updated by kyanagi (Kouhei Yanagita) about 2 years ago

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

Actions #9

Updated by nobu (Nobuyoshi Nakada) about 2 years 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