仅使用加法和乘法实现除法

Question

我正在用BigDecimal编写一个C#类。我已经成功地实现了+，-和*操作符。但我想不出一种计算2 BigDecimals除法的方法。使用这三个操作符来实现除法的最快方法是什么？还是有更好的方法来做到这一点？(同时考虑开发时间和算法速度)

目标1:我希望结果是另一个具有固定精度的BigDecimal (应该是可变的)

目标2:正如您提到的，BigDecimal的目的不是一个固定的精度。那么如何实现无限精度的呢？

另一个问题：是否更好(关于速度和灵活性)使用Microsoft的BigRational类来处理任意精度的算术，然后在这个线程中使用Christopher的扩展方法：在BigFloat中有C#类吗？获得十进制表示而不是编写一个新类？

Answer 1

• 您可以从Java BigDecimal实现中了解一些想法。
• 对于计算a/b，可以使用二进制搜索算法查找b*c=a(您应该运行算法直到达到所需的精度)。
• 此外，您还可以查看这个BigFloat类，它具有指数形式的有趣实现。
• 对于无限的精度，您可以将BigDecimal存储为两个BigInteger的有理数。

有理数表示的代数：

(x1/x2) + (y1/y2) = (x1*y2+x2*y1)/(x2*y2)    
(x1/x2) - (y1/y2) = (x1*y2-x2*y1)/(x2*y2)    
(x1/x2) * (y1/y2) = (x1*y1)/(x2*y2)
(x1/x2) / (y1/y2) = (x1*y2)/(x2*y1)

实现双倍(固定精度)的实例：

public double Divide(double a, double b, double eps)
{
    double l = 0, r = a;
    while (r - l > eps)
    {
        double m = (l + r) / 2;
        if (m * b < a)
            l = m;
        else
            r = m;
    }
    return (l + r) / 2;
}

Answer 2

埃里克·利珀特的回答看上去很像“以最慢的方式进行长期分裂”。它是准确的，但它不快。假设您有一种使用double近似您的BigDecimal的方法，并且由于您已经在BD类中实现了+、-和*，那么您可以(大约)执行以下操作：

BD operator/(BD a, BD b) {
  BD r, result=0, residual;
  double aa, bb, rr;
  residual = a;
  bb = b;
  while (residual > desired) {
    rr = (double)residual / bb;
    r = rr; // assuming you have a conversion from double to bigdecimal with loss of precision
    result += r;
    residual = a - (result * b);
  }
  return result;
}

这将进行逐次逼近，但同时会出现多个数字(基本上，您使用BD算术查找错误，然后使用双算术将其除以)。我认为这应该是一种相对简单和有效的办法。

我使用float和double实现了上述版本--只是为了向我自己证明这个原则是可行的。使用一个简单的C框架，只需两次迭代就可以将精度降到double除法的水平。我希望你明白这个想法。

#include <stdio.h>

double divide(double a, double b);
int main(void) {
  double a, b, result;
  float fa, fb, fr;
  a = 123.5;
  b = 234.6;
  fa = a;
  fb = b;
  fr = fa / fb;
  printf("using float: %f\n", fr);
  result = divide(a, b);
  printf("using double: %lf\n", result);
  printf("difference: %le\n", result - fr);
}

double divide(double a, double b) {
      double r, result=0, residual;
      float aa, bb, rr;
      residual = a;
      bb = b;
      while (residual > 1e-8) {
        rr = (float)residual / bb;
        r = rr; // assuming you have a conversion from double to bigdecimal with loss of precision
        result += r;
        residual = a - (result * b);
        printf("residual is now %le\n", residual);
      }
      return result;
    }

输出：

using float: 0.526428
residual is now 8.881092e-06
residual is now 5.684342e-14
using double: 0.526428
difference: 3.785632e-08