gmp-impl.h assumes 32-bit unsigned int in fft_table_nk

[Niels Möller]

Robert Baruch <robert.c.baruch at gmail.com> writes:

> Thanks for the discussion! The fun thing is that I'll try to deal with
> integers on the order of 200 decimals (figure on the order of 700 bits). I
> think that mini-gmp is billed as "several orders of magnitude slower" than
> gmp on numbers over a few hundred bits, so I'd still like to see what gmp
> does (with --disable-fft).

It's going to be a smaller difference for platforms where the real gmp
lacks machine-specific assembly code. But lack of any subquadratic
multiplication in mini-gmp, in particular Karatsuba (aka Toom-2)
multiplication, will still slow it down for those sizes, I guess.

If you try mini-gmp, I'm very curious about your results.

I have only a little experience with 8-bit microcontrollers, but to get
good multiplication performance, I think you need to

1. Find a good multiplication primitive. Perhaps an 8-bit multiply
   instruction if you have one, or a tight shift-and-add-loop, or an
   8-bit squaring table.

2. Implement a tight mpn_addmul_1, using an 8-bit limb size.

3. Implement schoolbook-multiplication using the addmul_1 loop, and
   Karatsuba multiplication for some suitable threshold, perhaps as low
   as 32 or 48 bits (and if the threshold is low enough, consider
   specialized schoolbook-multiply functions for the few sizes you
   need).

See https://www.lysator.liu.se/~nisse/misc/6502-mul.html for some notes
I wrote a while ago.

If you're doing crypto, the next most important primitives are squaring
and montgomery redc.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.