How to Handle Arbitrarily Large Integers

How to get arbitrarily large numbers in c++?

Use a Bignumber library, I prefer TTMath for its simplicity. You can find it here Link to tttmath. TTTmath allows for operation on large numbers but You may need to make your own toString method.

Here is an example of TTTmath in use from their Samples page:

#include <ttmath/ttmath.h>
#include <iostream>

int main()
{
ttmath::UInt<2> a,b,c;

    a = "1234";
    b = 3456; 
    c = a*b;

    std::cout << c << std::endl;
}
Listing nr 1

What data structure to use with arbitrarily large integer numbers?

Usually one would go for an array/vector in this case, perhaps little-endian (lowest-significant word first). If you implement in-place operations, use a constant factor when growing the array, then amortized complexity for the reallocation remains O(1).

All operations should be doable in O(n) run time where n is the size of the input. EDIT: No, of course, multiplication and division will need more, this answer says it's at least O(N log N).

Just out of curiosity: Why are you reimplementing the wheel? Find here an implementation in Java. C# has one with .NET 4.0, too. While it might be a good exercise to implement this yourself (I remember myself doing it once), if you just need the functionality then it's there in many computing environments already.

Related Topics