Division vs DIV - Valentin's findings

[EdS2]

I feel this observation is worth a discussion, from over on the latest Pi Day offering:

(03-29-2023 01:16 AM)Valentin Albillo Wrote:  Indeed IP(T/(K*K)) and T DIV (K*K), which would appear at first sight to be equivalent, do really differ at times (though very rarely and for large values of T, it seems,) when the former's rounding does not match the latter's truncation.

A trivial program I wrote (relatively) quickly finds all mismatches for various very large integer T and for K from 2 to IP(√T) (i.e. ~ one million possible cases for the first eight values of T listed):

      T              # Mismatches            K
-----------------------------------------------------------
999,999,999,999      31 instances      2, 5, 8, 16, 20, ...
999,999,999,998      19 instances      2, 3, 8, 20, 25, ...
999,999,999,997      12 instances      3, 8, 25, 80, ...
999,999,999,996       3 instances      3, 3125, 31250, ...
999,999,999,995       3 instances      2, 3, 254
999,999,999,994       1 instance       254
999,999,999,993       1 instance       254
999,999,999,992       0 instances       -
 99,999,999,999       0 instances       -

As you can see, for T = 999,999,999,999 there are 31 different instances (in about a million) where IP(T/(K*K)) differs from T DIV (K*K), for K ranging from 1 to IP(√T). The instances begin at K = 2 (249,999,999,999 vs. 250,000,000,000, respectively) and end at K = 500,000 (3 vs. 4, respectively).

Doing the same with T = 999,999,999,998, there's just 19 instances reported instead of 31, and with T = 999,999,999,997 just 12. By the time T equals 999,999,999,995, a mere 3 faulty instances remain (namely for K = 2, 3 and 254), then 999,999,999,994 and 999,999,999,993 have just the one mismatch (in a million !) and for 999,999,999,992 and below there seems to be none.

Also, as expected, running this small program for input values with less than 12 digits, say T = 99,999,999,999 instead, i.e. 1E11 - 1, no instances of mismatches appear at all, and probably the same happens for all smaller T.

I find myself caught in a superposition of states: a lack of surprise that sometimes division will round upwards, and a great surprise that this rounding happens so very rarely in this experiment.

Checking a few of the examples, it seems that division on this 12 digit calculation will round upwards if the 13th digit would be 5 or greater. Is it obvious as to why this should happen so rarely - am I missing something?

Why these particular divisors, and why should divisors come and go as we traverse the table? Is there pattern here which I'm not seeing?

[J-F Garnier]

These cases are not rare at all, as soon as the dividend is >1E11 such as (4E11+7)/4 --> 10000000002 that clearly illustrates what is happening.
Although I don't have a rigorous reasoning, I don't believe the problem can occur with dividend X<1E11, so IP(X/Y) is then safe for integer division.
This is not specific to the 71B or Saturn machines, it happens as well on the 10-digit 41C and 34-digit Free42 with the 1E9 and 1E33 limits, respectively.

Rule of the thumb: pay attention to integer divisions when the dividend is less than a factor of 10 from the maximum integer.

J-F

[EdS2]

Mmm, but... if what we had was a rounding from a 13th digit, wouldn't we see it about half of the time? We see it rarely, and I think we don't believe there is a 13th digit, so there's something about the mechanics of division here which is, I think, a bit surprising.

(These are decimal calculations... division proceeds by shift and subtract? Is there an estimating of the next digit?)