Created
March 2, 2019 16:34
-
-
Save mjs3339/f32dc46163095d4e3ddff5f4df7de01b to your computer and use it in GitHub Desktop.
C# BigInteger Extension Class
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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