tags:

views:

3519

answers:

4

To use modular exponentiation as you would require when using the Fermat Primality Test with large numbers (100,000+), it calls for some very large calculations.

When I multiply two large numbers (eg: 62574 and 62574) PHP seems to cast the result to a float. Getting the modulus value of that returns strange values.

$x = 62574 * 62574;
var_dump($x);          // float(3915505476) ... correct
var_dump($x % 104659); // int(-72945)  ... wtf.

Is there any way to make PHP perform these calculations properly? Alternatively, is there another method for finding modulus values that would work for large numbers?

+1  A: 

I suggest you try BigInteger. If that doesn't work out, you may use SWIG to add C/C++ code for the big integer calculations and link it into your code.

Yuval F
+5  A: 

have you taken a look at bcmod()? php has issues with integers over 2^31

var_dump(bcmod("$x", '104659') ); // string(4) "2968"
Owen
er... on 32 bit platforms
Owen
+8  A: 

For some reason, there are two standard libraries in PHP handling the arbitrary length/precision numbers: BC Math and GMP. I personally prefer GMP, as it's fresher and has richer API.

Based on GMP I've implemented Decimal2 class for storing and processing currency amounts (like USD 100.25). A lot of mod calculations there w/o any problems. Tested with very large numbers.

Ivan Krechetov
A: 

Have you ever tried

bcmod(1440061624670807917708947644440855655647248331950114572760004491041044469861865427091855283373146954236633117246745937752162594055383906634366657266450432,16);

It returns 0

So bcmod doesn't work with large numbers either

john
ca2.php.net/manual/en/function.bcmod.php, look at the signature, you should be passing a STRING, string bcmod ( string $left_operand , string $modulus ). PHP will parse your bugnum to an integer directly thus losing its bignum property.
tomzx
I'm loving how this is rendered in my browser though ;)
bobwah