임의 정밀도 산술 설명

임의 정밀도 산술 설명

---

저는 C를 배우려고하는데 정말 큰 숫자 (즉, 100 자리, 1000 자리 등)로 작업 할 수 없다는 것을 알게되었습니다. 이 작업을 수행하는 라이브러리가 있다는 것을 알고 있지만 직접 구현하려고합니다.

나는 누군가가 임의의 정밀도 산술에 대한 매우 상세하고 멍청한 설명을 가지고 있는지 또는 제공 할 수 있는지 알고 싶습니다.

---

숫자를 더 작은 부분으로 취급하는 것은 적절한 저장과 알고리즘의 문제입니다. an int이 0에서 99까지만 될 수 있는 컴파일러가 있고 999999까지의 숫자를 처리하려고 한다고 가정 해 봅시다 (여기서는 간단하게 유지하기 위해 양수에 대해서만 걱정하겠습니다).

int덧셈, 뺄셈 및 기타 기본 작업에 대해 초등학교에서 배웠어야하는 동일한 규칙을 사용하여 각 숫자에 3을주고 똑같은 규칙을 사용합니다.

임의 정밀도 라이브러리에서는 숫자를 나타내는 데 사용되는 기본 유형의 수에 고정 된 제한이 없습니다.

예를 들어 추가 : 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의 거듭 제곱을 사용하여 이러한 종류의 작업을 수행하는 라이브러리를 작성했습니다 ( int예를 들어 16 비트 int가 0에서 99로 제한되는 것과 같이 두 s를 곱할 때 오버플로를 방지하기 위해 제곱 할 때 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)

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.

---

While re-inventing the wheel is extremely good for your personal edification and learning, its also an extremely large task. I don't want to dissuade you as its an important exercise and one that I've done myself, but you should be aware that there are subtle and complex issues at work that larger packages address.

For example, multiplication. Naively, you might think of the 'schoolboy' method, i.e. write one number above the other, then do long multiplication as you learned in school. example:

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

but this method is extremely slow (O(n^2), n being the number of digits). Instead, modern bignum packages use either a discrete Fourier transform or a Numeric transform to turn this into an essentially O(n ln(n)) operation.

And this is just for integers. When you get into more complicated functions on some type of real representation of number (log, sqrt, exp, etc.) things get even more complicated.

If you'd like some theoretical background, I highly recommend reading the first chapter of Yap's book, "Fundamental Problems of Algorithmic Algebra". As already mentioned, the gmp bignum library is an excellent library. For real numbers, I've used mpfr and liked it.

---

Don't reinvent the wheel: it might turn out to be square!

Use a third party library, such as GNU MP, that is tried and tested.

---

You do it in basically the same way you do with pencil and paper...

• The number is to be represented in a buffer (array) able to take on an arbitrary size (which means using malloc and realloc) as needed
• you implement basic arithmetic as much as possible using language supported structures, and deal with carries and moving the radix-point manually
• you scour numeric analysis texts to find efficient arguments for dealing by more complex function
• you only implement as much as you need.

Typically you will use as you basic unit of computation

• bytes containing with 0-99 or 0-255
• 16 bit words contaning wither 0-9999 or 0--65536
• 32 bit words containing...
• ...

as dictated by your architecture.

The choice of binary or decimal base depends on you desires for maximum space efficiency, human readability, and the presence of absence of Binary Coded Decimal (BCD) math support on your chip.

---

You can do it with high school level of mathematics. Though more advanced algorithms are used in reality. So for example to add two 1024-byte numbers :

unsigned char first[1024], second[1024], result[1025];
unsigned char carry = 0;
unsigned int  sum   = 0;

for(size_t i = 0; i < 1024; i++)
{
    sum = first[i] + second[i] + carry;
    carry = sum - 255;
}

result will have to be bigger by one place in case of addition to take care of maximum values. Look at this :

9
   +
9
----
18

TTMath is a great library if you want to learn. It is built using C++. The above example was silly one, but this is how addition and subtraction is done in general!

A good reference about the subject is Computational complexity of mathematical operations. It tells you how much space is required for each operation you want to implement. For example, If you have two N-digit numbers, then you need 2N digits to store the result of multiplication.

As Mitch said, it is by far not an easy task to implement! I recommend you take a look at TTMath if you know C++.

---

One of the ultimate references (IMHO) is Knuth's TAOCP Volume II. It explains lots of algorithms for representing numbers and arithmetic operations on these representations.

@Book{Knuth:taocp:2,
   author    = {Knuth, Donald E.},
   title     = {The Art of Computer Programming},
   volume    = {2: Seminumerical Algorithms, second edition},
   year      = {1981},
   publisher = {\Range{Addison}{Wesley}},
   isbn      = {0-201-03822-6},
}

---

Assuming that you wish to write a big integer code yourself, this can be surprisingly simple to do, spoken as someone who did it recently (though in MATLAB.) Here are a few of the tricks I used:

• I stored each individual decimal digit as a double number. This makes many operations simple, especially output. While it does take up more storage than you might wish, memory is cheap here, and it makes multiplication very efficient if you can convolve a pair of vectors efficiently. Alternatively, you can store several decimal digits in a double, but beware then that convolution to do the multiplication can cause numerical problems on very large numbers.

• Store a sign bit separately.

• Addition of two numbers is mainly a matter of adding the digits, then check for a carry at each step.

• Multiplication of a pair of numbers is best done as convolution followed by a carry step, at least if you have a fast convolution code on tap.

• Even when you store the numbers as a string of individual decimal digits, division (also mod/rem ops) can be done to gain roughly 13 decimal digits at a time in the result. This is much more efficient than a divide that works on only 1 decimal digit at a time.

• To compute an integer power of an integer, compute the binary representation of the exponent. Then use repeated squaring operations to compute the powers as needed.

• Many operations (factoring, primality tests, etc.) will benefit from a powermod operation. That is, when you compute mod(a^p,N), reduce the result mod N at each step of the exponentiation where p has been expressed in a binary form. Do not compute a^p first, and then try to reduce it mod N.

---

Here's a simple ( naive ) example I did in PHP.

I implemented "Add" and "Multiply" and used that for an exponent example.

http://adevsoft.com/simple-php-arbitrary-precision-integer-big-num-example/

Code snip

// Add two big integers
function ba($a, $b)
{
    if( $a === "0" ) return $b;
    else if( $b === "0") return $a;

    $aa = str_split(strrev(strlen($a)>1?ltrim($a,"0"):$a), 9);
    $bb = str_split(strrev(strlen($b)>1?ltrim($b,"0"):$b), 9);
    $rr = Array();

    $maxC = max(Array(count($aa), count($bb)));
    $aa = array_pad(array_map("strrev", $aa),$maxC+1,"0");
    $bb = array_pad(array_map("strrev", $bb),$maxC+1,"0");

    for( $i=0; $i<=$maxC; $i++ )
    {
        $t = str_pad((string) ($aa[$i] + $bb[$i]), 9, "0", STR_PAD_LEFT);

        if( strlen($t) > 9 )
        {
            $aa[$i+1] = ba($aa[$i+1], substr($t,0,1));
            $t = substr($t, 1);
        }

        array_unshift($rr, $t);
     }

     return implode($rr);
}

참고URL : https://stackoverflow.com/questions/1218149/arbitrary-precision-arithmetic-explanation