How to implement big int in C++

问题:

I\'d like to implement a big int class in C++ as a programming exercise—a class that can handle numbers bigger than a long int. I know that there are several open source implementations out there already, but I\'d like to write my own. I\'m trying to get a feel for what the right approach is.

I understand that the general strategy is get the number as a string, and then break it up into smaller numbers (single digits for example), and place them in an array. At this point it should be relatively simple to implement the various comparison operators. My main concern is how I would implement things like addition and multiplication.

I\'m looking for a general approach and advice as opposed to actual working code.

回答1:

Things to consider for a big int class:

1. Mathematical operators: +, -, /, *, % Don\'t forget that your class may be on either side of the operator, that the operators can be chained, that one of the operands could be an int, float, double, etc.

2. I/O operators: >>, << This is where you figure out how to properly create your class from user input, and how to format it for output as well.

3. Conversions/Casts: Figure out what types/classes your big int class should be convertible to, and how to properly handle the conversion. A quick list would include double and float, and may include int (with proper bounds checking) and complex (assuming it can handle the range).

回答2:

A fun challenge. :)

I assume that you want integers of arbitrary length. I suggest the following approach:

Consider the binary nature of the datatype \"int\". Think about using simple binary operations to emulate what the circuits in your CPU do when they add things. In case you are interested more in-depth, consider reading this wikipedia article on half-adders and full-adders. You\'ll be doing something similar to that, but you can go down as low level as that - but being lazy, I thought I\'d just forego and find a even simpler solution.

But before going into any algorithmic details about adding, subtracting, multiplying, let\'s find some data structure. A simple way, is of course, to store things in a std::vector.

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

You might want to consider if you want to make the vector of a fixed size and if to preallocate it. Reason being that for diverse operations, you will have to go through each element of the vector - O(n). You might want to know offhand how complex an operation is going to be and a fixed n does just that.

But now to some algorithms on operating on the numbers. You could do it on a logic-level, but we\'ll use that magic CPU power to calculate results. But what we\'ll take over from the logic-illustration of Half- and FullAdders is the way it deals with carries. As an example, consider how you\'d implement the += operator. For each number in BigInt<>::value_, you\'d add those and see if the result produces some form of carry. We won\'t be doing it bit-wise, but rely on the nature of our BaseType (be it long or int or short or whatever): it overflows.

Surely, if you add two numbers, the result must be greater than the greater one of those numbers, right? If it\'s not, then the result overflowed.

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.

And of course, you should implement standard operators such as operator<< (just shift each value in value_ to the left for n bits, starting at the value_.size()-1... oh and remember the carry :), operator< - you can even optimize a little here, checking the rough number of digits with size() first. And so on. Then make your class useful, by befriendig std::ostream operator<<.

Hope this approach is helpful!

回答3:

There\'s a complete section on this: [The Art of Computer Programming, vol.2: Seminumerical Algorithms, section 4.3 Multiple Precision Arithmetic, pp. 265-318 (ed.3)]. You may find other interesting material in Chapter 4, Arithmetic.

If you really don\'t want to look at another implementation, have you considered what it is you are out to learn? There are innumerable mistakes to be made and uncovering those is instructive and also dangerous. There are also challenges in identifying important computational economies and having appropriate storage structures for avoiding serious performance problems.

A Challenge Question for you: How do you intend to test your implementation and how do you propose to demonstrate that it\'s arithmetic is correct?

You might want another implementation to test against (without looking at how it does it), but it will take more than that to be able to generalize without expecting an excrutiating level of testing. Don\'t forget to consider failure modes (out of memory problems, out of stack, running too long, etc.).

Have fun!

回答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

回答5:

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

回答6:

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.

回答7:

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.

回答8:

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.

回答9:

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

回答10:

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.

回答11:

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.

回答12:

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

回答13:

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.

回答14:

C++ class BigInt that enables the user to work with arbitrary precision integers. http://sourceforge.net/projects/cpp-bigint/