Re: Tuning Karatsuba in LibTomMath
From: Tom St Denis (tomstdenis_at_yahoo.com)
Date: 26 Apr 2003 04:42:18 -0700
Tim Josling <email@example.com> wrote in message news:<3EA92F89.firstname.lastname@example.org>...
> 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.