Divide and conquer binomial
Torbjorn Granlund
tg at gmplib.org
Thu Dec 22 18:42:52 CET 2011
bodrato at mail.dm.unipi.it writes:
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.
Nice, I didn't figure out how t ohave both exact divisions and balanced
multiplies.
When the difference is smaller, things are slightly different. The last
steps of binomial(123456789, 12345678) are:
545136 x 552463 -> 1097599 / 192901 -> 904698
Which are also very well balanced.
But the basecase now is quite a stupid one...
What is the branching factor? I.e., is the basecase invoked a number of
times linear in the data size, or superlinear (like in Toom multiply)?
--
Torbjörn
More information about the gmp-devel
mailing list