[math] 임의 정밀도 산술 설명

숫자를 더 작은 부분으로 취급하는 것은 적절한 저장과 알고리즘의 문제입니다. 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)

곱셈 은 다음과 같이 엔트리 레벨 수학을 사용합니다.

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를 사용하여 결과에 추가 할 값 (처음에는 0)을 계산하는 것입니다.

ShiftLeft그리고 ShiftRight연산은 a LongInt를 랩 값 ( “실제”수학의 경우 10) 으로 빠르게 곱하거나 나누는 데 사용됩니다 . 위의 예에서 475를 0에 2 번 더해 (32의 마지막 숫자) 950을 얻습니다 (결과 = 0 + 950 = 950).

그런 다음 475를 왼쪽으로 이동하여 4750을 얻고 32를 오른쪽으로 이동하여 3을 얻습니다. 4750을 0에 3 번 더하여 14250을 얻은 다음 950의 결과에 더하여 15200을 얻습니다.

47500을 얻으려면 4750을 왼쪽으로 시프트하고 0을 얻으려면 3을 오른쪽으로 시프트합니다. 오른쪽으로 시프트 된 32는 이제 0이므로 완료되었으며 실제로 475 x 32는 15200과 같습니다.

나누기 도 까다 롭지 만 초기 산술 ( “goes into”에 대한 “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

이는 드로 다운 변수 (처음에는 0)를 사용하여 12345의 세그먼트가 27보다 크거나 같을 때까지 한 번에 하나씩 가져옴으로써 구현됩니다.

그런 다음 27 미만이 될 때까지 27을 빼면됩니다. 빼기 횟수는 맨 윗줄에 추가 된 세그먼트입니다.

삭제할 세그먼트가 더 이상 없으면 결과가 있습니다.

---

이것은 매우 기본적인 알고리즘이라는 것을 명심하십시오. 숫자가 특히 클 경우 복잡한 산술을 수행하는 훨씬 더 좋은 방법이 있습니다. GNU Multiple Precision Arithmetic Library 와 같은 것을 살펴볼 수 있습니다. 이것은 제 라이브러리보다 훨씬 더 좋고 빠릅니다.

그것은 메모리가 부족하면 단순히 종료된다는 점에서 다소 불행한 잘못된 기능이 있습니다 (제 생각에는 범용 라이브러리의 경우 다소 치명적인 결함).

라이센스 이유로 사용할 수없는 경우 (또는 명백한 이유없이 응용 프로그램이 종료되는 것을 원하지 않기 때문에) 적어도 자체 코드에 통합하기위한 알고리즘을 얻을 수 있습니다.

나는 또한 MPIR (GMP의 포크)의 이사회 가 잠재적 인 변경 사항에 대한 토론에 더 적합 하다는 것을 발견했습니다 . 개발자 친화적 인 무리처럼 보입니다.