Divide and conquer binomial

[Torbjorn Granlund]

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