(a * b) mod c with int64

[BeniBela]

Is there a function to calculate (a*b) mod c, when a,b,c are int64?

The result fits nicely in a int64, but the a*b calculation overflows

[Blaazen]

Can you use some workaround, like:
var a, b, c: Extended;

Result:=trunc(a*(b/c));

where Result is int64.

Integer part of Extended is ~62bits.

Also, here was some threads about 128-bit integers in past, so try search the forum.

[BeniBela]

Can you use some workaround, like:
var a, b, c: Extended;

Result:=trunc(a*(b/c));

I need an exact 50-bit remainder, so i think the intermediate result needs at least 100 bit and  extended is too unprecise

Also, here was some threads about 128-bit integers in past, so try search the forum.

I searched before, but didn't find anything

[circular]

Maybe you can find some bigint library.

[Laksen]

The only way to do that is probably to disable range and overflow detection in that part of the code. Sort of something like this:

Code: [Select]

   {$PUSH}
   {$Q-}
   writeln((a*b) mod c);
   {$POP}


[circular]

Yes but no, the result will no be correct if a*b is bigger than max int64 value.

[BeniBela]

Maybe you can find some bigint library.

I think that is overkill for just one 128 bit multiplication/modulo.

[Blaazen]

There are many links in this thread: http://www.lazarus.freepascal.org/index.php/topic,9375.msg45964.html#msg45964

[Martin_fr]

Bit late, but if I am not mistaken:

Well if you first take the modulo of  "a mod c"

d = a div c
m = a mod c

a = d * c + m
(a*b) =  d*b * c + m*b

To get the modulo of "(a*b) mod c" you can also say you wan the modulo of
   ( d*b*c + m*b ) mod c
since
  d*b*c
is dividable by c (c is a factor), you are looking for
   (m*b ) mod c
and since "m = a mod c", that means you need

  ((a mod c) * b) mod c

of course that can still overflow.

But since the above shows that
   m2 = (a*b) mod c
can be replaced by
  m2 = ((a mod c) * b) mod c

of course, instead of a, we could have replaced b. Lets replace b, the same way in
  m2 = ((a mod c) * b) mod c

and we get
  m = ((a mod c) * (b mod c)) mod c

It can still overflow. But maybe it is enough in your case

[BeniBela]

There are many links in this thread: http://www.lazarus.freepascal.org/index.php/topic,9375.msg45964.html#msg45964

Oh, there it is.

But still, I don't want to use a new library for such a simple division

and we get
  m = ((a mod c) * (b mod c)) mod c

It can still overflow. But maybe it is enough in your case

No, c is around 10**50




Now I have looked in the amd64 instruction manual, and it turned out that a 64 bit processor always calculates multiplication/division with 128 bit, so in assembler it is no problem.

Code: [Select]


//result := (a * b) mod m
function intMulMod64(a_rdi,b_rsi,m_rdx: int64): int64; assembler; nostackframe; inline;
asm
  mov rax, a_rdi
  mov rcx, m_rdx
  mul b_rsi
  div rcx
  mov rax, rdx
end;


But it would be nice to have a platform independent way


[edit]: and is there are way to change the calling convention to have the first parameter in eax and the last one not in edx?

[Laksen]

But it would be nice to have a platform independent way

Doesn't this work?

Code: [Select]

function intMulMod64(a,b,c: int64): int64;
begin
   {$PUSH}
   {$Q-}
   result := (a*b) mod c;
   {$POP}
end


[BeniBela]

But it would be nice to have a platform independent way

Doesn't this work?

Code: [Select]

function intMulMod64(a,b,c: int64): int64;
begin
   {$PUSH}
   {$Q-}
   result := (a*b) mod c;
   {$POP}
end


No, it becomes

Code: [Select]

...
000000000040024C 480fafc2                 imul   %rdx,%rax
0000000000400250 4899                     cqto   
0000000000400252 48f77de8                 idivq  -0x18(%rbp)
...

and cqto kills the register with the higher 64-bit word

[circular]

Maybe you can find some bigint library.

I think that is overkill for just one 128 bit multiplication/modulo.

Well if there is no other way. You cannot rely on pure asm if you want it to be cross platform.

[marcov]

Well if there is no other way. You cannot rely on pure asm if you want it to be cross platform.

Stronger even, while (some?) CPUs might support int128 in 64-bit mode, most architectures don't.

[KpjComp]

But it would be nice to have a platform independent way

Is speed important?

As one way would be to roll your own binary multiple / divide without ASM, it would involve a fair bit of Bit Anding and Bit shifting, but it would be possible to code totally in Pascal.  One advantage here is that you could have as many bit's as you wish.   4096bit multiply anyone.