div with rounding modes [+ rounded division] #33040

Keno · 2019-08-23T02:16:01Z

I found myself needing a rounding integer division, i.e. one that does RoundToNearestTiesAway (actually the reference implementation calls for RoundToNearestTiesToward, but the paper doesn't specified and either should be ok). Rather than adding a rntad (round-to-neearest-ties-away-division) function, I figured it may make sense to instead create a generic div(x, y, r::RoundingMode=RoundToZero) function, while keeping fld,cld (and the two-argument div) as useful shorthands for the rounding modes they represent.

~~This PR just does the re-arranging for the existing code. I haven't yet added the new functionality for round-nearest. Let's discuss whether this direction is sensible.~~

Keno · 2019-08-23T02:24:39Z

Somehow I missed that we already have rem(x, y, r::RoundingMode) with compatible semantics, which I thinks validates the sensibility here.

StefanKarpinski · 2019-08-23T02:30:25Z

I feel like @simonbyrne would have the most well-informed opinion on this matter but it seems like a solid idea to me?

simonbyrne · 2019-08-23T02:36:24Z

👍 this was my plan from #9283.

simonbyrne · 2019-08-23T15:17:36Z

base/div.jl

+"""
+    div(x, y, r::RoundingMode=RoundToZero)
+
+    Compute the remainder of `x` after integer division by `y`, with the quotient rounded


unindent this text

simonbyrne · 2019-08-23T15:31:57Z

base/div.jl

+        return q + copysign(1, q)
+    else
+        @assert rnd == RoundNearestTiesUp
+        return sign(q) == -1 ? q : q + 1


I don't think it handles negative odd values of y correctly, e.g. divrem(5, -3, RoundNearestTiesUp).

simonbyrne · 2019-08-23T15:32:28Z

base/div.jl

+                                              typeof(RoundNearestTiesAway),
+                                              typeof(RoundNearestTiesUp)})
+    (q, r) = divrem(x, y)
+    halfy = copysign(y >> 1, r)


would be good to explain the logic of this function: I don't quite understand it myself.

simonbyrne · 2019-08-23T15:33:11Z

test/int.jl

+            (3, 2, 2, 2, 2),
+            (-3, 2, -2, -2, -1),
+            (5, 2, 2, 3, 3),
+            (-5, 2, -2, -3, -2))


Add some odd divisor cases to the test cases. Also typemin/typemax divisors/dividends.

simonbyrne · 2019-08-23T15:39:42Z

base/div.jl

+    c == -1 && return q
+    c == 1 && return q + copysign(1, q)
+    if rnd == RoundNearest
+        return iseven(q) ? q : q + copysign(1, q)


None of these handle y == 1 correctly.

simonbyrne · 2019-08-24T22:39:15Z

base/div.jl

+        # The divisior is odd - no ties are possible, just
+        # round to nearest. N.B. 2r == y is impossible because
+        # y is odd.
+        return abs(2r) > abs(y) ? q + copysign(one(q), q) : q


This won't work if 2r overflows, e.g. x,y = typemax(Int)-2,typemax(Int)

simonbyrne · 2019-08-25T04:48:25Z

@Keno I've added some code that I think should handle overflow correctly. Tests could be improved, and I'm not really sure they will handle mixed Int/UInt arguments correctly. Feel free to adapt as you see fit.

Keno · 2019-08-25T05:07:57Z

Oh, I was just gonna use checked_mul, but I like that your version has divrem. We could switch all the divisions to bitshifts, or maybe we just trust that the compiler will figure it out (and that gmp has sufficient special cases). We should also definitely add your overflow test case.

smldis · 2019-08-25T15:25:09Z

base/div.jl

+div(a, b) = div(a, b, RoundToZero)
+
+"""
+    rem(x, y, r::RoundingMode)


maybe rem(x, y, r::RoundingMode=RoundToZero) as div docstring

simonbyrne · 2019-08-26T03:46:20Z

ooh, using checked_mul is a good idea. It should be possible to rewrite my code to use that instead.

Keno · 2019-08-26T03:47:32Z

(Just as a note, I meant mul_with_overflow, the checked_ one throws).

In preparation for supporting other rounding modes in div, create a three-argument div function that takes a rounding mode as the last argument and make this the fundamental fallback for fld/cld.

Keno · 2019-09-25T22:56:59Z

Rebased and fixed a few more issues. If CI passes, I'd like to start getting this in.

simonbyrne · 2019-09-25T23:08:08Z

If we want to check for overflow, we could exhaustively test Int8.

Keno · 2019-09-27T21:50:59Z

If we want to check for overflow, we could exhaustively test Int8.

Good idead. Done. This should be good to go from my side.

I think it's better to give a MethodError here than an approximate answer for non-AbstractFloat reals (e.g. custom integer types).

See JuliaLang/julia#33040 (a3eb9d4). This commit enables the new three-argument div API for BitIntegers.

It looks like in JuliaLang#33040 the `div` docstring was accidentally incorrectly copied from the `rem` docstring, so it currently describes the `rem` operation, not `div`. This commit changes that docstring to correctly describe integer division with custom rounding.

It looks like in #33040 the `div` docstring was accidentally incorrectly copied from the `rem` docstring, so it currently describes the `rem` operation, not `div`. This commit changes that docstring to correctly describe integer division with custom rounding.

NHDaly · 2020-01-26T17:12:14Z

I noticed that fld1 isn't included in this change, and it looks like it's still calling two-argument div:

julia/base/operators.jl

Line 770 in 09d617a

fld1(x::T, y::T) where {T<:Real} = (m = mod1(x, y); fld(x + y - m, y))

Should packages still implement a custom override for fld1 if needed? (I'm looking at adding this support for FixedDecimals, and i'm wondering if this can be as simple as just adding Base.div(x::T, y::T, r::RoundingMode) where {T <: FD} = T(div(x.i, y.i, r))? Do I need to stop defining two-arg-div, fld, fld1, etc?)

ararslan added the maths Mathematical functions label Aug 23, 2019

Keno changed the title ~~RFC: div with rounding modes~~ div with rounding modes [+ rounded division] Aug 23, 2019

Keno requested a review from simonbyrne August 23, 2019 04:07

simonbyrne reviewed Aug 23, 2019

View reviewed changes

Keno force-pushed the kf/3div branch 3 times, most recently from c5aa5ee to 1a374a7 Compare August 24, 2019 22:10

simonbyrne reviewed Aug 24, 2019

View reviewed changes

Keno force-pushed the kf/3div branch from eb42c70 to a71f150 Compare August 25, 2019 06:54

smldis reviewed Aug 25, 2019

View reviewed changes

Keno added a commit to JuliaCrypto/ToyFHE.jl that referenced this pull request Sep 25, 2019

Try backporting JuliaLang/julia#33040

77d2f3e

Keno and others added 5 commits September 25, 2019 17:04

Re-arrange fld/cld code

8ebb4e4

In preparation for supporting other rounding modes in div, create a three-argument div function that takes a rounding mode as the last argument and make this the fundamental fallback for fld/cld.

Implemented rounded division

c00c706

add various divrem combinations to avoid overflow

cb51af0

Whitespace/test fixes

f6f8795

Small tweaks to docstrings

14c2683

Keno force-pushed the kf/3div branch from 763db7f to 27d51bd Compare September 25, 2019 22:55

Bugfixes

bcb5605

Keno force-pushed the kf/3div branch from 27d51bd to bcb5605 Compare September 26, 2019 02:23

Add the exhaustive test

dba98bb

simonbyrne approved these changes Sep 27, 2019

View reviewed changes

Tigthen up types for div fallback

f85ebed

I think it's better to give a MethodError here than an approximate answer for non-AbstractFloat reals (e.g. custom integer types).

Keno merged commit a3eb9d4 into master Sep 28, 2019

Keno deleted the kf/3div branch September 28, 2019 19:17

simonbyrne mentioned this pull request Sep 30, 2019

Euclidean division: div, rem and friends #9283

Closed

rfourquet pushed a commit to rfourquet/BitIntegers.jl that referenced this pull request Sep 30, 2019

Adjust to new div API (#11)

df84fe0

See JuliaLang/julia#33040 (a3eb9d4). This commit enables the new three-argument div API for BitIntegers.

iamed2 mentioned this pull request Oct 23, 2019

Infinite recursion in div for Real #33651

Closed

This was referenced Oct 28, 2019

Fix div docstring to describe division, after #33040 #33703

Merged

Add support for rounding modes for division for FixedDecimals JuliaMath/FixedPointDecimals.jl#50

Closed

NHDaly mentioned this pull request Jan 26, 2020

Missing RoundFromZero support for three-arg div with RoundingMode #34519

Closed

helgee mentioned this pull request Apr 12, 2021

Three-argument div/divrem methods are missing compatibility note in docstring #40449

Closed

N5N3 mentioned this pull request Sep 19, 2021

Inferior performance of cld vs ceil for floating-point arguments #42294

Closed

Seelengrab mentioned this pull request Apr 21, 2023

Incorrect results from floating-point division (fld, cld, div) #49450

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

div with rounding modes [+ rounded division] #33040

div with rounding modes [+ rounded division] #33040

Keno commented Aug 23, 2019 •

edited

Keno commented Aug 23, 2019

StefanKarpinski commented Aug 23, 2019

simonbyrne commented Aug 23, 2019

simonbyrne Aug 23, 2019

simonbyrne Aug 23, 2019

simonbyrne Aug 23, 2019

simonbyrne Aug 23, 2019

simonbyrne Aug 23, 2019

simonbyrne Aug 24, 2019

simonbyrne commented Aug 25, 2019 •

edited

Keno commented Aug 25, 2019

smldis Aug 25, 2019

simonbyrne commented Aug 26, 2019

Keno commented Aug 26, 2019

Keno commented Sep 25, 2019

simonbyrne commented Sep 25, 2019

Keno commented Sep 27, 2019

NHDaly commented Jan 26, 2020 •

edited

div with rounding modes [+ rounded division] #33040

div with rounding modes [+ rounded division] #33040

Conversation

Keno commented Aug 23, 2019 • edited

Keno commented Aug 23, 2019

StefanKarpinski commented Aug 23, 2019

simonbyrne commented Aug 23, 2019

simonbyrne Aug 23, 2019

Choose a reason for hiding this comment

simonbyrne Aug 23, 2019

Choose a reason for hiding this comment

simonbyrne Aug 23, 2019

Choose a reason for hiding this comment

simonbyrne Aug 23, 2019

Choose a reason for hiding this comment

simonbyrne Aug 23, 2019

Choose a reason for hiding this comment

simonbyrne Aug 24, 2019

Choose a reason for hiding this comment

simonbyrne commented Aug 25, 2019 • edited

Keno commented Aug 25, 2019

smldis Aug 25, 2019

Choose a reason for hiding this comment

simonbyrne commented Aug 26, 2019

Keno commented Aug 26, 2019

Keno commented Sep 25, 2019

simonbyrne commented Sep 25, 2019

Keno commented Sep 27, 2019

NHDaly commented Jan 26, 2020 • edited

Keno commented Aug 23, 2019 •

edited

simonbyrne commented Aug 25, 2019 •

edited

NHDaly commented Jan 26, 2020 •

edited