任意精度算术说明 [英] Arbitrary-precision arithmetic Explanation

问题描述

我正在尝试学习 C，但遇到了无法处理非常大的数字(即 100 位、1000 位等)的问题.我知道存在可以执行此操作的库，但我想尝试自己实现它.

我只想知道是否有人已经或可以提供对任意精度算术的非常详细、简化的解释.

解决方案

将数字视为较小部分的充分存储和算法完全是问题.假设您有一个编译器，其中 int 只能是 0 到 99，并且您想处理最大为 999999 的数字(为了简单起见，我们在这里只关心正数).

你可以通过给每个数字三个 int 并使用你在小学时(应该已经)学到的加法、减法和其他基本运算的相同规则来做到这一点.

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

加法例如:123456 + 78:

12 34 5678—— —— ——12 35 34

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

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

事实上，这就是加法通常在 CPU 内部位级的工作方式.

减法是类似的(使用基类型的减法和借位而不是进位)，乘法可以通过重复加法(非常慢)或叉积(更快)来完成，除法更棘手，但可以通过移位和减法来完成所涉及的数字(你小时候学过的长除法).

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

需要注意的一些技巧.

1/数字相加或相乘时，预先分配所需的最大空间，如果发现太多，稍后再减少.例如，添加两个 100-"digit"(其中 digit 是 int)数字永远不会超过 101 位数字.将 12 位数字乘以 3 位数字永远不会产生超过 15 位的数字(加上数字计数).

2/为了提高速度，仅在绝对必要时才对数字进行标准化(减少所需的存储空间)——我的图书馆将此作为单独的调用，以便用户可以在速度和存储问题之间做出决定.

3/正负数相加就是减法，负数相减就等于正数相加.通过在调整符号后让加法和减法方法相互调用，您可以节省相当多的代码.

4/避免从小数字中减去大数字，因为你总是得到这样的数字:

<代码> 1011--- -- -- --99 99 99 99(你还有借钱).

相反，从 11 中减去 10，然后将其取反:

1110-——1(然后否定得到-1).

这是我必须为之执行此操作的其中一个库中的注释(已转换为文本).不幸的是，代码本身是受版权保护的，但您可能能够挑选出足够的信息来处理四个基本操作.假设下面的 -a 和 -b 代表负数，而 a 和 b 是零或正数.

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

-a + b 变成 b - aa + -b 变成 a - b

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

 a - -b 变成 a + b-a - b 变成 -(a + b)

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

small - big 变成 -(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 大于 1 或 12，所以我们首先使用 123.108 27 进入 123 4 次，4 x 27 = 108，123 - 108 = 15.---154 打倒 4.135 27 进入 154 5 次，5 x 27 = 135，154 - 135 = 19.---195 打倒 5.189 27 进入 195 7 次，7 x 27 = 189，195 - 189 = 6.---6 没有什么可以降低的了，所以停下来.

因此 12345/27 是 457 余数 6.验证:

<代码> 457 x 27 + 6= 12339 + 6= 12345

这是通过使用回撤变量(初始为零)将 12345 的段一次减少一个直到它大于或等于 27 来实现的.

然后我们简单地从中减去 27，直到低于 27 - 减去的数量是添加到顶行的部分.

当没有更多的段要降低时，我们就有了结果.

<小时>

请记住，这些是非常基本的算法.如果您的数字特别大，则有更好的方法来进行复杂的算术运算.您可以查看类似 GNU Multiple Precision Arithmetic Library 之类的内容 - 它比我自己的库要好得多，速度也快得多.

它确实有一个相当不幸的缺陷，因为如果内存不足，它会简单地退出(在我看来，这是通用库的一个相当致命的缺陷)但是，如果你能看过去，它非常擅长什么确实如此.

如果您因许可原因无法使用它(或者因为您不希望您的应用程序无缘无故退出)，您至少可以从那里获取算法以集成到您自己的代码中.

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

I'm trying to learn C and have come across the inability to work with REALLY big numbers (i.e., 100 digits, 1000 digits, etc.). I am aware that there exist libraries to do this, but I want to attempt to implement it myself.

I just want to know if anyone has or can provide a very detailed, dumbed down explanation of arbitrary-precision arithmetic.

解决方案

It's all a matter of adequate storage and algorithms to treat numbers as smaller parts. Let's assume you have a compiler in which an int can only be 0 through 99 and you want to handle numbers up to 999999 (we'll only worry about positive numbers here to keep it simple).

You do that by giving each number three ints and using the same rules you (should have) learned back in primary school for addition, subtraction and the other basic operations.

In an arbitrary precision library, there's no fixed limit on the number of base types used to represent our numbers, just whatever memory can hold.

Addition for example: 123456 + 78:

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

Working from the least significant end:

• initial carry = 0.
• 56 + 78 + 0 carry = 134 = 34 with 1 carry
• 34 + 00 + 1 carry = 35 = 35 with 0 carry
• 12 + 00 + 0 carry = 12 = 12 with 0 carry

This is, in fact, how addition generally works at the bit level inside your CPU.

Subtraction is similar (using subtraction of the base type and borrow instead of carry), multiplication can be done with repeated additions (very slow) or cross-products (faster) and division is trickier but can be done by shifting and subtraction of the numbers involved (the long division you would have learned as a kid).

I've actually written libraries to do this sort of stuff using the maximum powers of ten that can be fit into an integer when squared (to prevent overflow when multiplying two ints together, such as a 16-bit int being limited to 0 through 99 to generate 9,801 (<32,768) when squared, or 32-bit int using 0 through 9,999 to generate 99,980,001 (<2,147,483,648)) which greatly eased the algorithms.

Some tricks to watch out for.

1/ When adding or multiplying numbers, pre-allocate the maximum space needed then reduce later if you find it's too much. For example, adding two 100-"digit" (where digit is an int) numbers will never give you more than 101 digits. Multiply a 12-digit number by a 3 digit number will never generate more than 15 digits (add the digit counts).

2/ For added speed, normalise (reduce the storage required for) the numbers only if absolutely necessary - my library had this as a separate call so the user can decide between speed and storage concerns.

3/ Addition of a positive and negative number is subtraction, and subtracting a negative number is the same as adding the equivalent positive. You can save quite a bit of code by having the add and subtract methods call each other after adjusting signs.

4/ Avoid subtracting big numbers from small ones since you invariably end up with numbers like:

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

Instead, subtract 10 from 11, then negate it:

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

Here are the comments (turned into text) from one of the libraries I had to do this for. The code itself is, unfortunately, copyrighted, but you may be able to pick out enough information to handle the four basic operations. Assume in the following that -a and -b represent negative numbers and a and b are zero or positive numbers.

For addition, if signs are different, use subtraction of the negation:

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

For subtraction, if signs are different, use addition of the negation:

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

Also special handling to ensure we're subtracting small numbers from large:

small - big becomes -(big - small)

Multiplication uses entry-level math as follows:

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

The way in which this is achieved involves extracting each of the digits of 32 one at a time (backwards) then using add to calculate a value to be added to the result (initially zero).

ShiftLeft and ShiftRight operations are used to quickly multiply or divide a LongInt by the wrap value (10 for "real" math). In the example above, we add 475 to zero 2 times (the last digit of 32) to get 950 (result = 0 + 950 = 950).

Then we left shift 475 to get 4750 and right shift 32 to get 3. Add 4750 to zero 3 times to get 14250 then add to result of 950 to get 15200.

Left shift 4750 to get 47500, right shift 3 to get 0. Since the right shifted 32 is now zero, we're finished and, in fact 475 x 32 does equal 15200.

Division is also tricky but based on early arithmetic (the "gazinta" method for "goes into"). Consider the following long division for 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.

Therefore 12345 / 27 is 457 with remainder 6. Verify:

  457 x 27 + 6
= 12339    + 6
= 12345

This is implemented by using a draw-down variable (initially zero) to bring down the segments of 12345 one at a time until it's greater or equal to 27.

Then we simply subtract 27 from that until we get below 27 - the number of subtractions is the segment added to the top line.

When there are no more segments to bring down, we have our result.

---

Keep in mind these are pretty basic algorithms. There are far better ways to do complex arithmetic if your numbers are going to be particularly large. You can look into something like GNU Multiple Precision Arithmetic Library - it's substantially better and faster than my own libraries.

It does have the rather unfortunate misfeature in that it will simply exit if it runs out of memory (a rather fatal flaw for a general purpose library in my opinion) but, if you can look past that, it's pretty good at what it does.

If you cannot use it for licensing reasons (or because you don't want your application just exiting for no apparent reason), you could at least get the algorithms from there for integrating into your own code.

I've also found that the bods over at MPIR (a fork of GMP) are more amenable to discussions on potential changes - they seem a more developer-friendly bunch.

这篇关于任意精度算术说明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！