Arbitrary- precision算术说明 [英] Arbitrary-precision arithmetic Explanation

问题描述

我想学习C和所遇到的无法与真正的大数字工作（即100位，1000位等）。我知道存在库要做到这一点，但我想尝试实现它自己。

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.

我只是想知道如果任何人有或能提供arbitrary- precision算术非常详细的，简单化的解释。

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

推荐答案

这是足够的贮存和算法来处理数字作为更小的部分的所有问题。让我们假设你有一个编译器，其中一个 INT 只能是0到99，你要处理的人数达到999999（我们只担心正数这里继续简单）。

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).

您做到这一点通过给每个第三 INT 和使用同样的规则，你（应该有）了解到早在小学的加法，减法和其他基本操作

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.

在任意precision库，有上用来重新present我们的数字基础类型的数量没有固定的限制，只是什么内存可容纳的。

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.

增加，例如： 123456 + 78 ：

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

从最显著结束工作：

Working from the least significant end:

• 初始利差= 0。


• 56 + 78 + 0套利= 134 = 34 1执行


• 34 + 00 + 1 =携带35 = 35 0套利


• 12 + 00 + 0套利= 12 = 12 0套利

这是，事实上，如何增加一般工作在你的CPU内的电平。

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).

其实我已经写库使用10个最大功率时的平方（以prevent溢出乘以两个 INT s ^在一起，如16位 INT 被限制在0到99来产生9,801（小于32,768）的平方的时候，还是32位的 INT 0使用通过9,999生成99980001（小于2,147,483,648）。），这大大缓解了算法

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.

一些技巧，需要提防。

1 /相加或相乘的数字时，pre-分配再后来减少，如果你觉得这太过分了所需要的最大空间。例如，将两个百通数字（其中数字是 INT ）号码将永远不可能给你超过101位。乘以一个3位数绝不会产生超过15位的12位数字（添加数字计数）。

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 /为了增加速度，规范（减少所需的存储）的数字只有在绝对必要的 - 我的图书馆有这个作为一个单独的呼叫，使用户可以速度和存储问题之间决定

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 /加成的正和负号的是减法，并减去一个负数是相同的添加相当于阳性。您可以通过具有附加节省相当多code的加减法调整的迹象后，打电话给对方。

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 /避免由小减去大的数字，因为你总是像数字结束了：

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).

相反，10减去11，然后否定它：

Instead, subtract 10 from 11, then negate it:

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

下面是我必须为做到这一点的图书馆之一的意见（变成文本）。在code本身，不幸的是，受版权保护的，但你可以挑选出足够的信息来处理的四个基本操作。假设在下面的 -a 和 -b 重新present负数和一个和 b 0或正数。

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

在此实现方式涉及然后使用添加到计算的值被添加到的结果（初始为零）一次（向后）提取的每一个的32个1的数字。

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 和 ShiftRight 操作用于快速乘或除一个 LongInt的由包值（10真正的数学）。在上面的例子中，我们添加475到零的2倍（32最后一位），以获得950（结果= 0 + 950 = 950）。

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).

然后我们左移475获得4750和右移32获得3.添加4750至零3次获得14250再加入导致950获得15200。

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.

左移4750得到47500，右移3得到0。由于右移32现在是零，我们就完蛋了，事实上475×32等于做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.

的科的也是棘手，但基于早期的算法（对于gazinta法进入）。请考虑以下长除法27分之12345：

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.

所以27分之12345是 457 与其余 6 。验证：

  457 x 27 + 6
= 12339    + 6
= 12345

这是通过使用牵伸变量（最初零），以降低12345之一的段在一个时间，直到它的大于或等于27实施

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.

然后我们简单地减去从27直到我们得到如下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.

请这些都是pretty基本算法。有更好的方法来做到复杂的算术，如果你的号码将是特别大。你可以看看像 GNU多precision运算库的 - 这是大大超过我自己的图书馆更好，更快

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.

它确实有这相当不幸的不好的特性便索性退出，如果它运行的内存，但是，（在我看来通用库，而致命的缺陷），如果你能看过去的，这是pretty擅长它做什么。

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.

如果你不能将其用于许可证的原因（或者是因为你不想让你的应用程序只是退出没有明显的原因），你至少可以得到算法，从那里集成到您自己的code。

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.

我还发现，超过的BOD在 MPIR （GMP的一个分支）有更适合的潜在变化的讨论 - 他们似乎更开发者友好的一群。

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.

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