从小数/小数中得到分母和分子的最有效方法是什么?

Question

我想从小数中得到分子和分母，然后将分子和分母都化简。例如，如果小数是0.05，那么分子和分母应该是1/20。最好没有循环/迭代，或者尽量少的循环/迭代，并且没有内存堆。

我目前正在使用这个代码，但它导致0/1而不是预期的1/20。

---

public Fraction(double chance) {
long num = 0;
long den = 1;
unchecked {
ulong bitwiseRepr = BitConverter.DoubleToUInt64Bits(chance);
ulong signBit = bitwiseRepr >> 63;
ulong expBits = bitwiseRepr >> 52;
ulong mntsBits = bitwiseRepr & 0x7FFFFFFFFF;
long signFactor = signBit == 1 ? -1 : 1;
if (expBits == 0x0000 || expBits == 0x0800) { // +0, -0
goto NormalWay;
}
else if (expBits == 0x07FF || expBits == 0x0FFF) { // +Inf, -Inf
num = 0;
den = signFactor;
goto NormalWay;
}
else if (expBits == 0x07FFF) { // NaN
num = long.MaxValue;
den = 0;
goto NormalWay;
}
long significand = (long)((1u << 52) | mntsBits);
int nTrailizingZeros = CountTrailingZeroes(significand);
significand >>= nTrailizingZeros;
int exp = (int)expBits - 127 - 52 + nTrailizingZeros;
if (exp < 0) {
num = significand;
den = 1 << -exp;
}
else {
num = signFactor * significand * (1 << exp);
den = 1;
}
goto NormalWay;
}
NormalWay:
numerator = num;
denominator = den;
Normalize();
}
private static int CountTrailingZeroes(long v) {
int counter = 0;
while (counter < 64 && (v & 1u) == 0) {
v >>= 1;
counter++;
}
return counter;
}
[MethodImpl(MethodImplOptions.AggressiveOptimization | MethodImplOptions.AggressiveInlining)]
public void Normalize() {
bool numeratorIsNegative = numerator < 0;
bool denominatorIsNegative = denominator < 0;
if (numeratorIsNegative) {
numerator *= -1;
}
if (denominatorIsNegative) {
denominator *= -1;
}
if (numerator > long.MaxValue / 2 && denominator > long.MaxValue / 2) {
throw new ArithmeticException($"Numerator or denominator are greater than {long.MaxValue / 2} or lesser than {-long.MaxValue / 2}.");
}
numerator += denominator;
Reduce(GCD(numerator, denominator));
Reduce(Math.Sign(denominator));
numerator %= denominator;
if (numeratorIsNegative) {
numerator *= -1;
}
if (denominatorIsNegative) {
denominator *= -1;
}
}
[MethodImpl(MethodImplOptions.AggressiveOptimization | MethodImplOptions.AggressiveInlining)]
private void Reduce(long x) {
numerator /= x;
denominator /= x;
}
[MethodImpl(MethodImplOptions.AggressiveOptimization | MethodImplOptions.AggressiveInlining)]
private static long GCD(long a, long b) {
while (b != 0) {
long t = b;
b = a % b;
a = t;
}
return a;
}

当前的代码也将不太准确，因为它只适用于双精度(目前)。

Answer 1

就这么简单:

internal static (BigInteger numerator, BigInteger denominator) Fraction(decimal d)
{
int[] bits = decimal.GetBits(d);
BigInteger numerator = (1 - ((bits[3] >> 30) & 2)) *
unchecked(((BigInteger)(uint)bits[2] << 64) |
((BigInteger)(uint)bits[1] << 32) |
(BigInteger)(uint)bits[0]);
BigInteger denominator = BigInteger.Pow(10, (bits[3] >> 16) & 0xff);
return (numerator, denominator);
}