I've been putting this off for years but I have to tackle it some time
and I've made a start. It's the seemingly innocent problem of integer
division.

In general, the result of an integer division will require rounding and
a choice must be made as to which way to round. (There is rounding in
floating point, too, but that's a separate topic.)

Some languages take the easy way out and say that integer division
yields whatever result is yielded by the hardware but that's not
portable so I am looking for a default rounding mode which is most
useful to programmers that can be part of the language specification
while also being suitable for fast implementation.

AISI for signed integers there are these potential rounding modes

round up (towards positive infinity)
round down (towards negative infinity)
round towards zero
round away from zero
round to the nearest integer

Furthermore, for the last of those, round nearest, there are values
which are exactly mid way between two integers so there needs to be a
tie breaker to say what will happen in such a case, leading to these
variants:

round nearest up
round nearest down
round nearest towards zero
round nearest away from zero
round nearest even
round nearest odd

meaning the rounding would be to the nearest integer except that if two
integers were exactly the same distance away then the direction would be
up, down, etc, as stated.

I should add that for /unsigned/ integers the situation is similar
except that rounding towards zero is the same as rounding down, etc.

In other words, I make it that there are ten potential rounding modes
for signed integers and six potential rounding modes for unsigned ints,
and the question is over which to choose (at least as default).

Anyone disagree so far?

That's the overview. I'll reply with some of the mathematics of the issue.

--
James Harris

On 2021-06-18 10:12, James Harris wrote:
> I've been putting this off for years but I have to tackle it some time
> and I've made a start. It's the seemingly innocent problem of integer
> division.
>
> In general, the result of an integer division will require rounding and
> a choice must be made as to which way to round. (There is rounding in
> floating point, too, but that's a separate topic.)
>
> Some languages take the easy way out and say that integer division
> yields whatever result is yielded by the hardware but that's not
> portable so I am looking for a default rounding mode which is most
> useful to programmers that can be part of the language specification
> while also being suitable for fast implementation.
>
> AISI for signed integers there are these potential rounding modes
>
>   round up (towards positive infinity)
>   round down (towards negative infinity)
>   round towards zero
>   round away from zero
>   round to the nearest integer
>
> Furthermore, for the last of those, round nearest, there are values
> which are exactly mid way between two integers so there needs to be a
> tie breaker to say what will happen in such a case, leading to these
> variants:
>
>   round nearest up
>   round nearest down
>   round nearest towards zero
>   round nearest away from zero
>   round nearest even
>   round nearest odd
>
> meaning the rounding would be to the nearest integer except that if two
> integers were exactly the same distance away then the direction would be
> up, down, etc, as stated.
>
> I should add that for /unsigned/ integers the situation is similar
> except that rounding towards zero is the same as rounding down, etc.
>
> In other words, I make it that there are ten potential rounding modes
> for signed integers and six potential rounding modes for unsigned ints,
> and the question is over which to choose (at least as default).
>
> Anyone disagree so far?

I do. Integer division is defined mathematically. The following axioms
apply:

1. a = (a/b) * b + a rem b

The definition of full division

2. a > 0, b > 0 => a/b >= 0

The result is not negative when arguments are not.

3. a > 0, b > 0 -> a rem b >= 0

The remainder is not negative when arguments are not.

4. (-a)/b = -(a/b)
a/(-b) = -(a/b)

Multiplication association laws

These leave one valid implementation: truncation, e.g. rounding towards
zero.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

On 18/06/2021 09:12, James Harris wrote:

....

> In other words, I make it that there are ten potential rounding modes
> for signed integers and six potential rounding modes for unsigned ints,
> and the question is over which to choose (at least as default).

....

> That's the overview. I'll reply with some of the mathematics of the issue.

If we are dividing A by B there are two potentially useful results: the
quotient and the remainder, and that there are two types of remainder.
One is where the remainder is what's left over of A. The other is where
the remainder is what's left over of B.

For example,

-35 / 10

can lead to a remainder of 5 or -5, depending on how it's seen.
Following what seems to be the most common convention for MOD and REM
operators,

REM = -5 (i.e. what's left over of the -35).
MOD = 5 (i.e. what's left over of the 10).

In other words, REM has the sign of the dividend, MOD has the sign of
the divisor. I think that, also, REM will always be between 0 and the
dividend whereas MOD will always be between 0 and the divisor.

Tedious, isn't it! Now you know why I've been putting this off.....!

Where it gets slightly interesting is that I think that with the
appropriate rounding mode for division the other operations may be
natural consequences. Taking the above division,

-35 / 10

could be seen as either

-4 remainder 5
-3 remainder -5

so that in all cases if you add the remainder to (the divisor times the
quotient) then you get the original dividend. That's the Ada definition
of rem as set out in point 5 of

https://www.adaic.org/resources/add_content/standards/05rm/html/RM-4-5-5.html

But that's enough of that for now. I may come back to that particular
point but to save this post getting even more turgid let me ask you what
rounding mode or modes you think a programming language ought to support
for integer division. And which do you think should be default?

I think my own personal preference for integers is "round down" but I
see that Intel's signed divide operation uses "round towards zero" which
seems to me all kinds of wrong. :-(

Also, as a programmer, what integer rounding mode do you prefer a
language to have as default and would you see value in a language
providing other modes or would you consider that an unwanted complexity,
e.g. when reading someone else's code?

--
James Harris

On 2021-06-18 10:59, James Harris wrote:

> Following what seems to be the most common convention for MOD and REM
> operators,
>
>   REM = -5 (i.e. what's left over of the -35).
>   MOD =  5 (i.e. what's left over of the 10).

That is remainder proper vs. modulo ring complement.

mod is the number to add to the result of division to get back at the
ring's zero. The ring modulo is the dividend. The sign of the complement
is same as of the modulo = the sign of the dividend. The complement must
be from 0 to modulo - 1.

This gives you Ada definitions you refer to.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

On 18/06/2021 10:36, Dmitry A. Kazakov wrote:
> On 2021-06-18 10:12, James Harris wrote:
>> I've been putting this off for years but I have to tackle it some time
>> and I've made a start. It's the seemingly innocent problem of integer
>> division.
>>
>> In general, the result of an integer division will require rounding
>> and a choice must be made as to which way to round. (There is rounding
>> in floating point, too, but that's a separate topic.)
>>
>> Some languages take the easy way out and say that integer division
>> yields whatever result is yielded by the hardware but that's not
>> portable so I am looking for a default rounding mode which is most
>> useful to programmers that can be part of the language specification
>> while also being suitable for fast implementation.
>>
>> AISI for signed integers there are these potential rounding modes
>>
>>    round up (towards positive infinity)
>>    round down (towards negative infinity)
>>    round towards zero
>>    round away from zero
>>    round to the nearest integer
>>
>> Furthermore, for the last of those, round nearest, there are values
>> which are exactly mid way between two integers so there needs to be a
>> tie breaker to say what will happen in such a case, leading to these
>> variants:
>>
>>    round nearest up
>>    round nearest down
>>    round nearest towards zero
>>    round nearest away from zero
>>    round nearest even
>>    round nearest odd
>>
>> meaning the rounding would be to the nearest integer except that if
>> two integers were exactly the same distance away then the direction
>> would be up, down, etc, as stated.
>>
>> I should add that for /unsigned/ integers the situation is similar
>> except that rounding towards zero is the same as rounding down, etc.
>>
>> In other words, I make it that there are ten potential rounding modes
>> for signed integers and six potential rounding modes for unsigned
>> ints, and the question is over which to choose (at least as default).
>>
>> Anyone disagree so far?
>
> I do. Integer division is defined mathematically. The following axioms
> apply:
>
> 1. a = (a/b) * b + a rem b
>
> The definition of full division
>
> 2. a > 0, b > 0 => a/b >= 0
>
> The result is not negative when arguments are not.
>
> 3. a > 0, b > 0 -> a rem b >= 0
>
> The remainder is not negative when arguments are not.
>
> 4. (-a)/b  = -(a/b)
>    a/(-b)  = -(a/b)
>
> Multiplication association laws
>
> These leave one valid implementation: truncation, e.g. rounding towards
> zero.
>

That is one way to define division and remainder of integers. But it is
not the only way. You can also view "a / b" to mean "add or subtract
multiples of "b" to "a", until the remainder is in the range 0 up to
abs(b) - 1. That gives you round down (I think :-) ).

The round towards zero is nicer mathematically, IMHO, but it does mean
you can divide by a positive number and end up with a negative remainder
- that is not always something you want. And rounding down can be more
efficient than rounding towards zero.

As an example, C90 left it to the implementation to decide between round
to zero or round down. C99 then fixed it as round towards zero for
consistency and predictability.

My vote is - like yours - on round towards zero. But it is not quite as
simple a decision as you imply.

(For unsigned types, the result is the same - and there is no question.)

On 18/06/2021 10:44, David Brown wrote:
> The round towards zero is nicer mathematically, IMHO, [...].

We can all bandy around axioms [esp Dmitry]! But some seem
to me more fundamental than others. Start with:

(a) 23 cakes shared among 5 children is 4 each with 3 left over.

It would be absurd to claim they get 5 each with -2 left over.
So for positive integers, we always have rounding down with
remainder [if any] positive.

(b) If 5 more cakes appear, then they each get 1 more.

Consequently, if 5n more cakes appear, then each get n more,
and for consistency this has to apply equally if n is negative
[else taking away 5 cakes and then giving them back could
change the result]. So for negative numerators, we again have
to round down with remainder positive. This works better with
bank balances than with cakes.

(c) -23 cakes shared among -5 children is the same as (a).

Signs cancel in the same way here as throughout the rest of
mathematics. Negative children don't work very well -- there
are reasons why for thousands of years zero and negative
numbers were not "proper" numbers! -- but the maths does.

Everything else follows; and anything different is for
computational efficiency rather than mathematical niceness.

FWIW, any other rounding regime is easily defined in terms
of the Chosen One, so it's not really going to be a problem for
anyone whose special requirement differs from that.

--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Litolff

On 18/06/2021 13:26, Andy Walker wrote:
> On 18/06/2021 10:44, David Brown wrote:
>> The round towards zero is nicer mathematically, IMHO, [...].
>
>     We can all bandy around axioms [esp Dmitry]!  But some seem
> to me more fundamental than others.  Start with:
>
> (a)  23 cakes shared among 5 children is 4 each with 3 left over.
>
>      It would be absurd to claim they get 5 each with -2 left over.
>      So for positive integers, we always have rounding down with
>      remainder [if any] positive.

Agreed. (And note that rounding down and rounding towards zero are the
same for non-negative values.)

>
> (b)  If 5 more cakes appear, then they each get 1 more.
>
>      Consequently, if 5n more cakes appear, then each get n more,
>      and for consistency this has to apply equally if n is negative
>      [else taking away 5 cakes and then giving them back could
>      change the result].  So for negative numerators, we again have
>      to round down with remainder positive.  This works better with
>      bank balances than with cakes.

That would also be rounding down, but now for negative numerator.

>
> (c)  -23 cakes shared among -5 children is the same as (a).
>
>      Signs cancel in the same way here as throughout the rest of
>      mathematics.  Negative children don't work very well -- there
>      are reasons why for thousands of years zero and negative
>      numbers were not "proper" numbers! -- but the maths does.
>
>     Everything else follows;  and anything different is for
> computational efficiency rather than mathematical niceness.
>
>     FWIW, any other rounding regime is easily defined in terms
> of the Chosen One, so it's not really going to be a problem for
> anyone whose special requirement differs from that.
>

All this shows is that there are different ways to define division over
signed integers, which each give results that can be viewed as
reasonable, useful and intuitive from different viewpoints.

In reality, there is no good intuitive definition - because we don't
have an intuitive feel for -23 children or -5 cakes. There is no single
mathematical definition that will do the job, partly because "division"
involves two results, not just one, and because you can't make a
division function on integers that gives the key result you really want,
that (a / b) * b == a. And then we throw into the mix the fact that
numbers in a programming language rarely represent mathematical integers
exactly - they are usually bounded, and have odd effects at their
boundaries.

In programming languages, round down and round towards zero are the two
common strategies used. Each can be justified "intuitively" or
"mathematically".

And for those that think signed integers should be defined as wrapping,
because they think being "more defined" automatically means "better",
things get more complicated. For example, if we work with 16-bit values
(keeping the numbers smaller), then -5 / 3 should be -21847 remainder 0,
since -21847 * 3 equals -5 in wrapping 16-bit signed arithmetic.

On 18/06/2021 09:59, James Harris wrote:
> On 18/06/2021 09:12, James Harris wrote:
>
> ...
>
>> In other words, I make it that there are ten potential rounding modes
>> for signed integers and six potential rounding modes for unsigned
>> ints, and the question is over which to choose (at least as default).
>
> ...
>
>> That's the overview. I'll reply with some of the mathematics of the
>> issue.
>
> If we are dividing A by B there are two potentially useful results: the
> quotient and the remainder, and that there are two types of remainder.
> One is where the remainder is what's left over of A. The other is where
> the remainder is what's left over of B.

I've never heard of that one.

> For example,
>
>   -35 / 10
>
> can lead to a remainder of 5 or -5, depending on how it's seen.
> Following what seems to be the most common convention for MOD and REM
> operators,
>
>   REM = -5 (i.e. what's left over of the -35).
>   MOD =  5 (i.e. what's left over of the 10).

But will the 5 always be 5?

Perhaps you should have chosen values where the remainder wasn't exactly
half of B.

On 2021-06-18 14:13, David Brown wrote:

> In reality, there is no good intuitive definition - because we don't
> have an intuitive feel for -23 children or -5 cakes. There is no single
> mathematical definition that will do the job, partly because "division"
> involves two results, not just one, and because you can't make a
> division function on integers that gives the key result you really want,
> that (a / b) * b == a.

Actually there is. The concept is called continuation or extension. For
example, you take a system like natural numbers and then notice that
some elements are missing, e.g. a - b when a < b. This way negative
numbers can be defined as an extension of the set of natural numbers
fulfilled with negative ideals -a.

Doing so you keep as much properties intact as possible, all, if you
can. That way you can formally prove that there is really only one way
to produce negative numbers. Similarly, there is only one way to define
division of negative numbers. Because you want to keep fundamental
properties like (-a)/b = -(a/b). You have that for multiplication and
want to have it for its inverse as well.

Likewise, there is only one way to extend integers to reals. And only
one way to extend that to complex numbers. And there is no "good" way to
go any further without losing too much (e.g. quaternions).

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

On 2021-06-18 15:09, Bart wrote:

> But will the 5 always be 5?
>
> Perhaps you should have chosen values where the remainder wasn't exactly
> half of B.

The absolute value of the complement equals the absolute value of the
remainder if the divisor and the dividend have same signs.

|mod| = |rem|

If signs differ then, in absolute values the relation is this:

zero remains zero
everything else is

|mod| = |divisor| - |rem| (in absolute values)

E.g. -35 rem 3 = -2
-35 mod 3 = 1 (positive modulo 3)

2 + 1 = 3

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

On 18/06/2021 09:12, James Harris wrote:
> I've been putting this off for years but I have to tackle it some time
> and I've made a start. It's the seemingly innocent problem of integer
> division.
>
> In general, the result of an integer division will require rounding and
> a choice must be made as to which way to round. (There is rounding in
> floating point, too, but that's a separate topic.)
>
> Some languages take the easy way out and say that integer division
> yields whatever result is yielded by the hardware but that's not
> portable so I am looking for a default rounding mode which is most
> useful to programmers that can be part of the language specification
> while also being suitable for fast implementation.
>
> AISI for signed integers there are these potential rounding modes
>
>   round up (towards positive infinity)
>   round down (towards negative infinity)
>   round towards zero
>   round away from zero
>   round to the nearest integer
>
> Furthermore, for the last of those, round nearest, there are values
> which are exactly mid way between two integers so there needs to be a
> tie breaker to say what will happen in such a case, leading to these
> variants:
>
>   round nearest up
>   round nearest down
>   round nearest towards zero
>   round nearest away from zero
>   round nearest even
>   round nearest odd
>
> meaning the rounding would be to the nearest integer except that if two
> integers were exactly the same distance away then the direction would be
> up, down, etc, as stated.
>
> I should add that for /unsigned/ integers the situation is similar
> except that rounding towards zero is the same as rounding down, etc.
>
> In other words, I make it that there are ten potential rounding modes
> for signed integers and six potential rounding modes for unsigned ints,
> and the question is over which to choose (at least as default).
>
> Anyone disagree so far?

Disagree with what, that all this is far too complicated?

This is the approach I try use (here A and B are both positive):

* There is no rounding, not to nearest value anyway. The result of A/B
is the number of times you can subtract B from A while B>=A.

* With remainder, it is the final value of A in that last step

* When one operand is negative, the result should be negative. So (-A)/B
or A/(-B) is the same -(A/B), and ideally the same for remainder (but
see below).

* When both are negative, then they cancel out.

So that is a simple model, where the operations are only defined for
positive values, and any negative values are dealt with on top.

As to how it works in practice:

* x64 DIV hardware deals with A/B according to that model, including signs

* x64 REM hardware (remainder from DIV) almost does the same, but can
give a different sign for the result for A/-B or -A/-B. (Not sure what
to do about this, except try avoid negative remainders as no one knows
what they mean anyway. Perhaps always apply abs() to the result.)

* My bigint library, which uses signed magnitude, gives the same results
as DIV and REM above. This was a surprise, as REM is done in software.
(I haven't looked at why yet; perhaps it was simply to emulate x64 REM.)

There is another issue which I've discovered. While the above rounds
towards zero, if I try and optimise division by a constant (positive)
power of two by turning it into a right shift, then for negative A, it
will round away from zero!

(I've seen the effects of this in a jpeg decoder where in a line like this:

p^ := clamp((bb*57/2048)+luminance, 0,255)

the /2048 is turned into a shift. Then lsb of the final pixel may be
different when bb is negative. Fortunately for this app, that doesn't
matter.)

On 18/06/2021 15:22, Dmitry A. Kazakov wrote:
> On 2021-06-18 14:13, David Brown wrote:
>
>> In reality, there is no good intuitive definition - because we don't
>> have an intuitive feel for -23 children or -5 cakes.  There is no single
>> mathematical definition that will do the job, partly because "division"
>> involves two results, not just one, and because you can't make a
>> division function on integers that gives the key result you really want,
>> that (a / b) * b == a.
>
> Actually there is. The concept is called continuation or extension. For
> example, you take a system like natural numbers and then notice that
> some elements are missing, e.g. a - b when a < b. This way negative
> numbers can be defined as an extension of the set of natural numbers
> fulfilled with negative ideals -a.
>
> Doing so you keep as much properties intact as possible, all, if you
> can. That way you can formally prove that there is really only one way
> to produce negative numbers. Similarly, there is only one way to define
> division of negative numbers. Because you want to keep fundamental
> properties like (-a)/b = -(a/b). You have that for multiplication and
> want to have it for its inverse as well.
>
> Likewise, there is only one way to extend integers to reals. And only
> one way to extend that to complex numbers. And there is no "good" way to
> go any further without losing too much (e.g. quaternions).
>

Sure, you can do extensions in various ways (and you can, at least
sometimes, make choices about what you consider "fundamental properties"
- resulting in different extensions). And you can pick other algebraic
structures like modular rings for your integers.

But the prime purpose of integer types and operations in a programming
language are to be useful to the programmer - /not/ to satisfy
particular mathematical properties of mathematical integers, or other
number types. You only have a fixed finite size (for fixed size integer
types), and you will of necessity give up some mathematical properties
in creating your types and operations. It is always a compromise, and
it is a bad idea to declare certain properties as more "fundamental"
than others until you have looked at the options and decided on the
compromise that would work best for the language.

On 2021-06-18 14:13, David Brown wrote:

> In reality, there is no good intuitive definition - because we don't
> have an intuitive feel for -23 children or -5 cakes.

Let you borrowed $100 from a bank. You own $-100, the bank owns $100.
Say pay off the loan in 3 years. The amount of your money per year is
$-100/3 = $-33 or $33 of the bank's money. The remainder after 3 years
is $-1 of your money or $1 of the bank's money.

Calculations on your and bank's sides are same.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

On 2021-06-18 15:49, David Brown wrote:

> Sure, you can do extensions in various ways (and you can, at least
> sometimes, make choices about what you consider "fundamental properties"
> - resulting in different extensions). And you can pick other algebraic
> structures like modular rings for your integers.

But we are talking about integers here.

> But the prime purpose of integer types and operations in a programming
> language are to be useful to the programmer - /not/ to satisfy
> particular mathematical properties of mathematical integers, or other
> number types.

No. The purpose of *all* data types is to model entities of real world.
Programming language as well as programmers using them have no any
purpose outside the real world.

Integer is such an external entity existing in mathematics.

If an entity is modeled improperly, that constitutes a bug. Bugs must be
fixed.

> You only have a fixed finite size (for fixed size integer
> types), and you will of necessity give up some mathematical properties
> in creating your types and operations.

Sure. Computational models are never accurate. E.g. floating-point
operations might be not exactly commutative.

But in the case of division there is no reason to introduce systematic
inaccuracy. Likewise, you could not argue for 2+2=5 on the ground that
integers are incomputable. They are not, but you still can implement 2+2
properly.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

On 18/06/2021 15:09, Dmitry A. Kazakov wrote:
> On 2021-06-18 15:49, David Brown wrote:
>
>> Sure, you can do extensions in various ways (and you can, at least
>> sometimes, make choices about what you consider "fundamental properties"
>> - resulting in different extensions).  And you can pick other algebraic
>> structures like modular rings for your integers.
>
> But we are talking about integers here.
>
>> But the prime purpose of integer types and operations in a programming
>> language are to be useful to the programmer - /not/ to satisfy
>> particular mathematical properties of mathematical integers, or other
>> number types.
>
> No. The purpose of *all* data types is to model entities of real world.
> Programming language as well as programmers using them have no any
> purpose outside the real world.
>
> Integer is such an external entity existing in mathematics.
>
> If an entity is modeled improperly, that constitutes a bug. Bugs must be
> fixed.
>
>> You only have a fixed finite size (for fixed size integer
>> types), and you will of necessity give up some mathematical properties
>> in creating your types and operations.
>
> Sure. Computational models are never accurate. E.g. floating-point
> operations might be not exactly commutative.
>
> But in the case of division there is no reason to introduce systematic
> inaccuracy. Likewise, you could not argue for 2+2=5 on the ground that
> integers are incomputable. They are not, but you still can implement 2+2
> properly.

You can argue that 2+2=0 where you only have 2 bits of precision. This
program demonstrates that (bitfield here are unsigned):

record rec=
byte dummy: (x:2, y:2, z:2)
end

rec a
a.x := 2
a.y := 2
a.z := a.x+a.y

println a.x
println a.y
println a.z

Output is 2 2 0. However 'print a.x+a.y' displays 4, since internal
calculations are 64 bits wide.

Then you can argue instead that 9223372036854775808 +
9223372036854775808 = 0.

On 2021-06-18 17:38, Bart wrote:
> On 18/06/2021 15:09, Dmitry A. Kazakov wrote:
>> On 2021-06-18 15:49, David Brown wrote:
>>
>>> Sure, you can do extensions in various ways (and you can, at least
>>> sometimes, make choices about what you consider "fundamental properties"
>>> - resulting in different extensions).  And you can pick other algebraic
>>> structures like modular rings for your integers.
>>
>> But we are talking about integers here.
>>
>>> But the prime purpose of integer types and operations in a programming
>>> language are to be useful to the programmer - /not/ to satisfy
>>> particular mathematical properties of mathematical integers, or other
>>> number types.
>>
>> No. The purpose of *all* data types is to model entities of real
>> world. Programming language as well as programmers using them have no
>> any purpose outside the real world.
>>
>> Integer is such an external entity existing in mathematics.
>>
>> If an entity is modeled improperly, that constitutes a bug. Bugs must
>> be fixed.
>>
>>> You only have a fixed finite size (for fixed size integer
>>> types), and you will of necessity give up some mathematical properties
>>> in creating your types and operations.
>>
>> Sure. Computational models are never accurate. E.g. floating-point
>> operations might be not exactly commutative.
>>
>> But in the case of division there is no reason to introduce systematic
>> inaccuracy. Likewise, you could not argue for 2+2=5 on the ground that
>> integers are incomputable. They are not, but you still can implement
>> 2+2 properly.
>
> You can argue that 2+2=0 where you only have 2 bits of precision.

No, we had that discussion before.

The result must be either mathematically correct or else an ideal = dome
non-integer value. That could be propagation of an exception or +Inf
etc, never 0.

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

On 18/06/2021 09:59, James Harris wrote:
> On 18/06/2021 09:12, James Harris wrote:
>
> ...
>
>> In other words, I make it that there are ten potential rounding modes for
>> signed integers and six potential rounding modes for unsigned ints, and the
>> question is over which to choose (at least as default).
>
> ...
>
>> That's the overview. I'll reply with some of the mathematics of the issue.
>
> If we are dividing A by B there are two potentially useful results: the quotient
> and the remainder, and that there are two types of remainder. One is where the
> remainder is what's left over of A. The other is where the remainder is what's
> left over of B.
>
> For example,
>
>   -35 / 10
>
> can lead to a remainder of 5 or -5, depending on how it's seen. Following what
> seems to be the most common convention for MOD and REM operators,
>
>   REM = -5 (i.e. what's left over of the -35).
>   MOD =  5 (i.e. what's left over of the 10).
>
Yes, though I would put it differently.

The 'modulo' function is a well-known mathematical construct, such that
a mod b
maps a into numbers of the form 0<=m<b if b>=0
and m>b<=0 if b<=0
so if you plot a mod b against a you get a sawtooth waveform which shows nothing
unusual in the vicinity of zero.

Then, if you use 'mod' as your remainder function, and you plot a/b against a,
you get a set of discrete points which all lie on a straight line, which is a
mathematically clean property.

So it follows that (a+n)/b == a/b +n*b
which is useful if, for example, you are trying to compute the coordinates of
some item in a matrix, and then want to shift the origin.

BUT if you choose the so-called 'rem' as your remainder function, and you then
plot a/b against a, you do NOT get a straight line, and if you want to shift the
origin in some coordinate system, then you get a complete mess (and likely some
bugs too).

So it is clear which version any mathematician would prefer.

Now when the first computers were built, division was not built into the order
code, but had to be performed by a subroutine (and in those days subroutines
were usually written by mathematicians.

BUT when division came to be incorporated into the hardware, the hardware was
designed by Engineers, and unless those engineers were closely supervised by
Mathematicians (which they usually were in Europe, though not in America) they
did it wrong. So when I was designing the Orion computer for Ferranti, I
consulted the people in Portland Place and did it right. IBM, in general, did it
wrong, and hence so did FORTRAN (AIUI).

I as pretty sure Algol 60 got it right, and I made sure that Algol 68 did
likewise, and so, it would seem, did Ada. C sat on the fence (they recognised
there was a problem) but then fell off the wrong side. C++ also sat on the fence
(and still sits there SFAIK); but it also defined the % operator to be either
'rem' or 'mod' so as to be consistent with '/'. Bjarne had a good mathematical
background, and knew his Algol 68.

> In other words, REM has the sign of the dividend, MOD has the sign of the
> divisor. I think that, also, REM will always be between 0 and the dividend
> whereas MOD will always be between 0 and the divisor.
>
> Tedious, isn't it! Now you know why I've been putting this off.....!
>
> Where it gets slightly interesting is that I think that with the appropriate
> rounding mode for division the other operations may be natural consequences.
> Taking the above division,
>
>   -35 / 10
>
> could be seen as either
>
>   -4 remainder 5
>   -3 remainder -5
>
> so that in all cases if you add the remainder to (the divisor times the
> quotient) then you get the original dividend. That's the Ada definition of rem
> as set out in point 5 of
>
>
> https://www.adaic.org/resources/add_content/standards/05rm/html/RM-4-5-5.html
>
>
>
> But that's enough of that for now. I may come back to that particular point but
> to save this post getting even more turgid let me ask you what rounding mode or
> modes you think a programming language ought to support for integer division.
> And which do you think should be default?
>
> I think my own personal preference for integers is "round down" but I see that
> Intel's signed divide operation uses "round towards zero" which seems to me all
> kinds of wrong. :-(

Stick to your Guns.

--
Charles H. Lindsey ---------At my New Home, still doing my own thing------
Tel: +44 161 488 1845 Web: https://www.clerew.man.ac.uk
Email: chl@clerew.man.ac.uk Snail-mail: Apt 40, SK8 5BF, U.K.
PGP: 2C15F1A9 Fingerprint: 73 6D C2 51 93 A0 01 E7 65 E8 64 7E 14 A4 AB A5

On 18/06/2021 17:51, Charles Lindsey wrote:
> On 18/06/2021 09:59, James Harris wrote:

>> If we are dividing A by B there are two potentially useful results:
>> the quotient and the remainder, and that there are two types of
>> remainder. One is where the remainder is what's left over of A. The
>> other is where the remainder is what's left over of B.
>>
>> For example,
>>
>>    -35 / 10
>>
>> can lead to a remainder of 5 or -5, depending on how it's seen.
>> Following what seems to be the most common convention for MOD and REM
>> operators,
>>
>>    REM = -5 (i.e. what's left over of the -35).
>>    MOD =  5 (i.e. what's left over of the 10).
>>
> Yes, though I would put it differently.
>
> The 'modulo' function is a well-known mathematical construct, such that
>    a mod b
> maps a into numbers of the form 0<=m<b if b>=0
> and                             m>b<=0 if b<=0
> so if you plot a mod b against a you get a sawtooth waveform which shows
> nothing unusual in the vicinity of zero.
>
> Then, if you use 'mod' as your remainder function, and you plot a/b
> against a, you get a set of discrete points which all lie on a straight
> line, which is a mathematically clean property.

If I use A68G's % (int divide) and MOD operators, then plotting A/3
against A gives me a staircase shape, increasing from left to right,
with an extra-wide step about zero.

The MOD operator (A vs. A MOD 3) gives me the horizontal sawtooth curve
you mentioned. I'm not sure where the straight line comes into it.

If I use my REM function (that I mentioned in another post, with its
funny +/- signs), I get a sawtooth curve that is reflected about both X
and Y axes (180 degree rotation I think).

But given D = A % B, and remainder R = A rem B, that gives me the
ability to recover A using:

D*B + R

So perhaps that funny +/- behaviour has a purpose after all.

On 18/06/2021 09:36, Dmitry A. Kazakov wrote:
> On 2021-06-18 10:12, James Harris wrote:
>> I've been putting this off for years but I have to tackle it some time
>> and I've made a start. It's the seemingly innocent problem of integer
>> division.
>>
>> In general, the result of an integer division will require rounding
>> and a choice must be made as to which way to round. (There is rounding
>> in floating point, too, but that's a separate topic.)
>>
>> Some languages take the easy way out and say that integer division
>> yields whatever result is yielded by the hardware but that's not
>> portable so I am looking for a default rounding mode which is most
>> useful to programmers that can be part of the language specification
>> while also being suitable for fast implementation.
>>
>> AISI for signed integers there are these potential rounding modes
>>
>>    round up (towards positive infinity)
>>    round down (towards negative infinity)
>>    round towards zero
>>    round away from zero
>>    round to the nearest integer
>>
>> Furthermore, for the last of those, round nearest, there are values
>> which are exactly mid way between two integers so there needs to be a
>> tie breaker to say what will happen in such a case, leading to these
>> variants:
>>
>>    round nearest up
>>    round nearest down
>>    round nearest towards zero
>>    round nearest away from zero
>>    round nearest even
>>    round nearest odd
>>
>> meaning the rounding would be to the nearest integer except that if
>> two integers were exactly the same distance away then the direction
>> would be up, down, etc, as stated.
>>
>> I should add that for /unsigned/ integers the situation is similar
>> except that rounding towards zero is the same as rounding down, etc.
>>
>> In other words, I make it that there are ten potential rounding modes
>> for signed integers and six potential rounding modes for unsigned
>> ints, and the question is over which to choose (at least as default).
>>
>> Anyone disagree so far?
>
> I do.

Good. :-)

>
> Integer division is defined mathematically. The following axioms
> apply:
>
> 1. a = (a/b) * b + a rem b
>
> The definition of full division

I agree with that. It's a useful premise. Do you have any objection to
it being true for mod as well as for rem? Ada does not seem to define it
for mod and I can't see why not.

>
> 2. a > 0, b > 0 => a/b >= 0
>
> The result is not negative when arguments are not.
>
> 3. a > 0, b > 0 -> a rem b >= 0
>
> The remainder is not negative when arguments are not.
>
> 4. (-a)/b  = -(a/b)
>    a/(-b)  = -(a/b)
>
> Multiplication association laws
>
> These leave one valid implementation: truncation, e.g. rounding towards
> zero.
>

I am not sure your set of axioms deals with A and B both being negative
but AISI if the quotient is Q and the remainder is R then:

* Q will always have the 'xor' of the signs of A and B

* |R| will always be between 0 (inclusive) and |B| (exclusive)

* the sign of R, if R is nonzero, will depend on how Q was rounded

I don't see how you get to there being one valid implementation but it
seems increasingly likely that rounding a division towards zero gives
the Ada REM as a by-product whereas rounding towards minus infinity
would give the Ada MOD. That may be useful.

--
James Harris

On 18/06/2021 17:51, Charles Lindsey wrote:
> On 18/06/2021 09:59, James Harris wrote:

....

>
> BUT if you choose the so-called 'rem' as your remainder function, and
> you then plot a/b against a, you do NOT get a straight line, and if you
> want to shift the origin in some coordinate system, then you get a
> complete mess (and likely some bugs too).

I know what you mean. With rounding towards zero one gets irregular
results about x=zero rather than mathematical linearity. That's the main
reason I dislike it: it effectively treats below zero and above zero as
separate cases, which makes little or no sense to me.

>
> So it is clear which version any mathematician would prefer.

Curious to see that others prefer round towards zero. I think I'll have
to provide at least round down and round towards zero, and maybe others
as well.

....

>> I think my own personal preference for integers is "round down" but I
>> see that Intel's signed divide operation uses "round towards zero"
>> which seems to me all kinds of wrong. :-(
>
> Stick to your Guns.
>

I may well do!

The thing is, on hardware which rounds division towards zero, such as
x86, how expensive is it to implement integer round down?

--
James Harris

On 18/06/2021 12:26, Andy Walker wrote:
> On 18/06/2021 10:44, David Brown wrote:
>> The round towards zero is nicer mathematically, IMHO, [...].
>
>     We can all bandy around axioms [esp Dmitry]!  But some seem
> to me more fundamental than others.  Start with:
>
> (a)  23 cakes shared among 5 children is 4 each with 3 left over.
>
>      It would be absurd to claim they get 5 each with -2 left over.
>      So for positive integers, we always have rounding down with
>      remainder [if any] positive.
>
> (b)  If 5 more cakes appear, then they each get 1 more.
>
>      Consequently, if 5n more cakes appear, then each get n more,
>      and for consistency this has to apply equally if n is negative
>      [else taking away 5 cakes and then giving them back could
>      change the result].  So for negative numerators, we again have
>      to round down with remainder positive.  This works better with
>      bank balances than with cakes.

So you prefer rounding down and therefore (with a negative numerator)

-23 / 5 = -5 remainder 2

?

I don't necessarily disagree with that. Just checking whether that's
what you mean.

--
James Harris

On 18/06/2021 14:09, Bart wrote:
> On 18/06/2021 09:59, James Harris wrote:

....

>> For example,
>>
>>    -35 / 10
>>
>> can lead to a remainder of 5 or -5, depending on how it's seen.
>> Following what seems to be the most common convention for MOD and REM
>> operators,
>>
>>    REM = -5 (i.e. what's left over of the -35).
>>    MOD =  5 (i.e. what's left over of the 10).
>
> But will the 5 always be 5?
>
> Perhaps you should have chosen values where the remainder wasn't exactly
> half of B.

OK, here's an example of -32 / 10. The result can be either of

-4 remainder 8
-3 remainder -2

Whereas 32 / -10 can result in either of

-4 remainder -8
-3 remainder 2

For just changing where the sign is that's quite a contrast! :-(

In each case the lines are in the order

round down (and MOD)
round towards zero (and REM)

--
James Harris

On 18/06/2021 14:40, Bart wrote:
> On 18/06/2021 09:12, James Harris wrote:
>> I've been putting this off for years but I have to tackle it some time
>> and I've made a start. It's the seemingly innocent problem of integer
>> division.
>>
>> In general, the result of an integer division will require rounding
>> and a choice must be made as to which way to round. (There is rounding
>> in floating point, too, but that's a separate topic.)
>>
>> Some languages take the easy way out and say that integer division
>> yields whatever result is yielded by the hardware but that's not
>> portable so I am looking for a default rounding mode which is most
>> useful to programmers that can be part of the language specification
>> while also being suitable for fast implementation.
>>
>> AISI for signed integers there are these potential rounding modes
>>
>>    round up (towards positive infinity)
>>    round down (towards negative infinity)
>>    round towards zero
>>    round away from zero
>>    round to the nearest integer
>>
>> Furthermore, for the last of those, round nearest, there are values
>> which are exactly mid way between two integers so there needs to be a
>> tie breaker to say what will happen in such a case, leading to these
>> variants:
>>
>>    round nearest up
>>    round nearest down
>>    round nearest towards zero
>>    round nearest away from zero
>>    round nearest even
>>    round nearest odd
>>
>> meaning the rounding would be to the nearest integer except that if
>> two integers were exactly the same distance away then the direction
>> would be up, down, etc, as stated.
>>
>> I should add that for /unsigned/ integers the situation is similar
>> except that rounding towards zero is the same as rounding down, etc.
>>
>> In other words, I make it that there are ten potential rounding modes
>> for signed integers and six potential rounding modes for unsigned
>> ints, and the question is over which to choose (at least as default).
>>
>> Anyone disagree so far?
>
> Disagree with what, that all this is far too complicated?
>

Do you disagree with there being, at least in theory, those ten
potential rounding modes for signed and six for unsigned?

Also, would you support them all in a programming language? Or which
ones would you support? And, I have to ask, if you would support more
than one, how would you have a programmer express the rounding mode in
the syntax?

....

> (I've seen the effects of this in a jpeg decoder where in a line like this:
>
>     p^ := clamp((bb*57/2048)+luminance, 0,255)
>
> the /2048 is turned into a shift. Then lsb of the final pixel may be
> different when bb is negative. Fortunately for this app, that doesn't
> matter.)

Good point. What does two's complement right shift do to negative
numbers? A signed shift one place right applied to

2'1110_0001'
2'1110_0000'

would in both cases result in 2'1111_0000'.

I think (using an online calculator) that that means -31 and -32 both
become -16. Which I think means they both round DOWN.

If so, that's effectively another vote for Charles's suggestion to round
down by default, rather than towards zero.

--
James Harris

On 19/06/2021 10:46, James Harris wrote:
> On 18/06/2021 12:26, Andy Walker wrote:
>> On 18/06/2021 10:44, David Brown wrote:
>>> The round towards zero is nicer mathematically, IMHO, [...].
>>
>>      We can all bandy around axioms [esp Dmitry]!  But some seem
>> to me more fundamental than others.  Start with:
>>
>> (a)  23 cakes shared among 5 children is 4 each with 3 left over.
>>
>>       It would be absurd to claim they get 5 each with -2 left over.
>>       So for positive integers, we always have rounding down with
>>       remainder [if any] positive.
>>
>> (b)  If 5 more cakes appear, then they each get 1 more.
>>
>>       Consequently, if 5n more cakes appear, then each get n more,
>>       and for consistency this has to apply equally if n is negative
>>       [else taking away 5 cakes and then giving them back could
>>       change the result].  So for negative numerators, we again have
>>       to round down with remainder positive.  This works better with
>>       bank balances than with cakes.
>
> So you prefer rounding down and therefore (with a negative numerator)
>
>   -23 / 5 = -5 remainder 2

So -1/1000 is -1, with remainder 999?

I can't say I find that intuitive. Apart from which, how much work is it
going to take to get those results given that most hardware works
differently?

If you want to get mathematical, then 1/1000 and -1/1000 will give the
float values 0.001 and -0.001, differing only in sign. Scale the values
by X, and the results are equally scaled.

If you convert such a float result to integer, then the result will not
match the proposal, unless you introduce equivalent rounding methods for
converting float to integer.

The usual behaviour is to round towards zero.

On 19/06/2021 11:33, Bart wrote:
> On 19/06/2021 10:46, James Harris wrote:

....

>> So you prefer rounding down and therefore (with a negative numerator)
>>
>>    -23 / 5 = -5 remainder 2
>
> So -1/1000 is -1, with remainder 999?

If, for that expression, one is using mod and mod is defined as
resulting in a number between 0 and 999 then yes. What other choice
would there be?

I think I'm going to have to offer the programmer a choice of at least
rounding integer division down and rounding towards zero, and maybe all
the others.

The questions, then, are which to make default and how to specify some
other rounding mode in the syntax.

>
> I can't say I find that intuitive.

AISI one can think of mod as providing a remainder in the range one
requires. For example, if one wants a remainder in the range 0 to 9 (say
for display of a decimal number) then one uses a denominator of 10. And
if one wants a remainder to be in the range 0 to -9 then one uses a
denominator of -10 - both with the mod operation (rounding down, i.e.
towards minus infinity).

Correspondingly, the case you mention looks like it is asking for a mod
in the range 0 to 999. And that's what it would get.

Essentially, one would use mod (rounding down) if one wanted a remainder
to be in a range determined by the /denominator/, whereas if one wanted
a remainder to be what's left /of the numerator/ then one would use rem
(rounding towards zero).

IOW, mod is controlled by the denominator and rem is controlled by the
numerator.

>
> Apart from which, how much work is it
> going to take to get those results given that most hardware works
> differently?

I don't know. Any suggestions? :-)

>
> If you want to get mathematical, then 1/1000 and -1/1000 will give the
> float values 0.001 and -0.001, differing only in sign. Scale the values
> by X, and the results are equally scaled.
>
> If you convert such a float result to integer, then the result will not
> match the proposal, unless you introduce equivalent rounding methods for
> converting float to integer.
>
> The usual behaviour is to round towards zero.

For some definition of 'usual'...!

--
James Harris