One of the new features in .NET 4.0 is the BigInteger class. This was suppose to be part of 3.5 framework, but after the CTP it was gone. Now it’s back. This big integer is a really large integer representation. However, I was not able to find the precision documented anywhere.
The class is available in the System.Numerics namespace and provides overloaded operators, parsing methods and other utility features for bit integer numbers.
Not very long ago, on codexpert.ro we launched a contest for finding the biggest pair of amicable numbers. One of the members (crystyce) that submited a solution found this big pair (2724918040393706557785752240819405848576, 2724918040396184856306258038787235905536) with a C++ implementation using a 3rd party BigInt class. I decided to put that in C# 4.0 and use BigInteger. Maybe you can find things to optimize in the below code, but that’s not the point here. I’m showing you this code just to get a feeling of BitInteger.
using System.Numerics;
namespace cs_test
{
static class Amicable
{
public static BigInteger Pow2(BigInteger exp)
{
BigInteger res = 1;
for (BigInteger i = 0; i < exp; i++)
res *= 2;
return res;
}
public static BigInteger ExpMod(BigInteger value, BigInteger exp, BigInteger mod)
{
BigInteger ullResult = 1;
BigInteger ullValue = value;
while (exp > 0)
{
if (exp % 2 != 0)
{ // odd
ullResult *= ullValue;
ullResult %= mod;
}
ullValue *= ullValue;
ullValue %= mod;
exp /= 2;
}
return (ullResult);
}
static public bool IsMillerRabinPrime(BigInteger prime)
{
// randomWitness = witness that the "prime" is NOT composite
// 1 < randomWitness < prime-1
long totalWitness = 15;
BigInteger [] randomWitness = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51001, 351011};
BigInteger primeMinusOne = prime - 1;
BigInteger oddMultiplier;
long bitLength;
long i, j;
BigInteger result;
// find oddMultiplier, defined as "prime - 1 = (2^B) * M"
// get bitLength (B) and find the oddMultiplier (M)
// init value multiplier
oddMultiplier = primeMinusOne;
bitLength = 0; // reset
while(oddMultiplier % 2 == 0)
{
oddMultiplier /= 2;
bitLength++;
}
for(i = 0; i < totalWitness; i++)
{
if (randomWitness[i] == prime)
return true;
// init value of result = (randomWitness ^ oddMultiplier) mod prime
result = ExpMod(randomWitness[i], oddMultiplier, prime);
// is y = 1 ?
if(result == 1)
continue; // maybe prime
// is y = prime-1 ?
if(result == primeMinusOne)
continue; // maybe prime
// loop to get AT LEAST one "result = primeMinusOne"
for(j = 1; j <= bitLength; j++)
{
// square of result
result = ExpMod(result, 2, prime);
// is result = primeMinusOne ?
if(result == primeMinusOne)
break; // maybe prime
}
if(result != primeMinusOne)
return false; // COMPOSITE
}
// it may be pseudoprime/prime
return true;
}
}
class Program
{
const int STARTM = 1;
const int STOPM = 100;
const int STOPN = 30;
static void Main(string[] args)
{
DateTime start = DateTime.Now;
for (BigInteger m = STARTM ; m <= STOPM ; m++)
{
for (BigInteger n = m+1 ; n <= m+STOPN ; n++)
{
BigInteger p = Amicable.Pow2(n) + Amicable.Pow2(m) - 1;
if (!Amicable.IsMillerRabinPrime(p)) continue;
BigInteger q = Amicable.Pow2(2 * n - m) + Amicable.Pow2(n) - 1;
if (!Amicable.IsMillerRabinPrime(q)) continue;
BigInteger r = Amicable.Pow2(3 * n - m) +
Amicable.Pow2(n + m) +
Amicable.Pow2(2 * n + 1) - 1;
if (!Amicable.IsMillerRabinPrime(r)) continue;
BigInteger f1 = Amicable.Pow2(n) * p * q;
BigInteger f2 = Amicable.Pow2(n) * r;
DateTime end = DateTime.Now;
Console.WriteLine(
"{2} ... {0}, {1}",
f1,
f2,
(end - start).Milliseconds / 1000.0);
}
}
}
}
}
0.017 ... 220, 284
0.021 ... 2172649216, 2181168896
0.028 ... 17296, 18416
0.040 ... 9363584, 9437056
0.138 ... 2.7249180403937065577857522408E+39, 2.7249180403961848563062580388E+39
As you can see, it was very fast finding the same big pair. Well it was at least on my 2 core machine.
The only thing I don't understand about the implementation is the presence of some helper functions in the BigInteger class.
public static BigInteger Abs(BigInteger value);
public static BigInteger Add(BigInteger left, BigInteger right);
public static BigInteger GreatestCommonDivisor(BigInteger left, BigInteger right);
public static BigInteger Divide(BigInteger dividend, BigInteger divisor);
public static BigInteger DivRem(BigInteger dividend, BigInteger divisor, out BigInteger remainder);
public static double Log(BigInteger value);
public static double Log(BigInteger value, double baseValue);
public static double Log10(BigInteger value);
public static BigInteger Max(BigInteger left, BigInteger right);
public static BigInteger Min(BigInteger left, BigInteger right);
public static BigInteger ModPow(BigInteger value, BigInteger exponent, BigInteger modulus);
public static BigInteger Multiply(BigInteger left, BigInteger right);
public static BigInteger Negate(BigInteger value);
public static BigInteger Pow(BigInteger value, int exponent);
public static BigInteger Remainder(BigInteger dividend, BigInteger divisor);
public static BigInteger Subtract(BigInteger left, BigInteger right);
That belongs to System.Math, or maybe to a System.Numerics.Math class. They are all helper functions, not specific to the implementation of the big integer; and the implementation does not depend on the existing of these functions. So they are clearly utility functions. They should go somewhere else. I have submitted this as feedback to Microsoft Connect. If you agree with it, vote for it here. Of course, if you have arguments for the current implementation, you can vote against it too.
C++, integer, numerics, VS2010 Hits for this post: 11481 .
