Back to main page

Sent: Friday, October 06, 2000 3:58 PM
Subject: Karatsuba measurements

    I have been pondering using Karatsuba's algorithm in the
implementation of some cryptographic stuff, and your page
(and code) have indeed been very useful. The figures that
yuo quote are very nice, in the sense that a crossover at 16
digits would be great.

    Now I have run your code on three platforms I have ready
access to, and I thought you might be interested to learn the
results.

    For Linux on x86 the crossover seems to be around 64-digit
factors. For HP-UX on PA-RISC2.0, between 125 and 130
digits. In both cases the top optimization level was used. In
addition, I compiled under C, not C++.

    These results are somewhat disappointing in that one has
to go to quite a few digits before the advantages of Karatsuba
kick in. For both platforms above, Karatsuba becomes significantly
faster only when reaching some 250 (Linux) or 600 digits (HP-UX).

    Now results under IA64 are very spectacular. I have tested
under a Linux IA64 box and an HP-UX IA64 box. In the latter
case I couldn't get the top compiler optimization because the
compiler is still buggy at that level, but anyway:

    Karatsuba is faster even with as few as 7 digits. At the
cryptographically all-important 150 digit threshold Karatsuba
is some three times faster, and for 1000 digits more than six
times faster. I guess that the IA64 architecture, with instructions
to do vector integer multiplication, is better exploited by Karatsuba.