File: binomial_coefficient.rb

package info (click to toggle)
ruby-distribution 0.7.3+dfsg-1
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, sid, stretch
  • size: 624 kB
  • ctags: 379
  • sloc: ruby: 4,283; makefile: 7
file content (56 lines) | stat: -rw-r--r-- 1,199 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
$:.unshift(File.expand_path(File.dirname(__FILE__)+"/../lib"))
require 'distribution'
require 'bench_press'

extend BenchPress



samples=10.times.map {|i| 2**(i+1)}

name 'binomial coefficient: multiplicative, factorial and optimized factorial methods'
author 'Claudio Bustos'
date '2011-01-27'
summary "Exact calculation of Binomial Coefficient could be obtained using multiplicative, pure factorial or optimized factorial algorithm (failing + factorial). 
Which one is faster?

Lower k is the best for all 
k=n/2 is the worst case.

The factorial method uses the fastest Swing Prime Algorithm."

reps 10 #number of repetitions

x=100

n=100
k=50



measure "Multiplicative" do
  samples.each do |n|
    [5,n/2].each do |k|
      k=[k,n-k].min
      (1..k).inject(1) {|ac, i| (ac*(n-k+i).quo(i))}
    end
  end
end

measure "Pure Factorial" do
  samples.each do |n|
    [5,n/2].each do |k|
      k=[k,n-k].min
      Math.factorial(n).quo(Math.factorial(k) * Math.factorial(n - k))
    end
  end
end

measure "Failing factorial + factorial" do
  samples.each do |n|
    [5,n/2].each do |k|
      k=[k,n-k].min
      (((n-k+1)..n).inject(1) {|ac,v| ac * v}).quo(Math.factorial(k))
    end
  end
end