Re: big number arithmetic

Felix von Leitner writes:
> Karatsuba starts to be useful (depending on the architecture) at
> 1024 bit numbers and up.

http://cr.yp.to/highspeed/fall2006.html includes a tutorial on writing
software for elliptic-curve arithmetic modulo 2^255-19 using 53-bit
floating-point operations. Here are the titles of three sections:

   Multiplication, schoolbook method: 121 fadd + 144 fmul.
   Multiplication, Karatsuba's method: 114 fadd + 142 fmul.
   Carrying and reduction modulo 2^255-19: 63 fadd + 11 fmul.

The code can be scheduled on typical CPUs to take one cycle per fadd, so
multiply-carry-reduce takes 184 cycles with schoolbook and 177 cycles
with Karatsuba, a noticeable speedup.

Of course, larger multipliers (64-bit floating-point, 128-bit integer,
etc.) mean larger numbers of bits before Karatsuba is worthwhile, but
slower multipliers (typical for 128-bit integer) mean smaller numbers. I
see the usual discrimination against Karatsuba et al. as an artifact of
the usual failure to schedule arithmetic operations sensibly.

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago