Class: Distribution::MathExtension::SwingFactorial

Inherits:
Object
  • Object
show all
Defined in:
lib/distribution/math_extension.rb

Overview

Factorization based on Prime Swing algorithm, by Luschny (the king of factorial numbers analysis :P )

Reference

  • The Homepage of Factorial Algorithms. © Peter Luschny, 2000-2010

URL: www.luschny.de/math/factorial/csharp/FactorialPrimeSwing.cs.html

Constant Summary collapse

SmallOddSwing = 
[ 1, 1, 1, 3, 3, 15, 5, 35, 35, 315, 63, 693, 231, 3003, 429, 6435, 6435, 109395, 12155, 230945, 46189, 969969, 88179, 2028117, 676039, 16900975, 1300075, 35102025, 5014575,145422675, 9694845, 300540195, 300540195]
SmallFactorial = 
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000, 355687428096000, 6402373705728000, 121645100408832000, 2432902008176640000]

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(n) ⇒ SwingFactorial

Returns a new instance of SwingFactorial.



81
82
83
84
85
86
87
88
89
90
 
# File 'lib/distribution/math_extension.rb', line 81

def initialize(n)
  if (n<20)
    @result=SmallFactorial[n]
    #naive_factorial(n)
  else
  @prime_list=[]
  exp2 = n - bitcount(n);
  @result= recfactorial(n)<< exp2
  end
end

Instance Attribute Details

#result ⇒ Object (readonly)

Returns the value of attribute result.



69
70
71
 
# File 'lib/distribution/math_extension.rb', line 69

def result
  @result
end

Class Method Details

.naive_factorial(n) ⇒ Object 



137
138
139
 
# File 'lib/distribution/math_extension.rb', line 137

def self.naive_factorial(n)
  (2..n).inject(1) { |f,nn| f * nn }
end

Instance Method Details

#bitcount(n) ⇒ Object 



72
73
74
75
76
77
78
79
80
 
# File 'lib/distribution/math_extension.rb', line 72

def bitcount(n)
  bc = n - ((n >> 1) & 0x55555555);
  bc = (bc & 0x33333333) + ((bc >> 2) & 0x33333333);
  bc = (bc + (bc >> 4)) & 0x0f0f0f0f;
  bc += bc >> 8;
  bc += bc >> 16;
  bc = bc & 0x3f;
  bc
end

#get_primorial(low, up) ⇒ Object 



126
127
128
129
130
131
132
133
 
# File 'lib/distribution/math_extension.rb', line 126

def get_primorial(low,up)
  prod=1;
  Prime.each(up) do |prime|
    next if prime<low
    prod*=prime
  end
  prod
end

#naive_factorial(n) ⇒ Object 



134
135
136
 
# File 'lib/distribution/math_extension.rb', line 134

def naive_factorial(n)
  @result=(self.class).naive_factorial(n)
end

#recfactorial(n) ⇒ Object 



91
92
93
94
 
# File 'lib/distribution/math_extension.rb', line 91

def recfactorial(n)
  return 1 if n<2
  (recfactorial(n/2)**2) * swing(n)
end

#swing(n) ⇒ Object 



95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
# File 'lib/distribution/math_extension.rb', line 95

def swing(n)
  return SmallOddSwing[n] if (n<33)
  sqrtN = Math.sqrt(n).floor
  count=0
  
  Prime.each(n/3) do |prime|
    next if prime<3
    if (prime<=sqrtN)
      q=n
      _p=1
      
      while((q=(q/prime).truncate)>0) do
        if((q%2)==1)
          _p*=prime
        end
      end
      if _p>1
        @prime_list[count]=_p
        count+=1
      end
      
    else
      if ((n/prime).truncate%2==1)
        @prime_list[count]=prime
        count+=1
      end
    end
  end
  prod=get_primorial((n/2).truncate+1,n)
  prod * @prime_list[0,count].inject(1) {|ac,v| ac*v}
end