1

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.

tshepang
  • 12,111
  • 21
  • 91
  • 136
Tom Helinski
  • 11
  • 1
  • 2
  • For homework, you can use a linked-list as a large number. A single node in the list will hold a single digit of the number. – Bart Kiers Aug 05 '11 at 06:49
  • You can always reverse engineer existing libraries like GMP (http://gmplib.org/) or Java's `BigInteger` class. The source code is available at http://www.java2s.com/Open-Source/Java-Document/6.0-JDK-Core/math/java/math/BigInteger.java.htm. – Ray Toal Aug 05 '11 at 06:50
  • 7
    How would you, the human, perform an arithmetic operation on very large numbers? There's your algorithm, at least a starting point... – Jeff Mercado Aug 05 '11 at 06:51
  • 1
    @Ray Toal: I don't think you need to reverse-engineer open source code ;) – Sebastian Mach Aug 05 '11 at 07:39
  • 1
    Heh, bad choice of words then.... the OP wants just an algorithm and it can be gleaned from reading source code. Should have said "you could _infer_ an algorithm from this existing code." Good point, though. It is always valuable to be precise! +1 – Ray Toal Aug 05 '11 at 07:46
  • Did any of the answers help or do you still have questions? – MGwynne Aug 18 '11 at 20:44

5 Answers5

3

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.

MGwynne
  • 3,512
  • 1
  • 23
  • 35
  • 1
    I implemented in C a simple FFT based multiplication (~Fürer's method) as a 1st year university student, for a school project. There is some interesting material in Numerical Recipes, and it is not very hard. – Alexandre C. Aug 05 '11 at 07:23
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

Code Lღver
  • 15,573
  • 16
  • 56
  • 75
Gopesh Sharma
  • 6,730
  • 4
  • 25
  • 35
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

cprogrammer
  • 5,503
  • 3
  • 36
  • 56
1

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

lhf
  • 70,581
  • 9
  • 108
  • 149
0

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.

rossum
  • 15,344
  • 1
  • 24
  • 38