I have little bit different question about dividing by constant (Yes,
I have read Agners manual about optimization but I obviously have
missed something). I want to calculate;
 x mod 25 (and also x mod 31, 41, and 61). Difference here is that x
is 96-bit integer. I have tried to use division by constant trick, but
I have misunderstood something. I have few questions. 
I have tried following:
divisor: 25 == 11001b
b = (the number of significant bits in divisor) - 1 = 4
r = 32 + b = 36
f = 2^r / divisor = 2^36 / 25 = 2748779069.44000
 fractional part of f is < 0.5   
=> f == 2748779069
result = ((x+1)*f) SHR r
I have used 96-bit multiplication and right shift.
Should I use f = 2^100 / 25 == 50706024009129176059868128215.04
=> 50706024009129176059868128215 instead of 2748779069 ?

I also started to think that because I want only residual so may be it
is possible to calculate only last 32-bits of (quotient * 25) and
subtract this from last 32-bits of x (this should work when last
32-bits of x is not zero?). If this result is negative then I can take
abs from result?

Any comments or hints how to calculate fast modulus by constant from
96 or 128-bit long integer ?

Yours,

Nuutti

Nuutti Kuosa wrote:

> I have little bit different question about dividing by constant (Yes,
> I have read Agners manual about optimization but I obviously have
> missed something). I want to calculate;
>  x mod 25 (and also x mod 31, 41, and 61). Difference here is that x
> is 96-bit integer. I have tried to use division by constant trick, but

This is a _lot_ tougher!

(Except for 31, which is a special case)

You can calculate the remainder of arbitrarily long integers using 
repeated division, but for reciprocal multipication you need both a very 
  long reciprocal, and then an equally long back-multiplication and 
subtraction.

For small divisors like yours, it might be feasible to do the job in 
multiple steps, handling 3 bytes per iteration:

   top = top3bytes(); // Grab the top as a 24-bit unsigned value
   res = top / 25;
// Implemented as reciprocal multiplication by the compiler!
   remainder = top - res * 25;

   top = (remainder << 24) + top3bytes(); Grab the next 24 bits!
.... Repeat the previous code!

For a mod 31 operation, you can simply add together all 5-bit elements 
from the input string. :-)

Repeat until the result is small enough.

Terje

-- 
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"

Thanks. That helped a lot because I had all kind of strange ideas
about this modulo arithmetic. Probably because my example number was
25 and it is special number in the 10-base system. Splitting number to
four 3-byte part is a great idea.

I actually found even more helpful post later from
board.win32asmcommunity.net
and now I know how to implement residual calculation very fast.

Here are few basic facts about modulo arithmetic:

(a+b) mod y = ( (a mod y) + (b mod y) ) mod y
and
(a*b) mod y =  ( (a mod y) * (b mod y) ) mod y

Then we have 96-bit integer (12 bytes) x:
aaabbbcccddd
We want to calculate x mod 25.
x == aaa*2^72 + bbb*2^48 + ccc*2^24 + ddd
=>
 x mod 25 == 
( (aaa*2^72) mod 25 + ( bbb*2^48) mod 25 + (ccc*2^24) mod 25 + ddd )
mod 25
== (21*aaa + 6*bbb + 16*ccc+ ddd) mod 25

because:
2^24 mod 25 == 16
2^48 mod 25 == 6
2^72 mod 25 == 21

after that we can use division by constant trick to calculate modulo
because we have 32-bit integer.

about modulo 31 and summing digits. It works because:
(2^5) mod 31 = 1
but this is also true to many other numbers:
(2^20) mod 25== 1
(2^5)  mod 31 == (2^10) mod 31==(2^15) mod 31==(2^20) mod 31== 1 
(2^20) mod 41== 1 
(2^60) mod 61== 1 (too big for 32-bit cpu)
so we can also calculate modulo respect to 25 summing 20-bit
numbers and taking modulo after that,

Here is original post to the bulleting board (64-bit case):

Instead of cutting the number in 32 bits, and compute:
N=a * 2^32 + b
(((a * 2^32) mod 7) * 2^32 + b) mod 7
2 divisions

I can cut it in 16 bits, and compute as follows:
N=a*2^48 + b*2^32 + c*2^16 + d
((a) + (b * 4) + (c * 2) + (d)) mod 7
1 division !
since
2^48 mod 7 = 1
2^32 mod 7 = 4
2^16 mod 7 = 2


I know a lot more now than a week ago :-)

Nuutti

Nuutti Kuosa wrote:
> Here are few basic facts about modulo arithmetic:
> 
> (a+b) mod y = ( (a mod y) + (b mod y) ) mod y
> and
> (a*b) mod y =  ( (a mod y) * (b mod y) ) mod y
> 
> Then we have 96-bit integer (12 bytes) x:
> aaabbbcccddd
> We want to calculate x mod 25.
> x == aaa*2^72 + bbb*2^48 + ccc*2^24 + ddd
> =>
>  x mod 25 == 
> ( (aaa*2^72) mod 25 + ( bbb*2^48) mod 25 + (ccc*2^24) mod 25 + ddd )
> mod 25
> == (21*aaa + 6*bbb + 16*ccc+ ddd) mod 25
> 
> because:
> 2^24 mod 25 == 16
> 2^48 mod 25 == 6
> 2^72 mod 25 == 21

Nice, I had forgotten about being able to simplify the modulo operations!

Terje

-- 
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"