Skip to content

Instantly share code, notes, and snippets.

@mjs3339
Created March 2, 2019 16:34
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mjs3339/f32dc46163095d4e3ddff5f4df7de01b to your computer and use it in GitHub Desktop.
Save mjs3339/f32dc46163095d4e3ddff5f4df7de01b to your computer and use it in GitHub Desktop.
C# BigInteger Extension Class
public static class BigIntegerEx
{
private static readonly BigInteger Ten = new BigInteger(10);
private static readonly BigInteger Three = new BigInteger(3);
public static BigInteger ToBigInteger(this char ul)
{
return new BigInteger(ul);
}
public static BigInteger ToBigInteger(this byte ul)
{
return new BigInteger(ul);
}
public static BigInteger ToBigInteger(this sbyte ul)
{
return new BigInteger(ul);
}
public static BigInteger ToBigInteger(this short ul)
{
return new BigInteger(ul);
}
public static BigInteger ToBigInteger(this ushort ul)
{
return new BigInteger(ul);
}
public static BigInteger ToBigInteger(this int ul)
{
return new BigInteger((ulong) ul);
}
public static BigInteger ToBigInteger(this uint ul)
{
return new BigInteger((ulong) ul);
}
public static BigInteger ToBigInteger(this long ul)
{
return new BigInteger((ulong) ul);
}
public static BigInteger ToBigInteger(this ulong ul)
{
return new BigInteger(ul);
}
public static BigInteger Sqrt(this BigInteger n)
{
var q = BigInteger.One << ((int) BigInteger.Log(n, 2) >> 1);
var m = BigInteger.Zero;
while(BigInteger.Abs(q - m) >= 1)
{
m = q;
q = (m + n / m) >> 1;
}
return q;
}
public static List<BigInteger> GetFactors(this BigInteger n)
{
var Factors = new List<BigInteger>();
var s = n.Sqrt();
var a = Three;
while(a < s)
{
if(n % a == 0)
{
Factors.Add(a);
if(a * a != n)
Factors.Add(n / a);
}
a += 2;
}
return Factors;
}
/// <summary>
/// https://en.wikipedia.org/wiki/Greatest_common_divisor
/// </summary>
public static BigInteger Gcd(this BigInteger a, BigInteger b)
{
while(b > BigInteger.Zero)
{
var r = a % b;
a = b;
b = r;
}
return a;
}
/// <summary>
/// https://en.wikipedia.org/wiki/Least_common_multiple
/// </summary>
public static BigInteger Lcm(this BigInteger a, BigInteger b)
{
return a * b / a.Gcd(b);
}
public static BigInteger BigIntegerBase2(this BigInteger bi, string binaryValue)
{
bi = BigInteger.Zero;
if(binaryValue.Count(b => b == '1') + binaryValue.Count(b => b == '0') != binaryValue.Length)
return bi;
foreach(var c in binaryValue)
{
bi <<= 1;
bi += c == '1' ? 1 : 0;
}
return bi;
}
public static int GetBitWidth(this BigInteger n)
{
var nb = n.ToByteArray().Length - 1;
var rv = nb << 3;
return rv;
}
public static BigInteger GetMaxValue(this BigInteger bi, int bitLength)
{
if (bi.Sign == -1)
bitLength -= 1;
return(BigInteger.One << bitLength) - BigInteger.One;
}
public static BigInteger GetMaxValue(this BigInteger bi)
{
var bitLength = bi.GetBitWidth();
if (bi.Sign==-1)
bitLength -= 1;
return (BigInteger.One << bitLength) - BigInteger.One;
}
public static BigInteger BigIntegerBase16(this BigInteger bi, string hexNumber)
{
if(string.IsNullOrEmpty(hexNumber))
throw new Exception("Error: hexNumber cannot be either null or have a length of zero.");
if(!hexNumber.ContainsOnly("0123456789abcdefABCDEFxX"))
throw new Exception("Error: hexNumber cannot contain characters other than 0-9,a-f,A-F, or xX");
hexNumber = hexNumber.ToUpper();
if(hexNumber.IndexOf("0X", StringComparison.OrdinalIgnoreCase) != -1)
hexNumber = hexNumber.Substring(2);
var bytes = Enumerable.Range(0, hexNumber.Length)
.Where(x => x % 2 == 0)
.Select(x => Convert.ToByte(hexNumber.Substring(x, 2), 16))
.ToArray();
return new BigInteger(bytes.Concat(new byte[] {0}).ToArray());
}
public static BigInteger BigIntegerBase10(this BigInteger bi, string str)
{
if(str[0] == '-')
throw new Exception("Invalid numeric string. Only positive numbers are allowed.");
var number = new BigInteger();
int i;
for(i = 0; i < str.Length; i++)
if(str[i] >= '0' && str[i] <= '9')
number = number * Ten + long.Parse(str[i].ToString());
return number;
}
public static string ToBinaryString(this BigInteger bigint)
{
var bytes = bigint.ToByteArray();
var index = bytes.Length - 1;
var base2 = new StringBuilder(bytes.Length * 8);
var binary = Convert.ToString(bytes[index], 2);
if(binary[0] != '0' && bigint.Sign == 1) base2.Append('0');
base2.Append(binary);
for(index--; index >= 0; index--)
base2.Append(Convert.ToString(bytes[index], 2).PadLeft(8, '0'));
return base2.ToString();
}
public static string ToHexString(this BigInteger bi)
{
var bytes = bi.ToByteArray();
var sb = new StringBuilder();
foreach(var b in bytes)
{
var hex = b.ToString("X2");
sb.Append(hex);
}
return sb.ToString();
}
public static string ToOctalString(this BigInteger bigint)
{
var bytes = bigint.ToByteArray();
var index = bytes.Length - 1;
var base8 = new StringBuilder((bytes.Length / 3 + 1) * 8);
var rem = bytes.Length % 3;
if(rem == 0) rem = 3;
var base0 = 0;
while(rem != 0)
{
base0 <<= 8;
base0 += bytes[index--];
rem--;
}
var octal = Convert.ToString(base0, 8);
if(octal[0] != '0' && bigint.Sign == 1) base8.Append('0');
base8.Append(octal);
while(index >= 0)
{
base0 = (bytes[index] << 16) + (bytes[index - 1] << 8) + bytes[index - 2];
base8.Append(Convert.ToString(base0, 8).PadLeft(8, '0'));
index -= 3;
}
return base8.ToString();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment