# 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
```