New algorithm for cube (third power) computation
nisse at lysator.liu.se
Thu Apr 8 22:26:18 CEST 2010
nisse at lysator.liu.se (Niels Möller) writes:
> However, I think the cubing it can be used as a building block for 8th
> powers. Computing a^8 = (a1 x + a0)^8 using three levels of Karatsuba is
> 3 + 3*3 + 3*3*3 = 39 multiplications (or squarings) of size n.
Ooops, I get this very wrong. Three squarings would be done by Karatsuba followed by
Toom4 followed by Toom8, 3 + 7 + 15 = 25
> But we can compute
> a^3 7 nxn (according to your paper)
> a^2 1 nxn (Karatsuba, but a0^2 and a1^2 are already computed!)
> a^5 = a^3 * a^2 4 nxn (Toom32)
Should be 9 nxn (Toom64)
> a^8 = a^5 * a^3 7 nxn (Toom53)
Should be 15 nxn (Toom10x6)
Should be 32
So this is a very stupid way to do it. I realized something was wrong
when I noticed the "saving" in the first two "clever" steps implies that
we compute both a^3 and a^2 in the same number of operations as the old
way of computing a^3 (which also gives a^2 as an intermediate value).
Sorry for the confusion.
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-devel