gmp-impl.h assumes 32-bit unsigned int in fft_table_nk
Niels Möller
nisse at lysator.liu.se
Sun Dec 20 20:43:57 UTC 2015
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.
More information about the gmp-bugs
mailing list