C++에서 big int를 구현하는 방법

https://stackoverflow.com/questions/269268

06-07-2019
|

문제

나는 프로그래밍 연습으로 C++에서 big int 클래스, 즉 long int보다 큰 숫자를 처리할 수 있는 클래스를 구현하고 싶습니다.이미 여러 가지 오픈 소스 구현이 있다는 것을 알고 있지만 직접 작성하고 싶습니다.나는 올바른 접근 방식이 무엇인지 느끼려고 노력하고 있습니다.

일반적인 전략은 숫자를 문자열로 가져온 다음 더 작은 숫자(예: 한 자리 숫자)로 나누어 배열에 배치하는 것임을 이해합니다.이 시점에서는 다양한 비교 연산자를 구현하는 것이 상대적으로 간단합니다.나의 주요 관심사는 덧셈과 곱셈과 같은 것을 어떻게 구현하는가입니다.

실제 작업 코드가 아닌 일반적인 접근 방식과 조언을 찾고 있습니다.

해결책

큰 int 클래스에 대해 고려해야 할 사항:

수학 연산자:+, -, /, *, %는 클래스가 운영자의 양쪽에있을 수 있고, 운영자가 묶을 수 있고, 피연산자 중 하나가 int, float, double 등이 될 수 있다는 것을 잊지 마십시오.
I/O 연산자:>>, << 이것은 사용자 입력에서 클래스를 올바르게 작성하는 방법과 출력을 위해 포맷하는 방법을 알아냅니다.
전환/캐스트:큰 INT 클래스를 전환 할 수있는 유형/클래스와 변환을 올바르게 처리하는 방법을 알아 봅니다.빠른 목록에는 Double 및 Float가 포함되며 INT (적절한 경계 점검 포함) 및 복합체 (범위를 처리 할 수 있다고 가정)가 포함될 수 있습니다.

다른 팁

재미있는 도전. :)

나는 당신이 임의의 길이의 정수를 원한다고 가정합니다. 다음 접근법을 제안합니다.

데이터 유형 "int"의 이진 특성을 고려하십시오. 간단한 이진 작업을 사용하여 CPU의 회로가 물건을 추가 할 때하는 일을 모방하는 방법을 생각해보십시오. 더 깊이 관심이있는 경우 독서를 고려하십시오. 이 Wikipedia는 하프 어드더와 풀 어드데이션에 관한 기사입니다. 당신은 그와 비슷한 일을 할 것입니다. 그러나 당신은 그 정도처럼 낮은 수준으로 내려갈 수 있습니다. 그러나 게으르면, 나는 단지 더 간단한 솔루션을 찾아서 더 간단한 솔루션을 찾을 것이라고 생각했습니다.

그러나 추가, 빼기, 곱하기에 대한 알고리즘 세부 사항에 들어가기 전에 데이터 구조를 찾으십시오. 간단한 방법은 물론 사물을 std :: 벡터에 보관하는 것입니다.

template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};

고정 크기의 벡터를 만들고 Preallocate를 만들고 싶을 때 고려할 수 있습니다. 그 이유는 다양한 작업의 경우 벡터의 각 요소 -O (n)를 거쳐야합니다. 작업이 얼마나 복잡한 지 오프 핸드를 알고 싶을 수도 있고 고정 된 N이 바로 그 일을 할 수 있습니다.

그러나 이제 숫자에서 작동하는 일부 알고리즘에. 논리 수준으로 할 수는 있지만 우리는 그 마법 CPU 파워를 사용하여 결과를 계산합니다. 그러나 우리가 우리가 반과 풀 어드더의 논리 실조에서 인수하는 것은 그것이 운반을 다루는 방식입니다. 예를 들어, 어떻게 구현하는지 고려하십시오 += 연산자. bigint <> :: value_의 각 숫자에 대해, 당신은 그것들을 추가하고 결과가 어떤 형태의 캐리를 생성하는지 확인할 것입니다. 우리는 그것을 조금씩하지 않을 것이지만, 우리의베이스 타입의 본질에 의존합니다 (길거나 int 또는 짧거나 무엇이든) 오버플로됩니다.

분명히 두 숫자를 추가하면 결과는 그 숫자 중 하나보다 커야합니다. 그렇지 않으면 결과가 오버플로되었습니다.

template< class BaseType >
BigInt< BaseType >& BigInt< BaseType >::operator += (BigInt< BaseType > const& operand)
{
  BT count, carry = 0;
  for (count = 0; count < std::max(value_.size(), operand.value_.size(); count++)
  {
    BT op0 = count < value_.size() ? value_.at(count) : 0, 
       op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
    BT digits_result = op0 + op1 + carry;
    if (digits_result-carry < std::max(op0, op1)
    {
      BT carry_old = carry;
      carry = digits_result;
      digits_result = (op0 + op1 + carry) >> sizeof(BT)*8; // NOTE [1]
    }
    else carry = 0;
  }

  return *this;
}
// NOTE 1: I did not test this code. And I am not sure if this will work; if it does
//         not, then you must restrict BaseType to be the second biggest type 
//         available, i.e. a 32-bit int when you have a 64-bit long. Then use
//         a temporary or a cast to the mightier type and retrieve the upper bits. 
//         Or you do it bitwise. ;-)

다른 산술 작업은 유사합니다. 도대체, 당신은 stl-functors std :: plus 및 std :: 마이너스, std :: times 및 std :: divides를 사용할 수도 있지만 ... :) 플러스 및 마이너스 연산자를 사용하여 곱셈 및 분할을 구현할 수 있지만, 각 반복에서 Plus 및 Minus에 대한 이전 호출에서 이미 계산 한 결과를 다시 계산하기 때문에 매우 느립니다. 이 간단한 작업을위한 좋은 알고리즘이 많이 있습니다. 사용 위키 백과 또는 웹.

물론, 당신은 다음과 같은 표준 연산자를 구현해야합니다. operator<< (value_의 각 값을 왼쪽으로 이동하여 N 비트로 시작합니다. value_.size()-1... 오, 그리고 캐리를 기억하십시오 :), operator< - 여기서 조금 최적화하고 거친 수의 숫자를 확인할 수도 있습니다. size() 첫 번째. 등등. 그런 다음 Befriendig std :: Ostream으로 수업을 유용하게 만드십시오. operator<<.

이 접근법이 도움이되기를 바랍니다!

이것에 대한 전체 섹션이 있습니다. 4 장에서 다른 흥미로운 자료 인 산술을 찾을 수 있습니다.

다른 구현을 정말로보고 싶지 않다면 배우는 것이 무엇인지 고려 했습니까? 수많은 실수가 발생하고 그것을 발견하는 것은 유익하고 위험합니다. 중요한 계산 경제를 식별하고 심각한 성능 문제를 피하기위한 적절한 저장 구조를 갖는 데 어려움이 있습니다.

당신을위한 도전 질문 : 구현을 어떻게 테스트하려고하고, 산술이 정확하다는 것을 어떻게 증명하기 위해 어떻게 제안합니까?

당신은 다른 구현이 (그것을 어떻게하는지 보지 않고)에 대해 테스트하기를 원할 수도 있지만, 배출 수준의 테스트를 기대하지 않고 일반화 할 수있는 것보다 더 많은 시간이 걸릴 것입니다. 실패 모드를 고려하는 것을 잊지 마십시오 (메모리 문제, 스택에서, 너무 오래 실행되는 등).

재미있게 보내세요!

추가 선형 시간 알고리즘에서 추가가 완료되어야 할 것입니다.
그러나 곱셈을 위해 시도 할 수 있습니다 http://en.wikipedia.org/wiki/karatsuba_algorithm

배열에 숫자의 숫자가 있으면 외면 할 때와 같이 정확하게 추가 및 곱셈을 할 수 있습니다.

숫자로서 0-9로 제한 할 필요가 없다는 것을 잊지 마십시오. 즉, 바이트를 숫자로 사용하고 (0-255), 소수점 자릿수와 동일하게 장거리 산술을 할 수 있습니다. 당신은 길이의 배열을 사용할 수도 있습니다.

나는 문자열을 사용하는 것이 올바른 방법이라고 확신하지 않습니다. 나는 코드를 직접 작성한 적이 없지만 기본 숫자 유형의 배열을 사용하는 것이 더 나은 솔루션 일 수 있다고 생각합니다. 아이디어는 CPU가 단일 비트를 정수로 확장하는 것과 같은 방식으로 이미 얻은 것을 단순히 확장한다는 것입니다.

예를 들어, 구조가있는 경우

typedef struct {
    int high, low;
} BiggerInt;

그런 다음 오버플로 조건을 염두에두고 각 "숫자"(이 경우 높고 낮은)에서 기본 작업을 수동으로 수행 할 수 있습니다.

BiggerInt add( const BiggerInt *lhs, const BiggerInt *rhs ) {
    BiggerInt ret;

    /* Ideally, you'd want a better way to check for overflow conditions */
    if ( rhs->high < INT_MAX - lhs->high ) {
        /* With a variable-length (a real) BigInt, you'd allocate some more room here */
    }

    ret.high = lhs->high + rhs->high;

    if ( rhs->low < INT_MAX - lhs->low ) {
        /* No overflow */
        ret.low = lhs->low + rhs->low;
    }
    else {
        /* Overflow */
        ret.high += 1;
        ret.low = lhs->low - ( INT_MAX - rhs->low ); /* Right? */
    }

    return ret;
}

약간의 예제이지만 사용중인 기본 숫자 클래스의 가변 수를 가진 구조로 확장하는 방법이 상당히 분명해야합니다.

다른 사람들이 말했듯이, 오래된 방식으로 오래된 방식으로해야하지만베이스 10 에서이 모든 일을하지 않아도됩니다. 기본 65536에서 모든 일을하고 오랫동안 물건을 보관하는 것이 좋습니다.

1 학년에서 4 학년에서 배운 알고리즘을 사용하십시오.
열, TENS 등으로 시작하십시오.

대상 아키텍처가 숫자의 BCD (Binary Coded Decimal) 표현을 지원하는 경우해야 할 층 및 곱셈/추가에 대한 하드웨어 지원을받을 수 있습니다. 컴파일러가 BCD 명령을 방출하도록하는 것은 읽어야 할 것입니다 ...

Motorola 68K 시리즈 칩이 이것을 가지고있었습니다. 내가 쓰라린 것이 아니라는 것이 아닙니다.

나의 시작은 31 비트와 32n'd를 오버플로로 사용하는 임의 크기의 정수 배열을 갖는 것입니다.

스타터 OP는 2의 보완을 사용하여 추가 한 다음 음성을 추가합니다. 그 후, 뺄셈은 사소하게 흐르며, 일단 추가/서브가 있으면 다른 모든 것이 가능합니다.

아마도 더 정교한 접근법이있을 것입니다. 그러나 이것은 디지털 논리의 순진한 접근법 일 것입니다.

다음과 같이 구현할 수 있습니다.

http://www.docjar.org/html/api/java/math/biginteger.java.html

단일 숫자 0-9의 경우 4 비트 만 있으면됩니다.

따라서 int 값은 각각 최대 8 자리를 허용합니다. 나는 숯불 배열을 고수하기로 결정했기 때문에 메모리의 두 배를 사용하지만 나에게는 1 회 만 사용됩니다.

또한 모든 숫자를 단일 int에 저장할 때 과도하게 복합하고 어떤 것이라면 느려질 수도 있습니다.

나는 속도 테스트가 없지만 Biginteger의 Java 버전을 보면 끔찍한 일을하는 것처럼 보입니다.

나를 위해 나는 아래를한다

//Number = 100,000.00, Number Digits = 32, Decimal Digits = 2.
BigDecimal *decimal = new BigDecimal("100000.00", 32, 2);
decimal += "1000.99";
cout << decimal->GetValue(0x1 | 0x2) << endl; //Format and show decimals.
//Prints: 101,000.99

정수 문자열에서 48을 빼고 인쇄하여 큰 숫자를 얻으십시오. 그런 다음 기본 수학적 작업을 수행하십시오. 그렇지 않으면 완전한 솔루션을 제공 할 것입니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow