Re: Tuning Karatsuba in LibTomMath

From: Tom St Denis (
Date: 04/26/03

Date: 26 Apr 2003 04:42:18 -0700

Tim Josling <> wrote in message news:<>...
> Yes agree. I just wanted to be sure noone got the impression is was a
> bad piece of work.
> By the way,I found a comment in the 'lgorithms' section of the manual
> that the cutover to Karabatsu (or whatever it is) 'cn be as little as 8
> limbs'. This would translate to about 80+ digits, in the same ball park
> as you.

It's "Karatsuba" named after the guy who invented the technique and
co-authored a paper on it. According to

A "limb" is a single digit. So when they say "as little as 8 limbs"
they do mean 8 "digits" [by my fancy terminology].

> The cutover to FFT method was huge, thousands of digits.

Same for Toom-Cook.

Anyways, as I said in an earlier post the only obvious way for me to
speed up my Karatsuba routines is to implement inlined add/sub
routines. The problem is it would make the code overly bloat.
However, by doing so I can ditch the two mp_lshd at the end [and just
hard-wire the shift] which would save a bit of time.