Wraparound multiplicaton vs mullo

[bodrato at mail.dm.unipi.it]

Ciao,

> When I wrote that, what I meant was that I saw no way to evaluate in
> polynomial roots without extending to a ring where computation is a
> lot more expensive. x^2 + 1 is ok because we can extend to Z[i], where
> we can do two points (i and -i) with three multiplicatons over the
> original, so it's only 50% more expensive. I can't do anything similar

But Karatsuba uses three multiplications anyway, and 0 and oo are simpler
than +/- i.

>   M'(n) = M'(n/2) + M(n/2) + O(n)
>         = ... = M(n/2) + M(n/4) + M(n/2^k) + M'(n/2^k) + O(n)

> Looks fairly good to me, but it's unclear to me if and when it's going
> to be better than the non-recursive x^4-1 algorithm (5 M(n/4) + O(n))

When M(n/2) uses Karatsuba
M'(n)= M(n/2) + M(n/4) + M'(n/4) + O(n) = 3 M(n/4) + M(n/4) + M'(n/4) + O(n)
And... if M'(n/4) < M(n/4), this is probably faster than the non-recursive.
When M(n/2) does not use Karatsuba, then M(n/2) < 3M(n/4) ...

Obviously, the O(n) can hide some surprises :-) and the recursion level
depend on the $k$ such that 2^k|n ...

Regards,
Marco

-- 
http://bodrato.it/papers/