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.



98
99
100
101
102
103
104
105
106
107
 
# File 'lib/distribution/math_extension.rb', line 98

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.



86
87
88
 
# File 'lib/distribution/math_extension.rb', line 86

def result
  @result
end

Class Method Details

.naive_factorial(n) ⇒ Object 



154
155
156
 
# File 'lib/distribution/math_extension.rb', line 154

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

Instance Method Details

#bitcount(n) ⇒ Object 



89
90
91
92
93
94
95
96
97
 
# File 'lib/distribution/math_extension.rb', line 89

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 



143
144
145
146
147
148
149
150
 
# File 'lib/distribution/math_extension.rb', line 143

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 



151
152
153
 
# File 'lib/distribution/math_extension.rb', line 151

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

#recfactorial(n) ⇒ Object 



108
109
110
111
 
# File 'lib/distribution/math_extension.rb', line 108

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

#swing(n) ⇒ Object 



112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
 
# File 'lib/distribution/math_extension.rb', line 112

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