Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
BigInteger ExtensionMethods
public static class BigIntegerExtensionMethods
{
public static BigInteger Sum(this IEnumerable<BigInteger> source)
{
return source.Aggregate((accumulator, current) => accumulator + current);
}
public static BigInteger Product(this IEnumerable<BigInteger> source)
{
return source.Aggregate((accumulator, current) => accumulator * current);
}
public static BigInteger Mod(this BigInteger source, BigInteger mod)
{
BigInteger r = (source >= mod) ? source % mod : source;
return (r < 0) ? BigInteger.Add(r, mod) : r.Clone();
}
public static BigInteger NthRoot(this BigInteger source, int root)
{
BigInteger remainder = new BigInteger();
return source.NthRoot(root, out remainder);
}
public static BigInteger NthRoot(this BigInteger source, int root, out BigInteger remainder)
{
if (root < 1) throw new Exception("Root must be greater than or equal to 1");
if (source.Sign == -1) throw new Exception("Value must be a positive integer");
remainder = 0;
if (source == BigInteger.One) { return BigInteger.One; }
if (source == BigInteger.Zero) { return BigInteger.Zero; }
if (root == 1) { return source; }
BigInteger upperbound = source.Clone();
BigInteger lowerbound = BigInteger.Zero;
while (true)
{
BigInteger nval = (upperbound + lowerbound) >> 1;
BigInteger testPow = BigInteger.Pow(nval, root);
if (testPow > source) upperbound = nval;
if (testPow < source) lowerbound = nval;
if (testPow == source)
{
lowerbound = nval;
break;
}
if (lowerbound == upperbound - 1) break;
}
remainder = source - BigInteger.Pow(lowerbound, root);
return lowerbound;
}
public static bool IsSquare(this BigInteger source)
{
if (source == null || source == BigInteger.Zero)
{
return false;
}
BigInteger input = BigInteger.Abs(source);
int base16 = (int)(input & Fifteen); // Convert to base 16 number
if (base16 > 9)
{
return false; // return immediately in 6 cases out of 16.
}
// Squares in base 16 end in 0, 1, 4, or 9
if (base16 != 2 && base16 != 3 && base16 != 5 && base16 != 6 && base16 != 7 && base16 != 8)
{
BigInteger remainder = new BigInteger();
BigInteger sqrt = input.NthRoot(2, out remainder);
return (remainder == 0);
// - OR -
//return (sqrt.Square() == input);
}
return false;
}
private static BigInteger Fifteen = new BigInteger(15);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment