任意精度算术解释

Question

我正在尝试学习C并且遇到无法使用真正的大数字(即100位,1000位等).我知道存在这样做的库,但我想尝试自己实现它.

我只是想知道是否有人或者可以提供任意精度算术的非常详细,愚蠢的解释.

Answer 1

这些都是充足的存储和算法,将数字视为较小的部分.假设您有一个编译器,其中int只能是0到99,并且您希望处理高达999999的数字(我们只会担心这里的正数以保持简单).

你这样做是通过给每个数字三个ints并使用你应该在小学里学到的相同规则来进行加法,减法和其他基本操作.

在任意精度库中,用于表示数字的基本类型数量没有固定限制,只有内存可以容纳.

例如:添加123456 + 78:

12 34 56
      78
-- -- --
12 35 34

从最不重要的一端开始工作:

• 初始值= 0.
• 56 + 78 + 0进位= 134 = 34进位1
• 34 + 00 + 1进位= 35 = 35进位0
• 12 + 00 + 0进位= 12 = 12进位0

实际上,这是加法通常如何在CPU内部的位级工作.

减法是类似的(使用基本类型的减法并借用而不是进位),乘法可以通过重复加法(非常慢)或交叉积(更快)来完成,除法更棘手但可以通过移位和减法来完成参与(你小时候会学到很长的分工).

我实际上已经编写了库来使用10的最大功率来做这种事情,这些函数可以在平方时适合整数(以防止在将两个ints 相乘时出现溢出,例如将16位int限制为0到99到平方时生成9,801(<32,768),或者int使用0到9,999生成32位,生成99,980,001(<2,147,483,648),这大大简化了算法.

一些值得注意的技巧.

1 /当添加或乘以数字时,预先分配所需的最大空间,如果发现它太多,则稍后减少.例如,添加两个100-"数字"(数字为数字int)数字将永远不会超过101位数.将12位数字乘以3位数字将永远不会生成超过15位数字(添加数字计数).

2 /为了增加速度,只有在绝对必要时才对数字进行标准化(减少所需的存储空间) - 我的库将其作为一个单独的调用,以便用户可以在速度和存储问题之间做出决定.

3 /正数和负数的相加是减法,减去负数与添加等效正数相同.通过在调整符号后使用add和subtract方法相互调用,可以节省相当多的代码.

4 /避免从小数字中减去大数字,因为你总是得到如下数字:

         10
         11-
-- -- -- --
99 99 99 99 (and you still have a borrow).

相反,从11中减去10,然后否定它:

11
10-
--
 1 (then negate to get -1).

以下是我必须执行此操作的库之一的注释(转换为文本).遗憾的是,代码本身受版权保护,但您可以选择足够的信息来处理这四种基本操作.在下面假设-a并且-b表示负数,a并且b是零或正数.

对于另外,如果标志是不同的,否定的使用减法:

-a +  b becomes b - a
 a + -b becomes a - b

对于减法,如果符号不同,请使用否定的加法:

 a - -b becomes   a + b
-a -  b becomes -(a + b)

还有特殊处理,以确保我们从大型减去小数字:

small - big becomes -(big - small)

乘法使用入门级数学,如下所示:

475(a) x 32(b) = 475 x (30 + 2)
               = 475 x 30 + 475 x 2
               = 4750 x 3 + 475 x 2
               = 4750 + 4750 + 4750 + 475 + 475

实现这一目的的方法包括一次一个地(向后)提取32的每个数字,然后使用add来计算要添加到结果的值(最初为零).

ShiftLeft和ShiftRight操作用于快速乘以或除以LongInt包裹值(10为"真实"数学).在上面的示例中,我们将475添加到零2次(最后一位数为32)以获得950(结果= 0 + 950 = 950).

然后我们离开移位475以获得4750并且右移32获得3.将4750添加到零3次以获得14250然后添加到950的结果以获得15200.

左移4750得到47500,右移3得到0.因为右移32现在为零,我们完成了,实际上475 x 32等于15200.

分区也很棘手,但基于早期的算术("gazinta"方法为"进入").考虑以下长划分12345 / 27:

       457
   +-------
27 | 12345    27 is larger than 1 or 12 so we first use 123.
     108      27 goes into 123 4 times, 4 x 27 = 108, 123 - 108 = 15.
     ---
      154     Bring down 4.
      135     27 goes into 154 5 times, 5 x 27 = 135, 154 - 135 = 19.
      ---
       195    Bring down 5.
       189    27 goes into 195 7 times, 7 x 27 = 189, 195 - 189 = 6.
       ---
         6    Nothing more to bring down, so stop.

因此12345 / 27是457剩下的6.校验:

  457 x 27 + 6
= 12339    + 6
= 12345

这是通过使用一个下拉变量(最初为零)来实现的,一次一个地降低12345的段,直到它大于或等于27.

然后我们简单地从中减去27直到我们得到27以下 - 减法的数量是添加到顶行的段.

如果没有更多细分可以降低,我们就会得到结果.

请记住,这些是非常基本的算法.如果您的数字特别大,那么有更好的方法可以进行复杂的算术运算.您可以查看类似GNU多精度算术库的内容 - 它比我自己的库更好更快.

它确实有一个相当不幸的错误,因为它会在内存不足的情况下退出(在我看来,这是一个通用库的一个相当致命的缺陷),但是,如果你能看一眼它,它的功能就相当不错了.

如果由于许可原因而无法使用它(或者因为您不希望您的应用程序只是出于没有明显原因退出),您至少可以从那里获取算法以集成到您自己的代码中.

我还发现,在在的BOD MPIR(GMP的一个分支)有更适合的潜在变化的讨论-他们似乎更开发者友好的一群.

Answer 2

虽然重新发明轮子对你的个人启发和学习非常有益,但它也是一项非常大的任务.我不想劝阻你作为一项重要的练习,也不是我自己完成的练习,但是你应该意识到,大型软件包解决了工作中存在的微妙而复杂的问题.

例如,乘法.天真的,你可能会想到'小学生'的方法,即将一个数字写在另一个数字之上,然后在学校学习时进行长时间的乘法运算.例:

      123
    x  34
    -----
      492
+    3690
---------
     4182

但这种方法非常慢(O(n ^ 2),n是位数).相反,现代bignum包使用离散傅立叶变换或数值变换将其转换为基本上O(n ln(n))的操作.

这只适用于整数.当你在某种类型的真实数字表示(log,sqrt,exp等)上进入更复杂的函数时,事情变得更加复杂.

如果您有一些理论背景,我强烈建议您阅读Yap的书"算法代数的基本问题"的第一章.如前所述,gmp bignum库是一个很好的库.对于实数,我使用了mpfr并喜欢它.

Answer 3

不要重新发明轮子:它可能会变成方形!

使用经过试用和测试的第三方库,例如GNU MP.