Safe integer division and range arithmetic

[Mike Samuel]

I was looking at "Range Arithmetic" and Wuffs approach to {under,over}flow.

What do you do for integer division?

if denominator != 0 {

    x = numerator / denominator;

} else {

    ...

}

I see the note on TryFoo in interval.go

> // Those operator-like methods come in two forms: Foo and TryFoo. The TryFoo

> // forms return (z IntRange, ok bool). The bool indicates success, as
> // operations like dividing by zero or shifting by a negative value can fail.

but was wondering if there's something else that happens before you get a coarse grained !ok but couldn't follow lang/check/bounds.go.

If denominator's type before the if is base.u32[-100 ..= 101] do you further specialize that to [-100, 0)∪[1, 101) internally or are there facts that cannot be expressed in terms of singular `<` and `≤`?

Did you reject range arithmetic like Racket's data/integer-set for pragmatic reasons?

I imagine that if there were many ranges you get O(n**2) problems but a ceiling on count size like TypeScript does for string value unions seems like it'd work.

cheers,

mike

(Wuffs seems very cool.)

[Nigel Tao]

On Fri, Sep 18, 2020 at 4:26 AM Mike Samuel <mikes...@gmail.com> wrote:
> If denominator's type before the if is base.u32[-100 ..= 101] do you further specialize that to [-100, 0)∪[1, 101) internally

Yes!
https://github.com/google/wuffs/blob/9557d89c5658b16d713d5c1afaa8ad80170da620/lib/interval/interval.go#L655

But, a few lines above, if the denominator range y contains 0, we just
return ok == false.

> Did you reject range arithmetic like Racket's data/integer-set for pragmatic reasons?

A single range is simpler than multiple ranges, and we haven't needed
multiple ranges so far.

FWIW, in the 11 packages under std/, the only uses of division so far
are to divide by constant powers-of-2, such as "x / 16" or "(y + 7) /
8", which could easily be re-written as right-shifts.

[Mike Samuel]

On Thu, Sep 17, 2020 at 9:33 PM Nigel Tao <nige...@golang.org> wrote:

On Fri, Sep 18, 2020 at 4:26 AM Mike Samuel <mikes...@gmail.com> wrote:
> If denominator's type before the if is base.u32[-100 ..= 101] do you further specialize that to [-100, 0)∪[1, 101) internally

Yes!
https://github.com/google/wuffs/blob/9557d89c5658b16d713d5c1afaa8ad80170da620/lib/interval/interval.go#L655

But, a few lines above, if the denominator range y contains 0, we just
return ok == false.

Awesome.  Thanks for the pointer.

 

> Did you reject range arithmetic like Racket's data/integer-set for pragmatic reasons?

A single range is simpler than multiple ranges, and we haven't needed
multiple ranges so far.

FWIW, in the 11 packages under std/, the only uses of division so far
are to divide by constant powers-of-2, such as "x / 16" or "(y + 7) /
8", which could easily be re-written as right-shifts.

Makes sense.