Divide and conquer binomial

[bodrato at mail.dm.unipi.it]

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/