> Can you show us the optimized Nim code too...
Sure. I left it out because the post was already long.
let
m2 = 10
m1 = 3*m2
b1 = 127
b2 = 256
mul = 102
a1 = 101
a2 = 7
a = (a1 shl m1) + a2
b = (b1 shl m1) + b2
echo a1, " ", a2
echo b1, " ", b2
echo a div (1 shl m1), " ", a mod (1 shl m1)
echo b div (1 shl m1), " ", b mod (1 shl m1)
echo "max in segment: ", (1 shl m1) - 1
echo "work modulo: ", (1 shl m2)
echo "basic number: ", a
echo "multiplier: ", mul
echo "adding: ", (mul*b) div (1 shl m1), " ", (mul*b) mod (1 shl m1)
var c = a
let mask = (1 shl (2*m1 - 1)) + (1 shl (m1 - 1))
let stop = 1000000000
for each in 1..stop:
c += mul*b
let overflow = c and mask
if overflow != 0:
let r1 = (c div (1 shl m1)) mod (1 shl m2)
let r2 = (c mod (1 shl m1)) mod (1 shl m2)
c = (r1 shl m1) + r2
echo (c div (1 shl m1)) mod (1 shl m2), " ", (c mod (1 shl m1)) mod (1 shl
m2)
Run
In case you want it, here's the optimized C code.
#include <stdlib.h>
#include <stdio.h>
int main() {
long long m2 = 10;
long long m1 = 3*m2;
long long b1 = 127;
long long b2 = 256;
long long mul = 102;
long long a1 = 101;
long long a2 = 7;
long long a = (a1 << m1) + a2;
long long b = (b1 << m1) + b2;
long long c = a;
long long mask = (((long long )1) << (2*m1 - 1)) + (((long long )1) <<
(m1 - 1));
for (long i = 0; i < 1000000000; ++i) {
c += mul*b;
long long overflow = c & mask;
if (overflow != 0) {
long long r1 = (c / (1 << m1)) % (1 << m2);
long long r2 = (c % (1 << m1)) % (1 << m2);
c = (r1 << m1) + r2;
}
}
printf("%lld %lld\n", (c / (1 << m1)) % (1 << m2), (c % (1 << m1)) % (1
<< m2));
}
Run
