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

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

---

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

일반적인 전략은 숫자를 문자열로 얻은 다음 더 작은 숫자 (예 : 단일 숫자)로 나누고 배열에 배치하는 것임을 이해합니다. 이 시점에서 다양한 비교 연산자를 구현하는 것은 비교적 간단해야합니다. 내 주요 관심사는 덧셈과 곱셈과 같은 것들을 구현하는 방법입니다.

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

---

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

1. 수학 연산자 : +,-, /, *, % 클래스가 연산자의 양쪽에있을 수 있고, 연산자가 연결될 수 있으며, 피연산자 중 하나가 int, float, double 등이 될 수 있음을 잊지 마십시오. .

2. I / O 연산자 : >>, << 여기에서는 사용자 입력에서 클래스를 올바르게 생성하는 방법과 출력용으로 형식을 지정하는 방법을 알아 봅니다.

3. 변환 / 캐스트 : big int 클래스를 변환 할 수 있어야하는 유형 / 클래스를 파악하고 변환을 올바르게 처리하는 방법을 알아 봅니다. 빠른 목록에는 double 및 float가 포함되며 int (적절한 경계 검사 포함) 및 complex (범위를 처리 할 수 ​​있다고 가정)가 포함될 수 있습니다.

---

재미있는 도전. :)

임의 길이의 정수를 원한다고 가정합니다. 다음 접근 방식을 제안합니다.

"int"데이터 유형의 이진 특성을 고려하십시오. 간단한 이진 연산을 사용하여 CPU의 회로가 무언가를 추가 할 때 수행하는 작업을 에뮬레이션하는 것을 고려하십시오. 더 심도있는 관심이 있다면 반가산기 및 완전 가산기에 대한 위키피디아 기사를 읽어보십시오 . 당신은 그와 비슷한 일을하게 될 것입니다.하지만 당신은 저수준으로 내려갈 수 있습니다.하지만 게으 르기 때문에 저는 그저 포기하고 더 간단한 해결책을 찾을 것이라고 생각했습니다.

그러나 더하기, 빼기, 곱하기에 대한 알고리즘 세부 정보로 들어가기 전에 데이터 구조를 찾아 보겠습니다. 물론 간단한 방법은 std :: vector에 저장하는 것입니다.

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

고정 된 크기의 벡터를 만들 것인지 미리 할당 할 것인지 고려할 수 있습니다. 그 이유는 다양한 연산을 위해 벡터의 각 요소 인 O (n)을 거쳐야하기 때문입니다. 작업이 얼마나 복잡 할 지 직접 알고 싶을 수 있으며 고정 n이 바로 그 작업을 수행합니다.

그러나 이제는 숫자 연산에 대한 일부 알고리즘에 대해 설명합니다. 논리 수준에서 할 수 있지만 그 마법의 CPU 성능을 사용하여 결과를 계산할 것입니다. 그러나 Half-와 FullAdders의 논리 그림에서 우리가 인수 할 것은 운반을 다루는 방식입니다. 예를 들어 + = 연산자를 구현하는 방법을 고려하십시오 . BigInt <> :: value_의 각 숫자에 대해 추가하고 결과가 어떤 형태의 캐리를 생성하는지 확인합니다. 우리는 그것을 비트 단위로하지 않을 것이지만, BaseType의 특성 (long, int, short 등)에 의존합니다. 오버플로됩니다.

당연히 두 개의 숫자를 더하면 결과는 그 숫자 중 큰 숫자보다 커야합니다. 그렇지 않은 경우 결과가 오버플로되었습니다.

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

The other arithmetic operation go analogous. Heck, you could even use the stl-functors std::plus and std::minus, std::times and std::divides, ..., but mind the carry. :) You can also implement multiplication and division by using your plus and minus operators, but that's very slow, because that would recalculate results you already calculated in prior calls to plus and minus in each iteration. There are a lot of good algorithms out there for this simple task, use wikipedia or the web.

물론 다음과 같은 표준 연산자를 구현해야합니다 operator<<(value_의 각 값을 n 비트에 대해 왼쪽으로 이동하고 value_.size()-1... 에서 시작 하여 캐리를 기억하십시오 :) operator<.-여기에서 약간 최적화 할 수도 있습니다. size()첫 번째 와 대략적인 자릿수 . 등등. 그런 다음 befriendig std :: ostream으로 클래스를 유용하게 만드십시오 operator<<.

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

---

이것에 대한 완전한 섹션이 있습니다 : [컴퓨터 프로그래밍의 기술, vol.2 : Seminumerical Algorithms, section 4.3 Multiple Precision Arithmetic, pp. 265-318 (ed.3)]. 4 장, 산술에서 다른 흥미로운 자료를 찾을 수 있습니다.

정말로 다른 구현을보고 싶지 않다면 무엇을 배우고 싶습니까? 무수히 많은 실수를 저지르고이를 발견하는 것은 유익하고 위험합니다. 또한 중요한 컴퓨팅 경제를 식별하고 심각한 성능 문제를 방지하기위한 적절한 스토리지 구조를 갖추는 데 어려움이 있습니다.

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

(어떻게 수행하는지 보지 않고) 다른 구현을 테스트하기를 원할 수도 있지만, 엄청난 수준의 테스트를 기대하지 않고 일반화 할 수 있으려면 그 이상이 필요합니다. 실패 모드 (메모리 부족 문제, 스택 부족, 너무 오래 실행 등)를 고려하는 것을 잊지 마십시오.

즐기세요!

---

addition would probably have to be done in the standard linear time algorithm
but for multiplication you could try http://en.wikipedia.org/wiki/Karatsuba_algorithm

---

Once you have the digits of the number in an array, you can do addition and multiplication exactly as you would do them longhand.

---

Don't forget that you don't need to restrict yourself to 0-9 as digits, i.e. use bytes as digits (0-255) and you can still do long hand arithmetic the same as you would for decimal digits. You could even use an array of long.

---

I'm not convinced using a string is the right way to go -- though I've never written code myself, I think that using an array of a base numeric type might be a better solution. The idea is that you'd simply extend what you've already got the same way the CPU extends a single bit into an integer.

For example, if you have a structure

typedef struct {
    int high, low;
} BiggerInt;

You can then manually perform native operations on each of the "digits" (high and low, in this case), being mindful of overflow conditions:

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

It's a bit of a simplistic example, but it should be fairly obvious how to extend to a structure that had a variable number of whatever base numeric class you're using.

---

Like others said, do it to old fashioned long-hand way, but stay away from doing this all in base 10. I'd suggest doing it all in base 65536, and storing things in an array of longs.

---

Use the algorithms you learned in 1st through 4th grade.
Start with the ones column, then the tens, and so forth.

---

If your target architecture supports BCD (binary coded decimal) representation of numbers, you can get some hardware support for the longhand multiplication/addition that you need to do. Getting the compiler to emit BCD instruction is something you'll have to read up on...

The Motorola 68K series chips had this. Not that I'm bitter or anything.

---

My start would be to have an arbitrary sized array of integers, using 31 bits and the 32n'd as overflow.

The starter op would be ADD, and then, MAKE-NEGATIVE, using 2's complement. After that, subtraction flows trivially, and once you have add/sub, everything else is doable.

There are probably more sophisticated approaches. But this would be the naive approach from digital logic.

---

Could try implementing something like this:

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

You'd only need 4 bits for a single digit 0 - 9

So an Int Value would allow up to 8 digits each. I decided i'd stick with an array of chars so i use double the memory but for me it's only being used 1 time.

Also when storing all the digits in a single int it over-complicates it and if anything it may even slow it down.

I don't have any speed tests but looking at the java version of BigInteger it seems like it's doing an awful lot of work.

For me I do the below

//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

---

subtract 48 from your string of integer and print to get number of large digit. then perform the basic mathematical operation . otherwise i will provide complete solution.

참고URL : https://stackoverflow.com/questions/269268/how-to-implement-big-int-in-c