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.