Skip to content

Instantly share code, notes, and snippets.

@Misaka12456
Created August 9, 2023 05:44
Show Gist options
  • Save Misaka12456/521494981c54d5e4fe60b13c832164d8 to your computer and use it in GitHub Desktop.
Save Misaka12456/521494981c54d5e4fe60b13c832164d8 to your computer and use it in GitHub Desktop.
[C#][Utils][System.Enhance Utils Library] BigFloat - Float number with no limit of precision and storage range
using System.Numerics;
using System.Text;
namespace System.Enhance.Basics
{
/// <summary>
/// Represents a float number with no limit of precision and storage range.
/// </summary>
public struct BigFloat
{
/// <summary>
/// The maximum precision of the <see cref="BigFloat"/> when converting to string.
/// </summary>
public const int MaxPrecision = 100;
/// <summary>
/// The NaN (not a number) value of the <see cref="BigFloat"/> .
/// </summary>
public readonly static BigFloat NaN = new BigFloat(0, 0, true);
/// <summary>
/// The zero value of the <see cref="BigFloat"/> .
/// </summary>
public readonly static BigFloat Zero = new BigFloat(0, 1);
/// <summary>
/// The one value of the <see cref="BigFloat"/> .
/// </summary>
public readonly static BigFloat One = new BigFloat(1, 1);
/// <summary>
/// The minus one (-1) value of the <see cref="BigFloat"/> .
/// </summary>
public readonly static BigFloat MinusOne = new BigFloat(-1, 1);
/// <summary>
/// The positive infinity value of the <see cref="BigFloat"/> .
/// </summary>
public readonly static BigFloat PositiveInfinity = new BigFloat(1, 0, true);
/// <summary>
/// The negative infinity value of the <see cref="BigFloat"/> .
/// </summary>
public readonly static BigFloat NegativeInfinity = new BigFloat(-1, 0, true);
/// <summary>
/// The sign of the <see cref="BigFloat"/> , <see langword="true" /> for positive, <see langword="false" /> for negative.
/// </summary>
public bool Sign
{
get
{
// 分子和分母都是非负数,返回true
if (m_numerator.Sign >= 0 && m_denominator.Sign >= 0)
{
return true;
}
// 分子和分母都是负数,返回true(负负得正)
if (m_numerator.Sign < 0 && m_denominator.Sign < 0)
{
return true;
}
// 分子负数分母非负数,或者分子非负数分母负数,返回false
return false;
}
}
/// <summary>
/// The numerator part of the <see cref="BigFloat"/> .
/// </summary>
public BigInteger Numerator => m_numerator;
/// <summary>
/// The denominator part of the <see cref="BigFloat"/> .
/// </summary>
public BigInteger Denominator => m_denominator;
private BigInteger m_numerator, m_denominator; // 分子,分母
/// <summary>
/// Whether the BigFloat is <see langword="NaN"/> (not a number).
/// </summary>
public bool IsNaN { get; private set; } = false;
/// <summary>
/// Whether the BigFloat is <see langword="Infinity"/> (positive or negative).
/// </summary>
public bool IsInfinity => (IsNaN || m_denominator == 0) && m_numerator != 0;
/// <summary>
/// Whether the BigFloat is <see langword="PositiveInfinity"/> (positive).
/// </summary>
public bool IsPositiveInfinity => IsInfinity && m_numerator > 0;
/// <summary>
/// Whether the BigFloat is <see langword="NegativeInfinity"/> (negative).
/// </summary>
public bool IsNegativeInfinity => IsInfinity && m_numerator < 0;
/// <summary>
/// Creates a new <see cref="BigFloat"/> instance with the specified numerator and denominator.
/// </summary>
/// <param name="numerator">The numerator of the BigFloat.</param>
/// <param name="denominator">The denominator of the BigFloat.</param>
/// <exception cref="ArgumentException">Thrown when the denominator is zero.</exception>
public BigFloat(BigInteger numerator, BigInteger denominator)
{
if (denominator == 0)
{
throw new ArgumentException("The denominator of the BigFloat cannot be zero, which leads to a BigFloat as meaningless. " +
"If you want to use a NaN BigFloat, directly use BigFloat.NaN instead.");
}
m_numerator = numerator;
m_denominator = denominator;
}
private BigFloat(BigInteger numerator, BigInteger denominator, bool ignoreCheck = false)
{
if (!ignoreCheck && denominator == 0)
{
throw new ArgumentException("The denominator of the BigFloat cannot be zero, which leads to a BigFloat as meaningless. " +
"If you want to use a NaN BigFloat, directly use BigFloat.NaN instead." +
"If you want to create a NaN BigFloat privately, please set ignoreCheck to true.");
}
else if (denominator == 0)
{
IsNaN = true;
}
m_numerator = numerator;
m_denominator = denominator;
}
public BigFloat(sbyte value)
{
m_numerator = value;
m_denominator = BigInteger.One;
}
public BigFloat(byte value)
{
m_numerator = value;
m_denominator = BigInteger.One;
}
public BigFloat(short value)
{
m_numerator = value;
m_denominator = BigInteger.One;
}
public BigFloat(ushort value)
{
m_numerator = value;
m_denominator = BigInteger.One;
}
public BigFloat(int value)
{
m_numerator = value;
m_denominator = BigInteger.One;
}
public BigFloat(long value)
{
m_numerator = value;
m_denominator = BigInteger.One;
}
public BigFloat(uint value)
{
m_numerator = value;
m_denominator = BigInteger.One;
}
public BigFloat(ulong value)
{
m_numerator = value;
m_denominator = BigInteger.One;
}
public BigFloat(BigInteger value)
{
m_numerator = value;
m_denominator = BigInteger.One;
}
public BigFloat(float value)
{
int bits = BitConverter.ToInt32(BitConverter.GetBytes(value), 0);
int mantissa = bits & 0x007FFFFF; // mantissa=尾数
int exponent = (bits >> 23) & 0xFF; // exponent=指数
int sign = (bits >> 31) & 0x01; // sign=符号位
if (exponent == 0xFF) // NaN or Infinity
{
if (mantissa == 0)
{
m_numerator = sign == 0 ? BigInteger.One : BigInteger.MinusOne;
m_denominator = BigInteger.Zero;
IsNaN = true;
}
else
{
m_numerator = sign == 0 ? BigInteger.One : BigInteger.MinusOne;
m_denominator = BigInteger.Zero;
}
}
else if (exponent == 0) // Denormalized
{
m_numerator = BigInteger.Zero;
m_denominator = BigInteger.One;
}
else // Normalized
{
int e = exponent - 127;
var m = new BigInteger(mantissa) * BigInteger.Pow(2, -23);
var a = BigInteger.Pow(2, e);
var b = BigInteger.Pow(10, 23);
var gcd = BigInteger.GreatestCommonDivisor(m, b);
m /= gcd;
b /= gcd;
m_numerator = sign == 0 ? m * a : -m * a;
m_denominator = b;
}
}
public BigFloat(double value)
{
long bits = BitConverter.DoubleToInt64Bits(value);
long mantissa = bits & 0x000FFFFFFFFFFFFFL;
int exponent = (int)((bits >> 52) & 0x7FFL);
int sign = (int)((bits >> 63) & 0x01L);
if (exponent == 0x7FF) // NaN 或者 Infinity
{
if (mantissa == 0)
{
m_numerator = sign == 0 ? BigInteger.One : BigInteger.MinusOne;
m_denominator = BigInteger.Zero;
IsNaN = true;
}
else
{
m_numerator = sign == 0 ? BigInteger.One : BigInteger.MinusOne;
m_denominator = BigInteger.Zero;
}
}
else if (exponent == 0)
{
m_numerator = BigInteger.Zero;
m_denominator = BigInteger.One;
}
else
{
int e = exponent - 1023;
var m = new BigInteger(mantissa) * BigInteger.Pow(2, -52);
var a = BigInteger.Pow(2, e);
var b = BigInteger.Pow(10, 52);
var gcd = BigInteger.GreatestCommonDivisor(m, b);
m /= gcd;
b /= gcd;
m_numerator = sign == 0 ? m * a : -m * a;
m_denominator = b;
}
}
public BigFloat(decimal value)
{
int[] bits = decimal.GetBits(value);
int sign = (bits[3] >> 31) & 0x01;
int exponent = (bits[3] >> 16) & 0x1F;
int mantissaHigh = bits[2];
int mantissaLow = bits[0];
if (exponent == 0x1F) // NaN 或者 Infinity
{
if ((mantissaHigh == 0) && (mantissaLow == 0))
{
m_numerator = sign == 0 ? BigInteger.One : BigInteger.MinusOne;
m_denominator = BigInteger.Zero;
IsNaN = true;
}
else
{
m_numerator = sign == 0 ? BigInteger.One : BigInteger.MinusOne;
m_denominator = BigInteger.Zero;
}
}
else if (exponent == 0)
{
m_numerator = BigInteger.Zero;
m_denominator = BigInteger.One;
}
else
{
int e = exponent - 28;
long m = ((long)mantissaHigh << 32) | (mantissaLow & 0xFFFFFFFFL);
var d = BigInteger.Pow(10, 28);
var a = BigInteger.Pow(2, e) * m;
var gcd = BigInteger.GreatestCommonDivisor(a, d);
a /= gcd;
d /= gcd;
m_numerator = sign == 0 ? a : -a;
m_denominator = d;
}
}
public static BigFloat operator +(BigFloat x, BigFloat y)
{
if (x.IsNaN || y.IsNaN)
{
return NaN;
}
var num = (x.m_numerator * y.m_denominator) + (y.m_numerator * x.m_denominator);
var den = x.m_denominator * y.m_denominator;
var r = new BigFloat(num, den, true);
if (r.m_denominator < 0)
{
r.m_numerator = -r.m_numerator;
r.m_denominator = -r.m_denominator;
}
else if (r.m_denominator == 0)
{
r = NaN;
}
return r;
}
public static BigFloat operator -(BigFloat x, BigFloat y)
{
if (x.IsNaN || y.IsNaN)
{
return NaN;
}
var num = (x.m_numerator * y.m_denominator) - (y.m_numerator * x.m_denominator); // 同+
var den = x.m_denominator * y.m_denominator;
var r = new BigFloat(num, den);
if (r.m_denominator < 0)
{
r.m_numerator = -r.m_numerator;
r.m_denominator = -r.m_denominator;
}
else if (r.m_denominator == 0)
{
r = NaN;
}
return r;
}
public static BigFloat operator *(BigFloat x, BigFloat y)
{
if (x.IsNaN || y.IsNaN)
{
return NaN;
}
var num = x.m_numerator * y.m_numerator;
var den = x.m_denominator * y.m_denominator;
var r = new BigFloat(num, den);
if (r.m_denominator < 0)
{
r.m_numerator = -r.m_numerator;
r.m_denominator = -r.m_denominator;
}
else if (r.m_denominator == 0)
{
r = NaN;
}
return r;
}
public static BigFloat operator /(BigFloat x, BigFloat y)
{
if (y.m_numerator == 0 && !y.IsNaN)
{
y.IsNaN = true;
}
if (x.IsNaN || y.IsNaN)
{
return NaN;
}
// 相当于x*(y的倒数)
var num = x.m_numerator * y.m_denominator;
var den = x.m_denominator * y.m_numerator;
var r = new BigFloat(num, den);
if (r.m_denominator < 0)
{
r.m_numerator = -r.m_numerator;
r.m_denominator = -r.m_denominator;
}
else if (r.m_denominator == 0)
{
r = NaN;
}
return r;
}
public static bool operator ==(BigFloat x, BigFloat y)
{
if (x.IsNaN || y.IsNaN) return false; // NaN不相等(不能用if (a == BigFloat.NaN)判断, 需要用if (a.IsNaN)判断)
return x.m_numerator * y.m_denominator == y.m_numerator * x.m_denominator;
}
public static bool operator !=(BigFloat x, BigFloat y)
{
if (x.IsNaN || y.IsNaN) return true; // NaN不相等(不能用if (a == BigFloat.NaN)判断, 需要用if (a.IsNaN)判断)
return x.m_numerator * y.m_denominator != y.m_numerator * x.m_denominator;
}
public static bool operator <(BigFloat x, BigFloat y) => x.CompareTo(y) < 0;
public static bool operator >(BigFloat x, BigFloat y) => x.CompareTo(y) > 0;
public static bool operator <=(BigFloat x, BigFloat y) => x.CompareTo(y) <= 0;
public static bool operator >=(BigFloat x, BigFloat y) => x.CompareTo(y) >= 0;
public int CompareTo(BigFloat? other)
{
if (!other.HasValue) return 1;
var otherMain = other.Value;
#region NaN检查
#region 无穷判断检查
if (IsPositiveInfinity && !otherMain.IsInfinity) return 1; // 正无穷 > 任何数
if (IsNegativeInfinity && !otherMain.IsInfinity) return -1; // 负无穷 < 任何数
if (IsPositiveInfinity && otherMain.IsNegativeInfinity) return 1; // 正无穷 > 负无穷
if (IsNegativeInfinity && otherMain.IsPositiveInfinity) return -1; // 负无穷 < 正无穷
if (!IsInfinity && otherMain.IsPositiveInfinity) return -1; // 任何数 < 正无穷
if (!IsInfinity && otherMain.IsNegativeInfinity) return 1; // 任何数 > 负无穷
#endregion
if (IsNaN && !otherMain.IsNaN) return -1; // NaN < 任何数
if (!IsNaN && otherMain.IsNaN) return 1; // 任何数 > NaN
if (IsNaN && otherMain.IsNaN) return 0; // NaN == NaN
#endregion
if (Sign != otherMain.Sign)
{
return Sign.CompareTo(otherMain.Sign);
}
var absValue1 = Abs();
var absValue2 = otherMain.Abs();
int numResult = absValue1.m_numerator.CompareTo(absValue2.m_numerator);
if (numResult != 0) return numResult;
return absValue1.m_denominator.CompareTo(absValue2.m_denominator);
}
public override bool Equals(object? obj)
{
if (obj is BigFloat bf)
{
return this == bf;
}
return false;
}
public override int GetHashCode()
{
return m_numerator.GetHashCode() ^ m_denominator.GetHashCode() ^ IsNaN.GetHashCode();
}
/// <summary>
/// Calculates the power of given exponent of this instance.
/// </summary>
/// <param name="n">The exponent.</param>
/// <returns>The result of the power operation.</returns>
public BigFloat Pow(BigFloat n)
{
if (m_denominator == 0 || IsNaN)
{
return NaN; // 对NaN的任何运算都返回NaN
}
var num = n.m_numerator;
var den = n.m_denominator;
if (num == 0 && den < 0)
{
// 0的负次幂是无穷大
return PositiveInfinity;
}
bool isNegativeBase = m_numerator < 0;
if (isNegativeBase && den % 2 == 0)
{
// 负数的偶次幂是正数
isNegativeBase = false;
}
if (num < 0)
{
// 负次幂等于正次幂的倒数
num *= -1;
var temp = num;
num = den;
den = temp; // 交换num和den(取倒数)
}
BigFloat r;
if (den == 0)
{
// 指数为整数
r = NewtonRaphson(this, num);
}
else if (den > 0)
{
// 指数为正分数
r = NewtonRaphson(this, den).Pow(new BigFloat(num, 1));
}
else
{
// 指数为负分数
var temp = NewtonRaphson(One / this, -den);
r = temp.Pow(new BigFloat(num, 1));
}
if (isNegativeBase)
{
// 负数的奇次幂是负数
r.m_numerator *= -1;
}
return r;
}
private static BigFloat NewtonRaphson(BigFloat x, BigInteger nInt)
{
var r = x;
var n = new BigFloat(nInt, 1);
for (; ; )
{
var prevR = r;
var num = r.Pow(n - 1);
var den = n;
r = (num + x / (prevR.Pow(n - 1))) / den;
if (r == prevR)
{
// 当r不再变化时, 说明已经达到了精度要求,迭代结束
break;
}
}
return r;
}
/// <summary>
/// Returns the absolute value of this instance.
/// </summary>
/// <returns>A new instance which contains the absolute value of this instance.</returns>
public BigFloat Abs() // 取绝对值
{
return new BigFloat(BigInteger.Abs(m_numerator), BigInteger.Abs(m_denominator));
}
/// <summary>
/// Normalizes this instance (reduces it such that the denominator is positive and the numerator and denominator are relatively prime).
/// </summary>
/// <returns>Normalized instance.</returns>
public BigFloat Normalize() // "约分"
{
if (m_denominator < 0)
{
m_numerator *= -1;
m_denominator *= -1;
}
var gcd = BigInteger.GreatestCommonDivisor(m_numerator, m_denominator);
if (gcd != 1)
{
m_numerator /= gcd;
m_denominator /= gcd;
}
return this;
}
/// <summary>
/// Gets the integral part of this instance (the biggest integral value that is less than or equal to this instance).
/// </summary>
/// <returns>The integral part of this instance.</returns>
public BigFloat Floor() // 取整
{
if (m_denominator == 0 || IsNaN)
{
return NaN; // 对NaN的任何运算都返回NaN
}
if (m_numerator < 0)
{
return new BigFloat(m_numerator / m_denominator - 1, 1);
}
else
{
return new BigFloat(m_numerator / m_denominator, 1);
}
}
/// <summary>
/// Gets the smallest integral value that is greater than or equal to this instance.
/// </summary>
/// <returns>The value.</returns>
public BigFloat Ceiling() // 向上取整
{
if (m_denominator == 0 || IsNaN)
{
return NaN; // 对NaN的任何运算都返回NaN
}
if (m_numerator < 0)
{
return new BigFloat(m_numerator / m_denominator, 1);
}
else
{
return new BigFloat(m_numerator / m_denominator + 1, 1);
}
}
/// <summary>
/// Parse a string with numeric value to a <see cref="BigFloat"/>.
/// </summary>
/// <param name="s">The numeric value string.</param>
/// <returns>The <see cref="BigFloat"/> value.</returns>
/// <exception cref="FormatException">The string is not in a format compliant with <see cref="BigFloat"/>.</exception>
/// <exception cref="ArgumentNullException"><paramref name="s"/> is <see langword="null"/>.</exception>
/// <exception cref="OutOfMemoryException">There is insufficient memory to allocate a new <see cref="BigFloat"/> instance because the numeric value in the string is too large.</exception>
public static BigFloat Parse(string? s)
{
try
{
if (string.IsNullOrEmpty(s))
{
throw new ArgumentNullException(nameof(s));
}
s = s.Trim();
if (BigInteger.TryParse(s, out var intValue))
{
return new BigFloat(intValue, 1);
}
else
{
int decimalPointIdx = s.IndexOf('.');
if (decimalPointIdx != -1 && decimalPointIdx < s.Length - 1)
{
string intPart = s.Substring(0, decimalPointIdx);
string fracPart = s.Substring(decimalPointIdx + 1);
var num = BigInteger.Parse(intPart);
var den = BigInteger.Pow(10, fracPart.Length);
num *= BigInteger.Pow(10, fracPart.Length);
num += BigInteger.Parse(fracPart);
if (s[0] == '-')
{
num = BigInteger.Negate(num);
}
return new BigFloat(num, den);
}
}
throw new FormatException("Invalid input format");
}
catch (ArgumentNullException)
{
throw;
}
catch (OutOfMemoryException)
{
throw;
}
catch (FormatException)
{
throw;
}
catch (Exception ex)
{
throw new FormatException("Invalid input format", ex);
}
}
/// <summary>
/// Parse a string with numeric value to a <see cref="BigFloat"/>.
/// </summary>
/// <param name="s">The numeric value string.</param>
/// <param name="result">The <see cref="BigFloat"/> value.</param>
/// <returns>Whether the parsing is successful.</returns>
public static bool TryParse(string? s, out BigFloat result)
{
try
{
result = Parse(s);
return true;
}
catch
{
result = Zero;
return false;
}
}
/// <summary>
/// Converts the numeric value of this instance to its equivalent string representation.
/// </summary>
/// <returns>The numeric value.</returns>
public override string ToString()
{
if (IsNaN)
{
if (IsPositiveInfinity)
{
return "Infinity";
}
else if (IsNegativeInfinity)
{
return "-Infinity";
}
else
{
return "NaN";
}
}
var sb = new StringBuilder();
bool isNegative = false;
var absValue = this;
if (absValue.CompareTo(BigFloat.Zero) < 0)
{
isNegative = true;
absValue = absValue.Abs();
}
var num = absValue.m_numerator;
var den = absValue.m_denominator;
var intPart = BigInteger.DivRem(num, den, out var remainder);
sb.Append(intPart.ToString());
if (remainder != BigInteger.Zero)
{
sb.Append('.');
int precision = 0;
while (remainder != BigInteger.Zero && precision < MaxPrecision)
{
remainder *= 10;
var digit = BigInteger.DivRem(remainder, den, out remainder);
sb.Append(digit.ToString());
precision++;
}
}
else if (sb.Length == 0)
{
sb.Append('0');
}
if (isNegative)
{
sb.Insert(0, '-');
}
return sb.ToString();
}
/// <summary>
/// Converts the numeric value of this instance to its equivalent double-precision floating-point number.
/// </summary>
/// <returns>The converted double-precision floating-point number.</returns>
public double ToDouble()
{
if (IsNaN || m_denominator == 0)
{
if (IsPositiveInfinity)
{
return double.PositiveInfinity;
}
else if (IsNegativeInfinity)
{
return double.NegativeInfinity;
}
else
{
return double.NaN;
}
}
return (double)m_numerator / (double)m_denominator;
}
#region In-Operators (? -> BigFloat)
public static implicit operator BigFloat(sbyte value) => new BigFloat(value);
public static implicit operator BigFloat(byte value) => new BigFloat(value);
public static implicit operator BigFloat(short value) => new BigFloat(value);
public static implicit operator BigFloat(ushort value) => new BigFloat(value);
public static implicit operator BigFloat(int value) => new BigFloat(value);
public static implicit operator BigFloat(uint value) => new BigFloat(value);
public static implicit operator BigFloat(long value) => new BigFloat(value);
public static implicit operator BigFloat(ulong value) => new BigFloat(value);
public static implicit operator BigFloat(float value) => new BigFloat(value);
public static implicit operator BigFloat(double value) => new BigFloat(value);
public static implicit operator BigFloat(decimal value) => new BigFloat(value);
public static implicit operator BigFloat(BigInteger value) => new BigFloat(value);
#endregion
#region Out-Operators (BigFloat -> ?)
public static explicit operator sbyte(BigFloat bf) => (sbyte)(bf.m_numerator / bf.m_denominator);
public static explicit operator byte(BigFloat bf) => (byte)(bf.m_numerator / bf.m_denominator);
public static explicit operator short(BigFloat bf) => (short)(bf.m_numerator / bf.m_denominator);
public static explicit operator ushort(BigFloat bf) => (ushort)(bf.m_numerator / bf.m_denominator);
public static explicit operator int(BigFloat bf) => (int)(bf.m_numerator / bf.m_denominator);
public static explicit operator uint(BigFloat bf) => (uint)(bf.m_numerator / bf.m_denominator);
public static explicit operator long(BigFloat bf) => (long)(bf.m_numerator / bf.m_denominator);
public static explicit operator ulong(BigFloat bf) => (ulong)(bf.m_numerator / bf.m_denominator);
public static explicit operator float(BigFloat bf) => (float)bf.ToDouble();
public static explicit operator double(BigFloat bf) => bf.ToDouble();
public static explicit operator decimal(BigFloat bf) => (decimal)bf.ToDouble();
public static explicit operator BigInteger(BigFloat bf) => bf.m_numerator / bf.m_denominator;
#endregion
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment