On 18/06/2021 19:23, Bart wrote:
> On 18/06/2021 17:51, Charles Lindsey wrote:

....

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

That's surprising. A wide step around zero seems to me to be
mathematically irregular and might be the result of rem but is not what
I would expect of a mod operator.

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

I found a number of such graphs at

https://en.wikipedia.org/wiki/Modulo_operation#Variants_of_the_definition

Which of the graphs shown there match what you see?

--
James Harris

On 19/06/2021 12:55, James Harris wrote:
> On 18/06/2021 19:23, Bart wrote:
>> On 18/06/2021 17:51, Charles Lindsey wrote:
>
> ...
>
>>> 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.
>
> That's surprising. A wide step around zero seems to me to be
> mathematically irregular and might be the result of rem but is not what
> I would expect of a mod operator.
>
>>
>> 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).
>
> I found a number of such graphs at
>
>
> https://en.wikipedia.org/wiki/Modulo_operation#Variants_of_the_definition
>
> Which of the graphs shown there match what you see?
>

The very first graph there shows an example of the wide step for divide,
in red.

The top left one matches the behaviour of my languages for integer
divide and rem. But none exactly match that of A68G, which is a
combination of the top red divide graph, and the left green sawtooth in
the second box.

On 19/06/2021 15:06, Bart wrote:
> On 19/06/2021 12:55, James Harris wrote:
>> On 18/06/2021 19:23, Bart wrote:
>>> On 18/06/2021 17:51, Charles Lindsey wrote:
>>
>> ...
>>
>>>> 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.
>>
>> That's surprising. A wide step around zero seems to me to be
>> mathematically irregular and might be the result of rem but is not
>> what I would expect of a mod operator.
>>
>>>
>>> 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).
>>
>> I found a number of such graphs at
>>
>>   
>> https://en.wikipedia.org/wiki/Modulo_operation#Variants_of_the_definition
>>
>> Which of the graphs shown there match what you see?
>>
>
> The very first graph there shows an example of the wide step for divide,
> in red.
>
> The top left one matches the behaviour of my languages for integer
> divide and rem. But none exactly match that of A68G, which is a
> combination of the top red divide graph, and the left green sawtooth in
> the second box.

I don't know Algol 68, but according to the table further down on the
page, it uses the "Euclidean definition" (in which the remainder is
always non-negative, regardless of the sign of the numerator and
denominator).

The page and the graphs are quite instructive, I think. They show that
there is always a balance of properties here - whichever algorithm a
language picks, there will be compromises and effects that don't seem
reasonable or that don't match useful mathematical identities.

The table for languages may be a useful guide for a new language. For
example, if you are making a new language that is mostly C-like in style
and appearance, picking the same division as C (truncation) would
minimise surprises.

On 2021-06-19 10:45, James Harris wrote:
> 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

Just apply the rules, mathematics is your friend:

(-a)/(-b) = [apply (-a)/b = -(a/b)]
= -(a/(-b)) = [apply a/(-b) = -(a/b)]
= -(-(a/b)) = [apply -(-a) = a]
= a/b

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

On 19/06/2021 10:46, James Harris wrote:
[I wrote:]
>> [...] 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.

Yes. In the terms of the Wiki page that you referred us to,
that's "floored" or "euclidean" division, and satisfies identities

(a + nb) % b == a % b + n and a % b * b + a %* b = a

for all integers a, b, n provided b > 0. IRL, b is rarely negative,
and I don't really care what happens in that case, but if pushed I
would vote for "a *% b" to be non-negative ["euclidean"].

As Bart said, A68G [correctly according to the RR] uses
"truncated" quotient and "euclidean" remainder, which seems to me
to be broken, even if Charles did insist on it on advice from
mathematicians. As a mathematician, I agree with Knuth, Boute and
Leijen, the only named people in the Wiki article, that "floored"
and "euclidean" are superior to "truncated". According to Boute
in that article, Pascal is broken as it fails the second identity
above; if so, then Algol [60 and 68] is broken in exactly the
same way.

Like Bart, I don't like the "wide step" [which follows from
not obeying the first identity above], and don't see how any real
mathematician could approve of it. If that's a consequence of
designing languages around what's in the hardware [which seems to
be the claim], then the hardware is also broken. How fast do you
want your incorrect results? The only mitigation is that [again,
IRL] the principal uses have positive numerators and denominators
[eg, in number theory], for which almost all definitions agree.

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

On 19/06/2021 11:32, James Harris wrote:
> On 18/06/2021 14:40, Bart wrote:

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

If you say so. I've never really looked into it in that detail!

> Also, would you support them all in a programming language?

Not in any of mine.

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

My atttitude is that I simply don't want those all complications, all
those possibilities to have to think about, in the language. It makes it
harder to read and write especially for those equally uninterested.

The language will provide one default way of operating (hopefully the
most useful and/or intuitive), but should provide means of achieving the
other results via other features.

For example, with the simpler operation of converting float to integer,
it will round down towards zero (so both 5.8 and 5.2 end up as 5, and
-5.8 and -5.2 as -5)

This I believe is the default behaviour of x64's cvttsd2si instruction
(double 2 int).

Anyway, for any other behaviour, I use a combinination of round() (to
nearest int, but return a float), floor() and ceil().

And the same with any special requirements for integer divide and rem.

Until this thread, I'd assumed mod and rem were the same! (What C calls
'mod', its % operator, gives the same results as my 'rem'.)

If you are creating languages for other people to use (or those like
me), they might know about any of this either.

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

Yes, -32 always becomes -16 with either divide or shift.

But -31 because -15 with divide or -16 with shift.

The discrepancy is the problem. I think that most divides will not be by
powers of two, so what divide does is more important.

A simple optimisation is to turn a divide by a constant power of two
into a shift. A more complex one is dividing by any constant value of
two, turned into multiplies and shifts.

But they ideally need to behave the same way as dividing by a variable.
(This is where my language can give a different result. I've put it down
as a quirk for now.)

On 19/06/2021 17:14, Bart wrote:
> On 19/06/2021 11:32, James Harris wrote:
>> On 18/06/2021 14:40, Bart wrote:

....

> My atttitude is that I simply don't want those all complications, all
> those possibilities to have to think about, in the language. It makes it
> harder to read and write especially for those equally uninterested.

Neither do I. But

(1) I want the computations of a program to be the same on any machine.
That means that the definition has to be part of the language so that
implementations are not free to produce different results.

(2) I suspect that some programmers will want such controls.

>
> The language will provide one default way of operating (hopefully the
> most useful and/or intuitive), but should provide means of achieving the
> other results via other features.
>
> For example, with the simpler operation of converting float to integer,
> it will round down towards zero (so both 5.8 and 5.2 end up as 5, and
> -5.8 and -5.2 as -5)
>
> This I believe is the default behaviour of x64's cvttsd2si instruction
> (double 2 int).

So I see, though truncation seems to be Intel's favourite (as it is of
some people here) so it's perhaps not completely surprising that they
have an instruction for it. The more general

cvtsd2si

rounds according to the rounding-control bits in the MXCSR. By default
that's 'round nearest even' but it can be changed to 'round down',
'round up' and 'round towards zero (aka truncate)'.

>
> Anyway, for any other behaviour, I use a combinination of round() (to
> nearest int, but return a float), floor() and ceil().

OK.

>
> And the same with any special requirements for integer divide and rem.
>
> Until this thread, I'd assumed mod and rem were the same! (What C calls
> 'mod', its % operator, gives the same results as my 'rem'.)
>
> If you are creating languages for other people to use (or those like
> me), they might know about any of this either.

Yes, that's a bit of a problem. I need to find some way to make the
default behaviour as intuitive as possible and not intimidating.

>
>>> 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.
>
> Yes, -32 always becomes -16 with either divide or shift.
>
> But -31 because -15 with divide or -16 with shift.
>
> The discrepancy is the problem. I think that most divides will not be by
> powers of two, so what divide does is more important.

I don't think the fact that it's a power of 2 is significant. For
example, say I pick -53 and -54. In 8-bit binary they are

2'11001011'
2'11001010'

shifting either of them right gives

2'11100101'

which is -27 which (as the true result for -53 / 2 is -26.5) is, again,
rounded down.

Notably, this is not CPU specific. It is pure 2's complement shifting
and should be the same on any CPU which uses 2's complement
representation. And both positive and negative numbers are thereby
rounded down.

Binary conversions courtesy of

https://www.omnicalculator.com/math/twos-complement

>
> A simple optimisation is to turn a divide by a constant power of two
> into a shift.

I agree. And if >> 1 rounds down then / 2 probably should do as well, at
least by default, as programmers are used to replacing one with the other.

>
> A more complex one is dividing by any constant value of
> two, turned into multiplies and shifts.
>
> But they ideally need to behave the same way as dividing by a variable.
> (This is where my language can give a different result. I've put it down
> as a quirk for now.)
>

Yes. You may agree that the code fragment

int d = 4, x, y ,z;

x = val >> 2;
y = val / 4;
z = val / d;

should assign the same value to x, y and z irrespective of what is in val.

--
James Harris

On Fri, 18 Jun 2021 09:12:45 +0100
James Harris <james.harris.1@gmail.com> wrote:

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

I see this as an issue of matching the hardware capabilities to the
demands of the environment.

hardware: central processing unit, microprocessor, floating-point unit

business environment: banking, accounting, brokerage, ...
academic environment: mathematics, physics, chemistry, engineering, ...
programming environment: C, Forth, Fortran, COBOL, ...

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

Have you looked at the specifications for C and FORTH? Or, etc. like
COBOL and Fortran? I.e., I'd suspect this problem was "solved" decades
ago with the development of early programming languages.

E.g., a web page on some types of accounting rounding, which some lowly
programmer will have to figure out how to program:
https://www.syspro.com/blog/applying-and-operating-erp/rounding-for-accounting-accuracy/

--
What is hidden in the ground, when found, is hidden there again?

On 19/06/2021 12:55, James Harris wrote:
> On 18/06/2021 19:23, Bart wrote:
>> On 18/06/2021 17:51, Charles Lindsey wrote:
>
> ...
>
>>> 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.
>
> That's surprising. A wide step around zero seems to me to be mathematically
> irregular and might be the result of rem but is not what I would expect of a mod
> operator.
>
>>
>> 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).
>
> I found a number of such graphs at
>
>   https://en.wikipedia.org/wiki/Modulo_operation#Variants_of_the_definition
>
> Which of the graphs shown there match what you see?

Yes, that page is very good. Clearly, the definition I gave for MOD was wrong
(it is a long time since I had dealing with the A68 Report). But I also not that
there is a pencilled correction in my copy of my Informal Introduction to the
explanation for MOD and I am suspicious of my description of OVER.

The plots given in that page are helpful, and show some nice linear one for the
"good" implementations.

I had not heard of the term "Euclidean division", but the paper by Boute that is
referred to might be interesting, and could be downloaded from ACM.
>
>
>

--
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 19/06/2021 19:22, James Harris wrote:
> On 19/06/2021 17:14, Bart wrote:
>> On 19/06/2021 11:32, James Harris wrote:
>>> On 18/06/2021 14:40, Bart wrote:
>
> ...
>
>> My atttitude is that I simply don't want those all complications, all
>> those possibilities to have to think about, in the language. It makes
>> it harder to read and write especially for those equally uninterested.
>
> Neither do I. But
>
> (1) I want the computations of a program to be the same on any machine.
> That means that the definition has to be part of the language so that
> implementations are not free to produce different results.
>
> (2) I suspect that some programmers will want such controls.

I've looked in more detail at that page of graphs you linked to, which
gives a summary of support for MOD and REM across many languages (you'll
have to scroll past the graphs..).

There it seems that for integer operands, most languages support only
one version, and some support two.

Based on that, I may myself add support for an extra operator, once I
understand what it does, although it will be mainly for box-ticking.

Two alternatives is manageable I think, especially as so many well-known
languages offer them. But 10 (or was it 16) is too much.

>> This I believe is the default behaviour of x64's cvttsd2si instruction
>> (double 2 int).
>
> So I see, though truncation seems to be Intel's favourite (as it is of
> some people here) so it's perhaps not completely surprising that they
> have an instruction for it. The more general
>
>   cvtsd2si
>
> rounds according to the rounding-control bits in the MXCSR. By default
> that's 'round nearest even' but it can be changed to 'round down',
> 'round up' and 'round towards zero (aka truncate)'.

Yeah I remember similar flags for the x87. And I vaguely remember having
to switch from cvtsd2si to cvttsd2si likely for such issues. (I like how
these new opcodes trip off the tongue so easily.)

>> The discrepancy is the problem. I think that most divides will not be
>> by powers of two, so what divide does is more important.
>
> I don't think the fact that it's a power of 2 is significant. For
> example, say I pick -53 and -54. In 8-bit binary they are
>
>   2'11001011'
>   2'11001010'
>
> shifting either of them right gives
>
>   2'11100101'
>
> which is -27 which (as the true result for -53 / 2 is -26.5) is, again,
> rounded down.

Well, ANY shift will necessarily scale by a power of two.

Usually this is a purely logical operation on a collection of bits: bit
1 is shifted into bit 0. But when used to implement a fast divide, then
you need to look at how it rounds when shifting a number.

>> But they ideally need to behave the same way as dividing by a
>> variable. (This is where my language can give a different result. I've
>> put it down as a quirk for now.)
>>
>
> Yes. You may agree that the code fragment
>
>   int d = 4, x, y ,z;
>
>   x = val >> 2;
>   y = val / 4;
>   z = val / d;
>
> should assign the same value to x, y and z irrespective of what is in val.

My language does that, when val is positive or is unsigned.

However, even if it's fixed for /4 and /d (which can give different
values), I can't touch >>4; a right-shift is a right-shift with specific
behaviour.

(I can do this by generating a special op which is not DIV, neither SHR,
but an inbetween one. This does a runtime check for a positive value and
chooses whether to do DIV or SHR. A bit messy though, and it may lose
some of the benefits of doing shift.)

On 2021-06-20 00:25, Bart wrote:
> On 19/06/2021 19:22, James Harris wrote:

>> I don't think the fact that it's a power of 2 is significant. For
>> example, say I pick -53 and -54. In 8-bit binary they are
>>
>>    2'11001011'
>>    2'11001010'
>>
>> shifting either of them right gives
>>
>>    2'11100101'
>>
>> which is -27 which (as the true result for -53 / 2 is -26.5) is,
>> again, rounded down.

The morale: do not use shifts with numbers [*]

> Well, ANY shift will necessarily scale by a power of two.

Nope. It is the power of the radix, which can be 2 or 10, 16 whatever.
Right "arithmetic" shift pushes radix - 1 into to the leftmost unit.
E.g. say x is packed decimal (:-)) [**]

> Usually this is a purely logical operation on a collection of bits: bit
> 1 is shifted into bit 0. But when used to implement a fast divide, then
> you need to look at how it rounds when shifting a number.

Nope. Logical /= arithmetical. Logical shift /= arithmetical shift /=
circular shift /= dozens of other variants of shifts.

---------------
* Invest into optimization rather than mess with semantics. Modular x/2
is trivial to optimize to a shift on a 2's complement machine or maybe
it needs no optimization at all. Have you actually measured the times
x/2 and shift_right(x,2) take?

** IEEE 754 still deploys two messy decimal radix formats. Feel free to
add them in your language!

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

On 20/06/2021 09:09, Dmitry A. Kazakov wrote:
> On 2021-06-20 00:25, Bart wrote:
>> On 19/06/2021 19:22, James Harris wrote:
>
>>> I don't think the fact that it's a power of 2 is significant. For
>>> example, say I pick -53 and -54. In 8-bit binary they are
>>>
>>>    2'11001011'
>>>    2'11001010'
>>>
>>> shifting either of them right gives
>>>
>>>    2'11100101'
>>>
>>> which is -27 which (as the true result for -53 / 2 is -26.5) is,
>>> again, rounded down.
>
> The morale: do not use shifts with numbers [*]
>
>> Well, ANY shift will necessarily scale by a power of two.
>
> Nope. It is the power of the radix, which can be 2 or 10, 16 whatever.
> Right "arithmetic" shift pushes radix - 1 into to the leftmost unit.
> E.g. say x is packed decimal (:-)) [**]
>
>> Usually this is a purely logical operation on a collection of bits:
>> bit 1 is shifted into bit 0. But when used to implement a fast divide,
>> then you need to look at how it rounds when shifting a number.
>
> Nope. Logical /= arithmetical. Logical shift /= arithmetical shift /=
> circular shift /= dozens of other variants of shifts.

No. Shift is almost invariably meant as a binary shift.

I have a decimal number type which uses radix 1,000,000,000. Making A>>B
shift a billion at a time is not very useful!

When I had to implement someone's algorithm which involved shifts on big
numbers, I had to do them as binary shifts. Which here means that
multiplying or dividing by powers of two. Attempting anything else would
be meaningless.

Fortunately it didn't any other logical operations such as 'and' or 'or'
which would really require a pure binary type; emulation is too complex.

Shifting '-1 into the leftmost unit' is only relevant for two's
complement or the equivalent. My decimal type uses signed magnitude.

> ---------------
> * Invest into optimization rather than mess with semantics. Modular x/2
> is trivial to optimize to a shift on a 2's complement machine or maybe
> it needs no optimization at all. Have you actually measured the times
> x/2 and shift_right(x,2) take?

If I execute this loop:

to 100 million do
c:=a/b
c:=a/b
c:=a/b
c:=a/b
c:=a/b
c:=a/b
c:=a/b
c:=a/b
c:=a/b
c:=a/b
od

then when A is an integer variable, and B is a constant 256, it takes
about 0.5 seconds (using SAR). When B is either a constant 255 or a
variable containing 256, it takes 20 seconds (using CQO; IDIV).

If I compare dividing by constant 2**60 and constant 2**60-1, then it's
0.5 seconds vs 32 seconds.

On which machine is hardware divide faster than shift?

On 2021-06-20 12:42, Bart wrote:
> On 20/06/2021 09:09, Dmitry A. Kazakov wrote:
>> On 2021-06-20 00:25, Bart wrote:
>>> On 19/06/2021 19:22, James Harris wrote:
>>
>>>> I don't think the fact that it's a power of 2 is significant. For
>>>> example, say I pick -53 and -54. In 8-bit binary they are
>>>>
>>>>    2'11001011'
>>>>    2'11001010'
>>>>
>>>> shifting either of them right gives
>>>>
>>>>    2'11100101'
>>>>
>>>> which is -27 which (as the true result for -53 / 2 is -26.5) is,
>>>> again, rounded down.
>>
>> The morale: do not use shifts with numbers [*]
>>
>>> Well, ANY shift will necessarily scale by a power of two.
>>
>> Nope. It is the power of the radix, which can be 2 or 10, 16 whatever.
>> Right "arithmetic" shift pushes radix - 1 into to the leftmost unit.
>> E.g. say x is packed decimal (:-)) [**]
>>
>>> Usually this is a purely logical operation on a collection of bits:
>>> bit 1 is shifted into bit 0. But when used to implement a fast
>>> divide, then you need to look at how it rounds when shifting a number.
>>
>> Nope. Logical /= arithmetical. Logical shift /= arithmetical shift /=
>> circular shift /= dozens of other variants of shifts.
>
> No. Shift is almost invariably meant as a binary shift.

Even so, [binary] logical /= arithmetical /= circular.

> I have a decimal number type which uses radix 1,000,000,000. Making A>>B
> shift a billion at a time is not very useful!

Per definition decimal means radix = 10. Shifting billionary numbers is
no less useful than having them in first place.

> When I had to implement someone's algorithm which involved shifts on big
> numbers,

Do not use ill-defined algorithms.

>> ---------------
>> * Invest into optimization rather than mess with semantics. Modular
>> x/2 is trivial to optimize to a shift on a 2's complement machine or
>> maybe it needs no optimization at all. Have you actually measured the
>> times x/2 and shift_right(x,2) take?
>
> If I execute this loop:
>
>     to 100 million do
>         c:=a/b
>         c:=a/b
>         c:=a/b
>         c:=a/b
>         c:=a/b
>         c:=a/b
>         c:=a/b
>         c:=a/b
>         c:=a/b
>         c:=a/b
>     od
>
> then when A is an integer variable, and B is a constant 256, it takes
> about 0.5 seconds (using SAR). When B is either a constant 255 or a
> variable containing 256, it takes 20 seconds (using CQO; IDIV).
>
> If I compare dividing by constant 2**60 and constant 2**60-1, then it's
> 0.5 seconds vs 32 seconds.

So the compiler does not optimize expressions like

a/2**b

?

That was my point as a programmer to a compiler designer. Do not mess
with the semantics, it is not your job, it is mine. Fix that lazy
compiler first.

> On which machine is hardware divide faster than shift?

Arguably on every machine with an optimizing compiler.

Optimizing arithmetic into most effective machine instructions (e.g.
shifts if they are faster) is easier to do than doing so for a
hand-written prematurely "optimized" code. There are lots of properties
numeric operations have which the optimizing compiler may rely on. If
you break out of the model, none of that apply anymore. So the code
written in a sane way in accordance with laws of mathematics and common
sense will likely turn to be faster.

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

On 20/06/2021 12:52, Dmitry A. Kazakov wrote:
> On 2021-06-20 12:42, Bart wrote:
>> No. Shift is almost invariably meant as a binary shift.
> Even so, [binary] logical /= arithmetical /= circular.

Esp if, as per other parts of this and previous articles, you
[or the compiler] intend to use "shift" as an optimisation for division
by a power of two. Just another reason why you should do arithmetic on
integer types and logic on "bits" types, and not try to mix the two.

[...]
>> When I had to implement someone's algorithm which involved shifts on big numbers,
> Do not use ill-defined algorithms.

+1.

[...]
>> If I compare dividing by constant 2**60 and constant 2**60-1, then
>> it's 0.5 seconds vs 32 seconds.
> So the compiler does not optimize expressions like
>    a/2**b
> ?
> That was my point as a programmer to a compiler designer. Do not mess
> with the semantics, it is not your job, it is mine. Fix that lazy
> compiler first.

+1. Or perhaps +0.5, because before optimisation comes the
algorithm design and assessment of needs. Most of my programs run
in <1s elapsed time from pressing the button to getting the results
[inc compilation -- you can do a staggering amount of computation
in a second these days]; optimising that to 0.5s or even 0.01s
saves less time than it takes extra to type the flags to compile to
an optimised executable and run the result.

[...]
> Optimizing arithmetic into most effective machine instructions (e.g.
> shifts if they are faster) is easier to do than doing so for a
> hand-written prematurely "optimized" code. [...]

+1, again.

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

On 20/06/2021 12:52, Dmitry A. Kazakov wrote:
> On 2021-06-20 12:42, Bart wrote:
>

>> No. Shift is almost invariably meant as a binary shift.
>
> Even so, [binary] logical /= arithmetical /= circular.

No. As language designer then /I/ get to decide what >> and << mean, and
how they work on different types!

But largely that is in line with other languages do.

The de facto meaning of A<<B is A*(2**B), and of A>>B it is A/(2**B)
using integer divide.

>> I have a decimal number type which uses radix 1,000,000,000. Making
>> A>>B shift a billion at a time is not very useful!
>
> Per definition decimal means radix = 10.

From the user's point of view, it is decimal. It can represent 0.1
exactly for example, and printing large numbers is instant. I can switch
from base-1000000000 to base-10 by changing:

const digitwidth = 9
const digitbase = 1'000'000'000

to:

const digitwidth = 1
const digitbase = 10

It still works, but is at least a magnitude slower, so what's the point?

> Shifting billionary numbers is
> no less useful than having them in first place.
>
>> When I had to implement someone's algorithm which involved shifts on
>> big numbers,
>
> Do not use ill-defined algorithms.

It is not ill-defined once you know what they mean by << and >> (see above).

(This algorithm was for a fast version of the Ackermann function, but
I've lost the main reference and my code. However a version of it in Go
is here:
https://rosettacode.org/wiki/Ackermann_function#Expanded_version_with_arbitrary_precision),
which uses a 'Lsh' method for <<.)

>> If I compare dividing by constant 2**60 and constant 2**60-1, then
>> it's 0.5 seconds vs 32 seconds.
>
> So the compiler does not optimize expressions like
>
>    a/2**b

Huh? I said that in a/b, it will optimise the case where it KNOWS that b
is of the form 2**N. It can then generate code using SAR rather than
IDIV, with results which are 40 times faster in my test.

You were suggesting that hardware division might be faster than hardware
shift.

>> On which machine is hardware divide faster than shift?
>
> Arguably on every machine with an optimizing compiler.

Rubbish. If hardware divide is slower than hardware shift, no
optimisating compiler can make it faster unless:

(1) It turns divide into hardware shift
(2) It eliminates the divide op completely.

> Optimizing arithmetic into most effective machine instructions (e.g.
> shifts if they are faster) is easier to do than doing so for a
> hand-written prematurely "optimized" code. There are lots of properties
> numeric operations have which the optimizing compiler may rely on. If
> you break out of the model, none of that apply anymore. So the code
> written in a sane way in accordance with laws of mathematics and common
> sense will likely turn to be faster.

I think you misunderstood. I'm not manually turning A/B operations into
A>>N where N is some log2 of B. My compiler does that simple optimisation.

On 2021-06-20 15:04, Bart wrote:
> On 20/06/2021 12:52, Dmitry A. Kazakov wrote:
>> On 2021-06-20 12:42, Bart wrote:
>
>>> No. Shift is almost invariably meant as a binary shift.
>>
>> Even so, [binary] logical /= arithmetical /= circular.
>
> No. As language designer then /I/ get to decide what >> and << mean, and
> how they work on different types!

Nope. >> is a lexeme. The semantics of various shifts are defined across
the languages and hardware. You cannot decide. You can only introduce a
bug by using +,-,*,/ for something different.

> The de facto meaning of A<<B is A*(2**B), and of A>>B it is A/(2**B)
> using integer divide.

Nope, it is writing B into the stream A! (:-))

>>> I have a decimal number type which uses radix 1,000,000,000. Making
>>> A>>B shift a billion at a time is not very useful!
>>
>> Per definition decimal means radix = 10.
>
> From the user's point of view, it is decimal. It can represent 0.1
> exactly for example, and printing large numbers is instant.

I do not understand this. See decimal:

https://en.wikipedia.org/wiki/Decimal

Numeral system base = radix.

> It still works,

What works? Are you trying to say that a number can be represented in
any radix. Yes it can. So what?

> but is at least a magnitude slower, so what's the point?

The point is that if you choose machine radix 1000000000 you must live
with the consequences for low-level instructions like machine
representation shifts. Ergo, do not expose low-level instructions in the
language.

>>> When I had to implement someone's algorithm which involved shifts on
>>> big numbers,
>>
>> Do not use ill-defined algorithms.
>
> It is not ill-defined once you know what they mean by << and >> (see
> above).

It is ill-defined because the reader must learn some non-standard
notation for well established things. Use 2**K and everybody will
understand you.

>>> If I compare dividing by constant 2**60 and constant 2**60-1, then
>>> it's 0.5 seconds vs 32 seconds.
>>
>> So the compiler does not optimize expressions like
>>
>>     a/2**b
>
> Huh? I said that in a/b, it will optimise the case where it KNOWS that b
> is of the form 2**N.

Right. How you could replace it with

right_shift (a, b)

otherwise?

>>> On which machine is hardware divide faster than shift?
>>
>> Arguably on every machine with an optimizing compiler.
>
> Rubbish. If hardware divide is slower than hardware shift, no
> optimisating compiler can make it faster unless:
>
> (1) It turns divide into hardware shift
> (2) It eliminates the divide op completely.

(3) The program is longer than single division.

> I think you misunderstood. I'm not manually turning A/B operations into
> A>>N where N is some log2 of B. My compiler does that simple optimisation.

Good, then there is no need to introduce broken numeric shifts anymore.
If the algorithm uses some special form of divisor, let the programmer
hint that in the program. Why do you believe that 2**N is the only such
thing? Why not 5**N or (3**N + 1) etc. Do you have operations for them?
What about

a + 2**N
a * (b + 1)
...

The only reason people are obsessed with 2**N is because it is easy to
implement.

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

On 20/06/2021 14:46, Dmitry A. Kazakov wrote:
> On 2021-06-20 15:04, Bart wrote:

>> From the user's point of view, it is decimal. It can represent 0.1
>> exactly for example, and printing large numbers is instant.
>
> I do not understand this. See decimal:
>
>    https://en.wikipedia.org/wiki/Decimal
>
> Numeral system base = radix.

The reality is that binary numbers are usually treated as groups of 8 or
32 or 64, and calculations are down with those groups.

You can argue that the effective digit size is based on 256 (or 2**64)
rather than 2.

My digits are similarly grouped, except that 1000000000 is implemented
on top of a 32-bit binary value, in the same way that ANY decimal system
has to be implemneted in a binary computer.

>> It still works,
>
> What works?

It still mostly behaves as a decimal representation with the
characteristics expected. Such as calculations that give the same
results as pencil and paper ones.

>> It is not ill-defined once you know what they mean by << and >> (see
>> above).
>
> It is ill-defined because the reader must learn some non-standard
> notation for well established things. Use 2**K and everybody will
> understand you.

** is a rather scary operation that may end up as a call to floating
point pow() in some languages.

It is also not as clear; most people understand what is meant by binary
shifts and they can express their intention better than arithmetic
multiplies and divides, especially if you also write 2**8 instead of 256.

>> (1) It turns divide into hardware shift
>> (2) It eliminates the divide op completely.
>
> (3) The program is longer than single division.

Quite a few programs are dominated by division, because it is so slow.

>> I think you misunderstood. I'm not manually turning A/B operations
>> into A>>N where N is some log2 of B. My compiler does that simple
>> optimisation.
>
> Good, then there is no need to introduce broken numeric shifts anymore.
> If the algorithm uses some special form of divisor, let the programmer
> hint that in the program. Why do you believe that 2**N is the only such
> thing? Why not 5**N or (3**N + 1) etc. Do you have operations for them?
> What about
>
>    a + 2**N
>    a * (b + 1)
>    ...
>
> The only reason people are obsessed with 2**N is because it is easy to
> implement.

That's a pretty good reason. BTW practically all computers are obsessed
with it too.

On 2021-06-20 16:20, Bart wrote:
> On 20/06/2021 14:46, Dmitry A. Kazakov wrote:
>> On 2021-06-20 15:04, Bart wrote:
>
>>> From the user's point of view, it is decimal. It can represent 0.1
>>> exactly for example, and printing large numbers is instant.
>>
>> I do not understand this. See decimal:
>>
>>     https://en.wikipedia.org/wiki/Decimal
>>
>> Numeral system base = radix.
>
> The reality is that binary numbers are usually treated as groups of 8 or
> 32 or 64, and calculations are down with those groups.

Regardless true or not this has nothing to do with decimal numbers. The
calculations are done according to the rules of mathematics, whatever
representation.

> You can argue that the effective digit size is based on 256 (or 2**64)
> rather than 2.

Same, decimal is decimal regardless your point (about circuit design?)

>>> It still works,
>>
>> What works?
>
> It still mostly behaves as a decimal representation with the
> characteristics expected.

Why should a representation be relevant here?

> Such as calculations that give the same
> results as pencil and paper ones.

Yep, shifting by units of 0..10**9-1 is computable with pencil and
paper. What would you expect?

>>> It is not ill-defined once you know what they mean by << and >> (see
>>> above).
>>
>> It is ill-defined because the reader must learn some non-standard
>> notation for well established things. Use 2**K and everybody will
>> understand you.
>
> ** is a rather scary operation that may end up as a call to floating
> point pow() in some languages.

Use a sane language. In Whitespace 2**K is a comment.

> It is also not as clear; most people understand what is meant by binary
> shifts and they can express their intention better than arithmetic
> multiplies and divides, especially if you also write 2**8 instead of 256.

I hope that most people learn something the elementary school...

>> Good, then there is no need to introduce broken numeric shifts
>> anymore. If the algorithm uses some special form of divisor, let the
>> programmer hint that in the program. Why do you believe that 2**N is
>> the only such thing? Why not 5**N or (3**N + 1) etc. Do you have
>> operations for them? What about
>>
>>     a + 2**N
>>     a * (b + 1)
>>     ...
>>
>> The only reason people are obsessed with 2**N is because it is easy to
>> implement.
>
> That's a pretty good reason. BTW practically all computers are obsessed
> with it too.

That reminds me a story about a drunk guy who searched for his lost
watch under the street lamp. When asked why there, he answered, that he
can see better under the lamp.

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

On 19/06/2021 20:34, Rod Pemberton wrote:
> On Fri, 18 Jun 2021 09:12:45 +0100
> James Harris <james.harris.1@gmail.com> wrote:
>
>> 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.)
>>
>
> I see this as an issue of matching the hardware capabilities to the
> demands of the environment.
>
> hardware: central processing unit, microprocessor, floating-point unit
>
> business environment: banking, accounting, brokerage, ...
> academic environment: mathematics, physics, chemistry, engineering, ...
> programming environment: C, Forth, Fortran, COBOL, ...

OK.

>
>> 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.
>
> Have you looked at the specifications for C and FORTH? Or, etc. like
> COBOL and Fortran? I.e., I'd suspect this problem was "solved" decades
> ago with the development of early programming languages.

Sort of. There's a great table of what different languages do at

https://en.wikipedia.org/wiki/Modulo_operation#In_programming_languages

but just look at how inconsistent the choices are!

>
> E.g., a web page on some types of accounting rounding, which some lowly
> programmer will have to figure out how to program:
> https://www.syspro.com/blog/applying-and-operating-erp/rounding-for-accounting-accuracy/
>

That was a really interesting read and I've given it a lot of thought. I
think the rounding methods it mentions are different from the integer
roundings which are the subject of this thread as the roundings in the
article are elective, rare and often unary. As such I think that where
they are needed they could best be effected by functions. For example,

rounded = argentina_rounding(original)

For integer rounding from division, however, it is an unavoidable
consequence of the operation itself, it's a reasonably frequent
operation, and it has two operands rather than one. So I've some up with
a suggestion (in a new thread started just now, qv) of how it might be
realised in a programming language.

--
James Harris