Re: Tuning Karatsuba in LibTomMath

From: Tom St Denis (tomstdenis_at_yahoo.com)
Date: 04/26/03


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

Tim Josling <tej_at_melbpc.org.au_rubbish@nospam.com> wrote in message news:<3EA92F89.9050909@nospam.com>...
> 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

http://www.swox.com/gmp/manual/Nomenclature-and-Types.html#Nomenclature%20and%20Types

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.

Tom