New algorithm for cube (third power) computation

[Niels Möller]

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)
>                  ----

>                   19
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

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