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
|
