c# - 如何在 C# 中将 BigIntegers 的除法计算为十进制而不是 double ？

Question

长话短说

F# PowerPack's BigRational 类型可以转换为 double 来计算值。但是，当分子和分母达到一定大小后，返回的值为double.NaN。

由于 BigRational 将分子和分母都作为 System.Numerics.BigInteger 进行跟踪，因此您可以使用对数属性来解决问题:

a / b = e^(ln(a) - ln(b))

有了我们的 BigInteger 分子和分母，我们可以调用

BigInteger num = myBigRational.Numerator;
BigInteger den = myBigRational.Denominator;
double value = Math.Exp(BigInteger.Log(num) - BigInteger.Log(den));

由于 double 类型的结构对于接近 0 的值的限制，我宁愿使用 decimal。我只是还没弄清楚怎么做。

上下文

只是为了好玩，我正在编写一个使用 Taylor series 计算圆周率的程序arctan 的。

arctan(x) = x - x^3/3 + x^5/5 - x^7/7 +  x^9/9 - ...

如果我们在 1 处评估系列，我们得到

arctan(1) = 1 - 1/3 + 1/5 - 1/7 + 1/9 - ...

因为 arctan(1) = pi/4，我们可以将我们的级数乘以 4 来计算 pi。

我的程序的目标是计算收敛到 pi 精确到 n 位 需要多少级数项。例如，为了使序列精确到一位数 (3)，它需要前三项:

1 term:  4 * (1) = 4
2 terms: 4 * (1 - 1/3) = 2.666666666666667
3 terms: 4 * (1 - 1/3 + 1/5) = 3.466666666666667

要精确到 2 位数字 (3.1)，它需要前 19 个术语。精确到 3 位数字 (3.14) 要求前 119 项，依此类推。

我最初使用 C# 的 decimal 类型编写我的程序:

const int MaxDigits = 20;
private static void RunDecimalCalculation()
{
    decimal pi = 0m; // our current approximation of pi
    decimal denominator = 1m;
    decimal addSubtract = 1m;
    ulong terms = 0;

    for (int digits = 0; digits < MaxDigits; digits++)
    {
        decimal piToDigits, upperBound;
        GetBounds(digits, out piToDigits, out upperBound);

        while (pi >= upperBound | pi < piToDigits)
        {
            pi += addSubtract * 4m / denominator;
            denominator += 2m;
            addSubtract *= -1m;
            terms++;
        }

        PrintUpdate(terms, digits, pi);
    }
}

/// <summary>
/// Returns the convergence bounds for <paramref name="digits"/> digits of pi.
/// </summary>
/// <param name="digits">Number of accurate digits of pi.</param>
/// <param name="piToDigits">Pi to the first <paramref name="digits"/> digits of pi.</param>
/// <param name="upperBound">same as <paramref name="piToDigits"/>, but with the last digit + 1</param>
/// <example>
/// <code>GetBounds(1)</code>:
///     piToDigits = 3
///     upperBound = 4
/// 
/// <code>GetBounds(2)</code>:
///     piToDigits = 3.1
///     upperbound = 3.2
/// </example>
private static void GetBounds(int digits, out decimal piToDigits, out decimal upperBound)
{
    int pow = (int)Math.Pow(10, digits);
    piToDigits = (decimal)Math.Floor(Math.PI * pow) / pow;
    upperBound = piToDigits + 1m / pow;
}

不过，我意识到，由于每次迭代中的舍入误差，在足够多的项之后，所需的项数可能会减少。因此，我开始研究 F# PowerPack 的 BigRational 并重写了代码:

// very minor optimization by caching common values
static readonly BigRational Minus1 = BigRational.FromInt(-1);
static readonly BigRational One = BigRational.FromInt(1);
static readonly BigRational Two = BigRational.FromInt(2);
static readonly BigRational Four = BigRational.FromInt(4);

private static void RunBigRationalCalculation()
{
    BigRational pi = BigRational.Zero;
    ulong terms = 0;
    var series = TaylorSeries().GetEnumerator();

    for (int digits = 0; digits < MaxDigits; digits++)
    {
        BigRational piToDigits, upperBound;
        GetBounds(digits, out piToDigits, out upperBound);

        while (pi >= upperBound | pi < piToDigits)
        {
            series.MoveNext();
            pi += series.Current;
            terms++;
        }

        double piDouble = Math.Exp(BigInteger.Log(pi.Numerator) - BigInteger.Log(pi.Denominator));
        PrintUpdate(terms, digits, (decimal)piDouble);
    }
}

// code adapted from http://tomasp.net/blog/powerpack-numeric.aspx
private static IEnumerable<BigRational> TaylorSeries()
{
    BigRational n = One;
    BigRational q = One;

    while (true)
    {
        yield return q * Four / n;

        n += Two;
        q *= Minus1;
    }
}

不出所料，这个版本的运行速度令人难以置信很慢，这很好。 (十进制版本用了34秒到9个准确位；BigRational版本用了17秒到5个准确位，跑了大概半小时还没到6个准确位)。不过，让我感到沮丧的是 double 不如 decimal 准确，因此虽然项数总是正确的，但从

显示的值

double piDouble = Math.Exp(BigInteger.Log(pi.Numerator) - BigInteger.Log(pi.Denominator));

不准确。有没有办法通过数学魔法或一些具有 Math.Exp() 和 BigInteger.Log() decimal 版本的库来解决这个问题？

Answer 1

How do I evaluate the division of BigIntegers as decimal rather than double in C#?

您有 BigIntegers N 和 D，并希望将精确值 N/D 近似为小数。 WOLOG 假设两者都是正的。

这很简单。先解决这个问题:

• 给定 N 和 D，找到使 N/D - M/10²⁸ 的绝对值最小的 BigInteger M。

二、解决这个问题:

• 给定 M，找到 BigInteger M' 和非负整数 E，使得 M/10 ²⁸ = M'/10 ^E 并且 E 最小化。

三、解决本题:

• 给定 M'，找到非负 BigIntegers I0、I1、I2，使得 M' = I0 + I1 * 2³² + I2 * 2⁶⁴ 并且每个都是严格小于 2³²。如果没有这样的I0、I1、I2，那么你的数就不能表示为小数。

将 I0、I1 和 I2 转换为无符号整数，然后再转换为有符号整数。

现在你已经拥有了调用所需的一切

https://msdn.microsoft.com/en-us/library/bb1c1a6x(v=vs.110).aspx

嘿，你手头有一个小数点。

就是说:您一开始就不需要这样做。您正在 BigRationals 中进行数学计算；为什么你会想把它们去掉成小数或 double ？只需将 pi 近似为大有理数中您想要的任何水平，并将缓慢转换的系列与该水平进行比较。

仅供引用，这个系列收敛非常缓慢。一旦您凭经验确定了它的收敛速度，您能否提供关于收敛速度的任何界限的证明？