0

I am writing an algorithm that uses successive squaring to solve a^k mod m. Because of the way successive squaring works, the maximum number that the algorithm will ever have to compute is 2147483646^2 (I limited the user input to 214738364). Unfortunately, it still has to compute this. It seems to get the squaring part right, and then turns the overflowing number into a float, but then can't compute the modulus of a float and an integer.

A sample line is:

3422422^2 mod 715924 = 661224^2 mod 715924 = 437217178176 mod 715924 = -354280

How can I fix this, and how does one find one's way around integer overflow in PHP?

Andrew Latham
  • 5,982
  • 14
  • 47
  • 87
  • How can you fix what? That floating-point/integral mod isn't available? – Lightness Races in Orbit Jan 07 '12 at 17:37
  • Well, obviously a modulo isn't going to return a negative number, yet that is what's occurring here. Is there a special PHP function for the modulus of a float and an integer? – Andrew Latham Jan 07 '12 at 17:39
  • [What's wrong with modulus returning a negative number?](http://codepad.org/TwoMrkOR) I don't think floating-point has anything to do with it; it's just an overflowed integer. – Lightness Races in Orbit Jan 07 '12 at 17:42
  • Sorry, I meant the modulus of two positive integers won't return a negative number, as in the example I showed. So what's happening here? I thought that as soon as an integer overflowed in PHP, its type was changed to a floating point number. So after 661224^2 overflow, 4372178176 becomes a float, and then it's trying to compute the modulus of a positive float and a positive integer. – Andrew Latham Jan 07 '12 at 17:47
  • I see. I can neither confirm nor deny that, but I'd be surprised. And I certainly wouldn't expect floating-vs-int mod to randomly give you a negative number. – Lightness Races in Orbit Jan 07 '12 at 17:48
  • [Seems you're right!](http://php.net/manual/en/language.types.integer.php) Then I have no idea what's going on here :) – Lightness Races in Orbit Jan 07 '12 at 17:49
  • Ah, perhaps the operand is getting converted to `int`. And then, from the manual: `If the float is beyond the boundaries of integer (usually +/- 2.15e+9 = 2^31 on 32-bit platforms and +/- 9.22e+18 = 2^63 on 64-bit platforms), the result is undefined, since the float doesn't have enough precision to give an exact integer result. No warning, not even a notice will be issued when this happens!` Really, trying to deal with huge values like this with primitives is a fool's errand. At _best_ you're going to have terrible precision and useless results. – Lightness Races in Orbit Jan 07 '12 at 17:49
  • 1
    I doubt that's easy to reimplement with a productive runtime behaviour (you'd need to work on strings and simulate integer arithmentic). Which is why [`bcpowmod()`](http://php.net/bcpowmod) exists. – mario Jan 07 '12 at 17:49
  • That bcpowmod() worked like a charm, you should post it as an answer! Two questions though. First, if the result is undefined, why is the correct answer showing up? And second, am I just going to have to find creative workarounds for integer overflow like that one, or is there one concrete way to go around it? Because another algorithm I'm working on solves linear congruences, but it often overflows by multiplying two large integers together. i.e. 2291255x = 47 mod 3106907 Multiply by 1882971. 4314366718605x = 88499637 mod 3106907 Cast out 3106907s -3106906x = 1506241 mod 3106907 – Andrew Latham Jan 07 '12 at 17:57

1 Answers1

1

I would suggest checking out the GMP extension and reading this question.

Community
  • 1
  • 1
hackartist
  • 5,172
  • 4
  • 33
  • 48