2

Anyone know how to implement binomial coefficient calculation in parallel ? Any resource for multi-core or CUDA would be helpful, thank you.

Ang
  • 545
  • 5
  • 13
  • You know that `nCp = n! / (p! * (n - p)!)`, right? So why do you need parallelization? – tom Mar 02 '12 at 12:54
  • 1
    I think this question is a good start point : http://stackoverflow.com/questions/4256188/binomial-coefficient – Nic_tfm Mar 02 '12 at 13:09
  • @tom just want a fast way computing these coefficient, say n or p is very bit ? – Ang Mar 02 '12 at 13:26
  • 2
    @Ang: if n is "very big" how would a GPU with only native 64 bit integer and floating point types help you? Or are you planning on writing your own arbitary precision mathematical libraries as well? – talonmies Mar 02 '12 at 13:38
  • 2
    What is this used for? You can [easily](http://en.wikipedia.org/wiki/Stirling%27s_approximation) get a very good estimate for nCr in O(1). Depending on your application, this may or may not be "good enough" – BlueRaja - Danny Pflughoeft Mar 02 '12 at 15:58

1 Answers1

1

I would start off by doing the following.

  • Create an array of size (n + 1) and fill it with 1, 1, 2, 3, .... n.
  • Perform an inclusive scan on this array with a product operation. At this point you will have array[n] = n!. i.e. array[0] = 0!, array1 = 1! array[100] = 100! and so on.
  • Now that you have every factorial from 0! to n!, you can perform (n! / p! * (n - p)!) very easily.

The first and the last operations may need custom kernels. The second operation can be done using thrust and the inclusive_scan operation.

EDIT

As for the drawbacks, as mentioned above in the comments, there will be precison issues even with 64 bit integers at reasonable large size of n. But this is the basic algorithm that you would need to use.

Pavan Yalamanchili
  • 12,021
  • 2
  • 35
  • 55