임의의 차량 산술 설명

StackOverflow https://stackoverflow.com/questions/1218149

  •  10-07-2019
  •  | 
  •  

문제

나는 C를 배우려고 노력하고 있으며 실제로 큰 숫자 (예 : 100 자리, 1000 자리 등)로 일할 수 없다는 것을 알게되었습니다. 나는 이것을 할 수있는 도서관이 존재한다는 것을 알고 있지만 직접 구현하려고 노력하고 싶습니다.

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

도움이 되었습니까?

해결책

숫자를 작은 부품으로 취급하는 것은 적절한 저장 및 알고리즘의 문제입니다. 컴파일러가 있다고 가정 해 봅시다. int 0-99 일만 할 수 있으며 최대 999999의 숫자를 처리하려고합니다 (간단하게 유지하기 위해 양수 숫자에 대해서만 걱정할 것입니다).

당신은 각각 3 번을 주어서 그렇게합니다 intS 및 동일한 규칙을 사용하여 초등학교에서 추가, 뺄셈 및 기타 기본 운영을 위해 배웠습니다.

임의의 정밀 라이브러리에는 메모리가 보유 할 수있는 모든 것을 나타내는 데 사용되는 기본 유형의 수에는 고정 제한이 없습니다.

예를 들어 첨가 : 123456 + 78:

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

가장 중요한 목적에서 작업 :

  • 초기 캐리 = 0.
  • 56 + 78 + 0 캐리 = 134 = 34 1 캐리
  • 34 + 00 + 1 캐리 = 35 = 35
  • 12 + 00 + 0 Carry = 12 = 12 0 캐리

이것은 실제로 추가가 CPU 내부의 비트 레벨에서 일반적으로 작동하는 방식입니다.

뺄셈은 비슷합니다 (기본 유형 및 기본 대신 차입을 사용하여), 반복 첨가물 (매우 느리게) 또는 교차 제품 (더 빠른)으로 곱셈을 수행 할 수 있으며 부서는 까다 롭지 만 숫자의 이동 및 뺄셈으로 수행 할 수 있습니다. 관련 (당신이 어린 시절에 배운 긴 분열).

실제로 제곱시 정수에 맞을 수있는 최대 10의 전력을 사용하여 이런 종류의 작업을 수행하기 위해 도서관을 작성했습니다 (2 개를 곱할 때 오버플로를 방지하기 위해 int16 비트와 같은 S int 제곱시 9,801 (<32,768)을 생성하기 위해 0-99로 제한되거나 32 비트 int 알고리즘을 크게 완화시키는 99,980,001 (<2,147,483,648)을 생성하기 위해 0 ~ 9,999를 사용합니다.

조심해야 할 몇 가지 요령.

1/ 숫자를 추가하거나 곱할 때 필요한 최대 공간을 사전 할당 한 다음 나중에 너무 많은 것을 발견하면 줄입니다. 예를 들어, 두 개의 100- "숫자"를 추가합니다 (여기서 숫자는 int) 숫자는 결코 101 자리 이상을 줄 수 없습니다. 12 자리 숫자에 3 자리 숫자를 곱하면 15 자리 이상이 생성되지 않습니다 (자리 계수 추가).

2/ 추가 속도의 경우 필요한 경우에만 숫자를 정규화 (저장소를 줄이십시오) - 내 라이브러리는이를 별도의 호출로 사용하여 사용자가 속도와 스토리지 문제를 결정할 수 있도록했습니다.

3/ 양수 및 음수의 추가는 뺄셈이며, 음수를 빼는 것은 동등한 양의 추가와 동일합니다. 부호를 조정 한 후 추가 및 빼기 메소드가 서로 호출하여 상당한 코드를 저장할 수 있습니다.

4/ 작은 숫자에서 큰 숫자를 빼지 마십시오.

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

대신 11에서 10을 빼고 부정하십시오.

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

다음은 내가해야 할 라이브러리 중 하나의 의견 (텍스트로 바뀌 었습니다)은 다음과 같습니다. 불행히도 코드 자체는 저작권이 있지만 4 가지 기본 작업을 처리하기에 충분한 정보를 선택할 수 있습니다. 다음과 같이 가정하십시오 -a 그리고 -b 음수를 나타냅니다 a 그리고 b 0 또는 양수입니다.

을 위한 덧셈, 징후가 다른 경우, 부정의 빼기를 사용하십시오.

-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 자리의 각 자릿수를 추출한 다음 (뒤로)를 사용하여 결과에 추가 할 값을 계산하기 위해 (초기에 0).

ShiftLeft 그리고 ShiftRight 작업은 빠르게 곱하거나 나누는 데 사용됩니다 LongInt 랩 값 ( "실제"수학의 경우 10)에 의해. 위의 예에서, 우리는 475 ~ 0 2 회 (32의 마지막 숫자)를 추가하여 950 (결과 = 0 + 950 = 950)을 얻습니다.

그런 다음 시프트 475를 떠나 4750과 오른쪽 시프트 32를 얻습니다.

왼쪽 시프트 4750, 47500, 오른쪽 시프트 3이 0을 얻습니다.

분할 또한 까다 롭지 만 초기 산술 ( "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 다중 정밀 산술 라이브러리 - 내 라이브러리보다 실질적으로 더 좋고 빠릅니다.

그것은 기억이 떨어지면 단순히 종료 될 것이라는 점에서 다소 불행한 오용이 있습니다 (내 의견으로는 범용 도서관에 대한 치명적인 결함).

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

나는 또한 Bods가 끝났다는 것을 알았습니다 인사 (GMP의 포크)는 잠재적 인 변화에 대한 토론에 더 적합합니다. 더 개발자 친화적 인 무리처럼 보입니다.

다른 팁

바퀴를 다시 발명하는 것은 개인적인 교화와 학습에 매우 좋습니다. 나는 당신을 그 중요한 운동과 내가 스스로 한 운동으로 설득하고 싶지는 않지만, 더 큰 패키지가 주소를 다루는 직장에서 미묘하고 복잡한 문제가 있다는 것을 알고 있어야합니다.

예를 들어, 곱셈. 순진하게, 당신은 '남학생'방법을 생각할 수 있습니다. 즉, 하나의 숫자를 다른 숫자 위에 쓰고 학교에서 배운대로 긴 곱셈을합니다. 예시:

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

그러나이 방법은 매우 느립니다 (O (n^2), n은 숫자 수입니다). 대신, 최신의 Bignum 패키지는 이산 푸리에 변환 또는 숫자 변환을 사용하여 이것을 본질적으로 O (N LN (N)) 작업으로 바꿉니다.

그리고 이것은 단지 정수를위한 것입니다. 숫자의 실제 표현 (로그, SQRT, Exp 등)에 대해 더 복잡한 기능을 할 때 상황이 훨씬 복잡해집니다.

이론적 배경을 원한다면 Yap의 첫 번째 장을 읽는 것이 좋습니다. "알고리즘 대수의 기본 문제". 이미 언급했듯이 GMP Bignum 라이브러리는 훌륭한 라이브러리입니다. 실수로 MPFR을 사용하여 좋아했습니다.

바퀴를 재발 명하지 마십시오 : 그것은 정사각형으로 판명 될 수 있습니다!

다음과 같은 타사 라이브러리를 사용하십시오 GNU MP, 그것은 시도하고 테스트됩니다.

당신은 기본적으로 연필과 종이로하는 것과 같은 방식으로 그것을합니다 ...

  • 숫자는 임의 크기를 취할 수있는 버퍼 (배열)로 표시됩니다 (이는 사용을 의미합니다. malloc 그리고 realloc) 필요에 따라
  • 언어 지원 구조를 사용하여 가능한 한 기본 산술을 구현하고 운반을 처리하고 수동으로 이동합니다.
  • 더 복잡한 기능으로 다루기위한 효율적인 주장을 찾기 위해 숫자 분석 텍스트를 검색합니다.
  • 필요한만큼만 구현합니다.

일반적으로 기본 계산 단위로 사용합니다.

  • 0-99 또는 0-255가 포함 된 바이트
  • 16 개의 비트 단어 Contaning Wither 0-9999 또는 0--65536
  • 32 개의 비트 단어가 포함되어 있습니다 ...
  • ...

건축에 의해 지시 된 바와 같이.

이진 또는 소수점 기본의 선택은 최대 공간 효율, 인간 가독성 및 칩에 이진 코드 소수 (BCD) 수학 지원의 존재에 대한 욕구에 따라 달라집니다.

고등학교 수준의 수학으로 할 수 있습니다. 더 많은 고급 알고리즘이 실제로 사용됩니다. 예를 들어 두 개의 1024 바이트 숫자를 추가하려면 다음과 같습니다.

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;
}

결과는 더 커야합니다 one place 추가 된 경우 최대 값을 관리합니다. 이거 봐요 :

9
   +
9
----
18

ttmath 배우고 싶다면 훌륭한 도서관입니다. C ++를 사용하여 제작되었습니다. 위의 예는 어리석은 예 였지만 이것이 일반적으로 추가 및 뺄셈이 수행되는 방식입니다!

주제에 대한 좋은 언급은입니다 수학 연산의 계산 복잡성. 구현하려는 각 작업에 얼마나 많은 공간이 필요한지 알려줍니다. 예를 들어, 두 가지가있는 경우 N-digit 숫자가 필요합니다 2N digits 곱셈의 결과를 저장합니다.

처럼 미치 말하자면, 그것은 구현하기 쉬운 일이 아닙니다! C ++를 알고 있다면 ttmath를 살펴 보는 것이 좋습니다.

궁극적 인 참고 문헌 중 하나는 Knuth의 Taocp Volume II입니다. 이 표현에 대한 숫자와 산술 연산을 나타내는 많은 알고리즘을 설명합니다.

@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},
}

당신이 큰 정수 코드를 직접 작성하고 싶다고 가정하면, 이것은 놀랍게도 간단 할 수 있습니다. 최근에 (Matlab에서도) 최근에 한 사람으로 말한 것입니다. 여기에 내가 사용한 몇 가지 요령이 있습니다.

  • 각 개인 소수 자리를 이중 번호로 저장했습니다. 이것은 많은 작업을 간단하게, 특히 출력으로 만듭니다. 원하는 것보다 더 많은 저장 공간을 차지하지만 메모리는 저렴하며 한 쌍의 벡터를 효율적으로 회피 할 수 있다면 곱셈을 매우 효율적으로 만듭니다. 또는 몇 가지 소수 자릿수를 두 배로 저장할 수 있지만 곱셈을 수행하는 컨볼 루션은 매우 많은 수의 수치 문제를 일으킬 수 있다고 조심하십시오.

  • 사인을 별도로 저장하십시오.

  • 두 숫자를 추가하면 주로 숫자를 추가 한 다음 각 단계에서 캐리를 확인하는 문제입니다.

  • 한 쌍의 곱셈은 컨볼 루션과 캐리 단계로 이어지는 것이 가장 좋습니다.

  • 숫자를 개별 10 진수 숫자로 저장하더라도, 결과에서 한 번에 약 13 자리 숫자를 얻기 위해 분할 (모드/rem ops)을 수행 할 수 있습니다. 이것은 한 번에 1 진수 숫자로만 작동하는 분할보다 훨씬 효율적입니다.

  • 정수의 정수 힘을 계산하려면 지수의 이진 표현을 계산하십시오. 그런 다음 반복 된 제곱 작업을 사용하여 필요에 따라 전력을 계산하십시오.

  • 많은 작업 (인수, 원시 테스트 등)은 PowerMod 작업의 혜택을받습니다. 즉, 모드 (a^p, n)를 계산할 때, p가 이진 형태로 표현 된 지수화의 각 단계에서 결과 모드 n을 줄입니다. 먼저 A^P를 계산하지 마십시오. 그런 다음 MOD N을 줄이려고 노력하십시오.

여기 PHP에서 한 간단한 (순진한) 예입니다.

"추가"및 "곱하기"를 구현하고 지수 예제에 사용했습니다.

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

코드 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);
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top