Re: Tuning Karatsuba in LibTomMath

From: Tim Josling (tej_at_melbpc.org.au_rubbish_at_nospam.com)
Date: 04/25/03


Date: Fri, 25 Apr 2003 22:52:25 +1000


> Tim Josling <tej_at_melbpc.org.au_rubbish@nospam.com> wrote in message news:<3EA7C914.3080905@nospam.com>...
>
>> I am sure I remember seeing this discussed in the info file - I
>> installed it as part of Red Hat Linux 8.0.
>>
>> I thought the source code was relatively good, considering the fact it
>> is performance oriented code and the algorithms are often quite complex.
>>
>> Certainly the library us fast and has performed flawlessly for me. I
>> also found it easy to use.
>
>
> I didn't question the quality of the results produced. Certainly GMP
> is fast and definitely well tested.
>
> My comparison is based on the fact that LibTomMath uses very similar
> algorithms but doesn't sacrifice too much in terms of code
> readibility.
>
> While GMP is tons faster LibTomMath [actually its normally 2 to 4
> times faster at best] it is a heck of a lot easier to build and use
> right out of the box [its also much smaller if you exclude the
> pre-built PDF manual]. The LibTomMath code is also much easier to
> read since there are no conditionals all over the place.
>
> As for API they are similar. I'd say LibTomMath is a bit simpler but
> it also doesn't provide quite as much. For instance, GMP provides
> both signed and unsigned single digit functions [akin to my mp_add_d,
> mp_mul_d, etc...]. Though all of LibTomCrypt's three public key
> algorithms use the LibTomMath API and I can say it worked out well :-)
>
> Tom

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.

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

Tim Josling



Relevant Pages

  • Re: str(bigint) is slow
    ... Probably too many digits to ... GNU's GMP developers spend their lives finding these tradeoffs, ... the cutoff for plain Karatsuba multiplication in Python is ... computing powers in a decimal-friendly base to begin with wins big by ...
    (comp.lang.python)
  • Re: ANNOUNCE: DJGPP port of GMP-4.3.1
    ... (your compile for /beta/): ... In both cases the task was to compute pi with 100000000 digits. ... I do not believe that compilation speed of GCC is noticeably dependant on optimization level of GMP. ... some constant expression, GCC tries to calculate value in compile time instead of genarating code ...
    (comp.os.msdos.djgpp)
  • Re: A Formula for Pi
    ... That's 100 base 10 digits from 327 terms. ... the unlimited precision rationals of GMP, ... I mainly use gmp in C++ programs, ... my program loop would do 4 arctan ...
    (sci.math)
  • Re: Tuning Karatsuba in LibTomMath
    ... > is performance oriented code and the algorithms are often quite complex. ... Certainly GMP ... My comparison is based on the fact that LibTomMath uses very similar ... algorithms use the LibTomMath API and I can say it worked out well :-) ...
    (sci.crypt)
  • Re: Long numbers programming
    ... This made it fairly easy to support 36 digits. ... Tiny does NOT use GMP. ... It calculates in floating point ...
    (comp.lang.cobol)