7 Years
Discussion Span
Last Post by tyrantbrian

You can use the Karatsuba Fast Multiplication algorithm for this purpose. We normally employ this algorithm for cryptographic systems, where we need to multiply large numbers in the range of several thousand digits. Please refer to Wikipedia for the algorithm. http://en.wikipedia.org/wiki/Multiplication_algorithm#Karatsuba_multiplication. You can also read this tutorial better understanding - http://www.mpi-inf.mpg.de/~mehlhorn/ftp/chapter2A-en.pdf

Following is a source code that I found after googling. It shows how MPI can be used to perform Karatsuba Multiplication Algorithm in parallel. The code appears in GnuPG as a MPI helper function. Here is the link of the post http://www.stillhq.com/gpg/source-1.0.3/mpi/mpih-mul.html

There are many other large number multiplication algorithms (source: Wikipedia) that you could use like

* Gauss's complex multiplication algorithm.
* Toom–Cook.
* Fourier transform methods.
* Linear time multiplication.
* Quarter square multiplier.
* Polynomial multiplication.

Edited by tyrantbrian: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.