Releasing Toom-8.5 (mpn level)

[bodrato at mail.dm.unipi.it]

Hi,

> It is not perfect, yet! There are some _itch functions, but I'd not trust
> them...

Some doubts about _itch functions:

I'm trying with the balanced case, here is what I can prove:
#define mpn_toom6h_mul_n_itch(n) ( n*2 + GMP_NUMB_BITS*6 )
#define mpn_toom8h_mul_n_itch(n) ( ((n*15)>>3) + GMP_NUMB_BITS*6 )

... but the proof uses an assumption: toomK will use toomK for recursion.

Obviously the proof is correct also if toomK use some other function in
its recursion and this function needs _less_ preallocated memory than
toomK...

... but toom8h_itch(n) = 15/8*n +o(n) < 2*n + o(n) = toom6h_itch(n)

What about lower degree? I take the numbers from the latest gmp-impl.h
toom22_itch(n) =   2*n + o(n)
toom33_itch(n) = 5/2*n + o(n)
toom44_itch(n) =   3*n + o(n)

This means that the formulas above are correct if I use mpn_mul_n for
recursion, but they are not if I directly use toomXX_mul and pass the
preallocated scratch area.
Suggestions? Should I add toom44_itch() computed on the threshold point?
Should I use toom44_itch() for higher degree Toom too?

Regards,
Marco

-- 
http://bodrato.it/