20170608, 19:18  #1 
Einyen
Dec 2003
Denmark
5·11·61 Posts 
mulmod failing
I thought I used this well known mulmod code in quite a few programs, so I would have noticed this before: It seems to fail when a and b are large and c is small in "a*b (mod c)". By failing I mean the program is stuck in this function or it takes a very long time compared to what it should.
For example a=245673636173; b=245673636173; and c=2047; and it also "fail" when a!=b. I thought I did a lot of tests previously with many different values a,b,c < 2^64; Code:
uint64_t mulmod(uint64_t a, uint64_t b, uint64_t c) { uint64_t d; /* to hold the result of a*b mod c */ /* calculates a*b mod c, stores result in d */ asm ("mov %1, %%rax;" /* put a into rax */ "mul %2;" /* mul a*b > rdx:rax */ "div %3;" /* (a*b)/c > quot in rax remainder in rdx */ "mov %%rdx, %0;" /* store result in d */ :"=r"(d) /* output */ :"r"(a), "r"(b), "r"(c) /* input */ :"%rax", "%rdx" /* clobbered registers */ ); return d; } 
20170608, 20:03  #2 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
909_{10} Posts 
In my code I have this comment:
Code:
/* GCC on a 64bit Intel x86, help from WraithX and Wojciech Izykowski */ /* Beware: if (a*b)/c > 2^64, there will be an FP exception */ static inline uint64_t _mulmod(uint64_t a, uint64_t b, uint64_t n) { uint64_t d, dummy; /* d will get a*b mod c */ asm ("mulq %3\n\t" /* mul a*b > rdx:rax */ "divq %4\n\t" /* (a*b)/c > quot in rax remainder in rdx */ :"=a"(dummy), "=&d"(d) /* output */ :"a"(a), "rm"(b), "rm"(n) /* input */ :"cc" /* mulq and divq can set conditions */ ); return d; } 
20170608, 20:07  #3 
"Mark"
Apr 2003
Between here and the
41×163 Posts 
It is safest to compute a%c and b%c first. Yes, it is slower, but in the code I work with I typically need the value of a%c and b%c.

20170608, 20:14  #4 
Einyen
Dec 2003
Denmark
6433_{8} Posts 
Thank you. You are both correct. I found my example was working when I lowered a down below the limit a*a/2047 < 2^64.
What got me confused was, that I was sure I had tested mulmod with random values up to 2^64 for all 3 variables. But now I found that old test code, and I actually did a%c and b%c before mulmod back then, and I completely forgot Last fiddled with by ATH on 20170608 at 20:15 
20170608, 22:22  #5 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
6,563 Posts 
With the values you gave your code should crash with a dividebyzero* exception. Unless the calling code has installed an exception handler or something.
Any time the high order word is larger or equal than the divisor the result from div can't fit into a single register. 245,673,636,173 x 245,673,636,173 = 60,355,535,510,463,574,085,929 60,355,535,510,463,574,085,929 / 2,047 = 29,484,873,234,227,442,152 & 785 remainder Note that 29,484,873,234,227,442,152 cannot fit into a single 64bit register. This can also be detected by observing that the high order word of 60,355,535,510,463,574,085,929 is 3,271. So even before the divide is done we can know that it will fail because 3,271 >= 2,047. * Even though the divisor is not actually zero you will still get the dividebyzero exception whenever the result is too large. Last fiddled with by retina on 20170608 at 22:23 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
MISFIT uploads failing to PrimeNet  Chuck  PrimeNet  21  20140206 15:56 
Worker 1 Keeps failing  zenzu88  Software  2  20120410 15:16 
Tried out aliqueit.exe: ggnfs failing  Greebley  Aliquot Sequences  35  20100213 15:23 
torture test failing in 1 minute  ghatothkach  Hardware  5  20050114 09:50 
Failing Torture Test..  jugbugs  Hardware  12  20040325 02:37 