[m-rev.] for review: Add integer multiplication based on Karatsuba's algorithm

Matthias Güdemann matthias.gudemann at gmail.com
Sun Feb 23 22:54:25 AEDT 2014


Hi Paul and Julien,

I updated the PR on github with the changes suggested by Julien.

> Matthias, if you have any tests that you used to develop this I can add them
> to the test case.

I have tested the implementation here

https://github.com/mgudemann/mercury-contribs

(the implementation is named biginteger.m) where in biginttest.m I do
some calculation and compare the results to the current implementation
after conversion to strings to have a canonical representation. I will
provide some hardcoded inputs / outputs for the tests when I have some
time.

Most of the CPU time is now consumed in add_pairs. I wrote an
array-based implementation of add_pairs_equal, but this resulted in a
slight slow down. It seems that creating the array and converting to a
list afterwards takes more time than can be gained from using the
arrays.

So, with the exception of more complex algorithms like Toom-n or
Schönhage-Strassen for even larger numbers, I currently do not see
much obvious potential for further algorithmic optimization. Some
constant factors are possible, e.g., using more than 14 bits to reduce
the number of basic operations, but I am not sure if this is really
worth it. When I have some time, I will have a look at the integer
division code, maybe there is some optimization potential.

Cheers,
Matthias



More information about the reviews mailing list