Algorithm for doing arithmetic operation on very l

Question

I need a algorithm to perform arithmetic operations on large numbers(that are way above range of float, double int or any other data type for that matter). I am required to write the code in C. I tried looking up here: Knuth, Donald, The Art of Computer Programming, ISBN 0-201-89684-2, Volume 2: Seminumerical Algorithms, Section 4.3.1: The Classical Algorithms but couldn't stand it. I just need the algorithm not the code.

Answer 1

For addition, as far as I know, you won't get much better than the simple linear O(n) algorithm, i.e., just add digit by digit. You likely, have to read the entire input anyway, so it's at least linear. You might be able to do various tricks to get the constant down.

Your main issue is going to be multiplication, due to the quadratic nature of the basic long multiplication algorithm. You might want to consider one of the several much faster methods given here. The Karatsuba method is a little tricky to implement nicely but is probably the easiest non-trivial algorithm that will give you a gain. Otherwise, you'll have to look a bit more into the Fast Fourier Transform methods, such as Schönhage-Strassen's algorithm or Fürer's algorithm.

See also Big O notation.

Answer 2

There is no algorithm to perform arithmetic operations on very large numbers. The arithmetic operations remains the same. What you need is in class like http://www.codeproject.com/KB/cs/BigInt.aspx

Answer 3

I think Karatsuba algorithm is best to perform arithmetic operations on large numbers.For sufficiently large n, another generalization, the Schönhage–Strassen algorithm, is even faster. You can look for the algorithm in Karatsuba or Karatsuba_Multiplication

Answer 4

For just the algorithms, read Knuth vol 2 or Crandall and Pomerance. For the coding, I would suggest getting the obvious algorithms working first before moving on to Karatsuba or Fourier transforms.

Answer 5

The book Prime Numbers and Computer Methods for Factorization by Riesel has an appendix with easy-to-read code for multiple-precision arithmetic.