Releasing Toom-8.5 (mpn level)
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Fri Oct 30 17:11:08 CET 2009
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/
More information about the gmp-devel
mailing list