Robert Baruch <[email protected]> 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. _______________________________________________ gmp-bugs mailing list [email protected] https://gmplib.org/mailman/listinfo/gmp-bugs
