Fastest way to use big numbers

Question

Is there any way to reasonably operate on very big integer numbers (millions or billions of digits)? The operations I would need to do are simple +, -, * and maybe /.

What I am looking for are algorithms to do the above operations in a reasonable time (say up to 1 hour on a modern PC). I don't mind using any type of representation for the numbers, but if I need a different representation for each operation, then conversion between the different representations should also be done in reasonable time.

All the big number libraries I have looked at completely break down when used for this size numbers. Is this a sign that no such algorithms exist, or just that these libraries representations/implementations are not optimized for such sizes?

EDIT The 1-hour limit is probably impossible. I gave that number since a simple loop over a billion iterations should take less than that, and I was hoping for an algorithm that would use O(n) time. Does a limit of 24-hours seem more reasonable?

Answer 1

You may wish to take a look at the DecInt Python class.

This is optimised for very long decimal integers. (The numbers are stored in a representation that makes it easy to convert to decimal digits in O(n) time).

It can do the operations you wish including:

1. Multiplication in O(n ln(n))
2. Division in O(n ln(n)^2)