Allocation for toom33

[bodrato at mail.dm.unipi.it]

Hi,

>   The intriguing thing is that the comment promises significantly less
>   scratch space than is currently used (and less even if we would
>   require s+t >= n + 5). Maybe it's just wrong.
>
> Probably.  Or we've pessimised memory usage since we wrote it.  :-)

I believe that mpn_toom3_mul_n (the "old" balanced only function) has a
better memory usage than the newer mpn_toom33_mul. This is not because of
the added flexibility of the unbalanced function, but depend on the
sequence of evaluations.

toom33 compute at first all the evaluations:
a(1), a(-1), a(2), b(1), b(-1), b(2);
then the products:
c(1) <-a(1)*b(1) ...

The old toom3_mul_n interlaces the operations above, possibly overwriting
a(1) when it computes a(2)... Maybe the comment comes from the old
implementation... Maybe we should better merge the ideas of the two
versions before removing the "old" one.

Regards,
Marco

-- 
http://bodrato.it/