What data structure should be used with arbitrarily large integers?

Question

Possible duplicate:
What data structure should be used to create your own BigInteger class?

Out of sheer interest, I'm trying to create a type that can contain an arbitrarily large integer. I want to support four basic operations [+, -, *, /] and optimize the speed of these operations.

I was thinking of some kind of doubly linked list and bit flag to indicate a positive or negative value. But I'm not quite sure how to add, for example, a large number of different sizes. Should I go to the last element of both numbers and then go back (using the second backward pointer to the previous element).

  123456789 // one large number
 + 123 // another large number with different size

Providing I can have arbitrarily large memory, what is the best data structure for this task?

I would appreciate a little hint and any comments on the worst complexity of arithmetic operations. Thanks!

Answer 1

Usually in this case one could use an array / vector, possibly a little-endian (first low word). If you perform operations on the spot, use a constant coefficient when growing the array, then the amortized complexity for the redistribution remains O (1).

All operations must be performed at O ​​(n) runtime, where n is the size of the input. EDIT : No, of course, more is needed for multiplication and separation, this answer says that it is at least O (N log N).

Just out of curiosity: Why are you redefining the wheel? Find a Java implementation here . C # also has .NET 4.0. Although it can be a good exercise to implement it myself (I remember how I did it once), if you just need functionality, then this is already in many computing environments.