Author: Dieter Buerssner
Date: 12:48:55 09/18/03
Go up one level in this thread
On September 18, 2003 at 13:15:50, Gerd Isenberg wrote:
>hmm, once again
>
> x % 65535 = ( x * 65536 / 65535 ) % 65536
Yes, I meant this (but I used a bit too few parentheses.
>sorry Dieter, i can't follow anymore...
Have you tried the formula? My little interpreter language has only floating
point types, but it will produce correct integer results for basic arithmetics
for integers fitting in 336 bits, when one uses floor() after division. A small
run, that may be self documenting. 10 random integers are created, in a rather
large range, and left and right side of the expression above are evaluated. For
each random integer, 2 lines of output, left and right side. rand01() returns a
number between 0.0 (inclusive) and 1.0 (exclusive). All mantissa bits can be set
(so it will need internally many calls to some 32-bit random number generator)
CALC 5> #rand_i(r) {floor(rand01()*r)}
CALC 6> range=2^256
1.157920892373161954235709850086879078532699846656405640394575840079131E77
CALC 7> a=2^16-1
6.553500000000000000000000000000000000000000000000000000000000000000000E4
CALC 8> a1=a+1
6.553600000000000000000000000000000000000000000000000000000000000000000E4
CALC 9> for({i=0},{i<10},{i++}){x=rand_i(range); fmod(x,a); val; fmod(floor(a1*x
/a),a1); val}
3.662400000000000000000000000000000000000000000000000000000000000000000E4
3.662400000000000000000000000000000000000000000000000000000000000000000E4
1.805600000000000000000000000000000000000000000000000000000000000000000E4
1.805600000000000000000000000000000000000000000000000000000000000000000E4
4.700000000000000000000000000000000000000000000000000000000000000000000E1
4.700000000000000000000000000000000000000000000000000000000000000000000E1
3.144900000000000000000000000000000000000000000000000000000000000000000E4
3.144900000000000000000000000000000000000000000000000000000000000000000E4
6.044900000000000000000000000000000000000000000000000000000000000000000E4
6.044900000000000000000000000000000000000000000000000000000000000000000E4
4.930700000000000000000000000000000000000000000000000000000000000000000E4
4.930700000000000000000000000000000000000000000000000000000000000000000E4
3.870800000000000000000000000000000000000000000000000000000000000000000E4
3.870800000000000000000000000000000000000000000000000000000000000000000E4
2.168500000000000000000000000000000000000000000000000000000000000000000E4
2.168500000000000000000000000000000000000000000000000000000000000000000E4
3.138000000000000000000000000000000000000000000000000000000000000000000E3
3.138000000000000000000000000000000000000000000000000000000000000000000E3
6.099600000000000000000000000000000000000000000000000000000000000000000E4
6.099600000000000000000000000000000000000000000000000000000000000000000E4
All are the same. It is no proof of course.
This will work only (IIRC) for %(2**k-1). Don't ask me to explain it, please :-)
BTW. The same code will work reliably with normal C compilers (when the synthax
is adjusted) on IEEE floating point environments, and when the range is
adjusted. So, for the typical double format, with 53 bit mantissa, it should
work for numbers up to 2**(53-16) (To not overflow the exact integer range of
the floating point format after the multiplication). The IEEE floating point
standard gives the implementation no freedom for non accurate rounding. Even
when the actual bit for the rounding decision is 50 bits later, than the
precision, you will get a reliable result.
Regards,
Dieter
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.