What is the most efficient way to get denominator and numerator from decimal/fractional number

Question

I want to get numerator and denominator from decimal and then simplify both numerator and denominator. For example, if decimal is 0.05, then numerator and denominator should be 1/20. Preferably without loops/iterations or least amount of those and without memory heap.

I'm currently using this code, but it results in 0/1 rather than expected 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;
        }

Current code is also going to be less acurate cause it works just for doubles (yet).

Decimal to Fraction conversion isn't new. There are many posts/articles on the subject. Try these: [On MSDN](https://social.msdn.microsoft.com/Forums/en-US/e4df16cf-4207-4b76-8116-e02f689135ec/converting-a-decimal-to-a-fraction-in-c?forum=csharplanguage) or [On SO](https://stackoverflow.com/questions/5124743/algorithm-for-simplifying-decimal-to-fractions) — Tim Jarosz, Dec 21 '22 at 16:29
Does this answer your question? [Algorithm for simplifying decimal to fractions](https://stackoverflow.com/questions/5124743/algorithm-for-simplifying-decimal-to-fractions) — High Performance Mark, Dec 21 '22 at 17:10
it sorta does, yes, but that won't work on really small decimals from what i tested — BasicallyIAmFox, Dec 21 '22 at 17:30
`double chance` is _never_ exactly 0.05. Instead the nearest `double` is _exactly_ 3602879701896397/72057594037927936. BasicallyIAmFox, is that the fraction you seek in this case? — chux - Reinstate Monica, Dec 22 '22 at 06:11

score 0 · Accepted Answer · answered Dec 21 '22 at 17:24

As simple as that:

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);
}

@BasicallyIAmFox check it once again, it gives (5, 100). – Roman Ryzhiy Dec 21 '22 at 18:04 — Roman Ryzhiy, Dec 21 '22 at 18:04

What is the most efficient way to get denominator and numerator from decimal/fractional number

1 Answers1