Divide and conquer binomial
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Thu Dec 22 13:42:37 CET 2011
Ciao,
Il Gio, 22 Dicembre 2011 12:44 pm, Torbjorn Granlund ha scritto:
> Very interesting! Nice apparent complexity. (Did you analyse it?)
Not yet.
> This code does not cope with non-zero remainders in any divisions,
> right?
All divisions it uses are exact.
> I ran out of time for the moment. I'd like to explore that idea in the
> future, though, since it makes for a very balanced computation.
When n >> k, my code uses almost balanced multiplications. In the last
steps of binomial(12345678901234567890123, 1234567) sizes are:
536203 x 536204 -> 1072406 / 19291 -> 1053116
I mean: multiply {536203 limbs} times {536204 limbs}, divexact the 1072406
limbs obtained by 19291, the final result is 1053116 limbs.
When the difference is smaller, things are slightly different. The last
steps of binomial(123456789, 12345678) are:
545136 x 552463 -> 1097599 / 192901 -> 904698
But the basecase now is quite a stupid one...
> I hacked a(nother) basecase n-over-k function, this time for small k
> This time, I think I finally obsolete the
> old code over the entire place, perhaps also your improved verson of it.
I'll test it, but I'm sure it is faster than my basecase.
Regards,
m
--
http://bodrato.it/software/
More information about the gmp-devel
mailing list