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, 109_395, 12_155, 230_945, 46_189,
969_969, 88_179, 2_028_117, 676_039, 16_900_975,
1_300_075, 35_102_025, 5_014_575, 145_422_675,
9_694_845, 300_540_195, 300_540_195]
SmallFactorial = 
[1, 1, 2, 6, 24, 120, 720, 5040, 40_320, 362_880,
3_628_800, 39_916_800, 479_001_600, 6_227_020_800,
87_178_291_200, 1_307_674_368_000, 20_922_789_888_000,
355_687_428_096_000, 6_402_373_705_728_000,
121_645_100_408_832_000, 2_432_902_008_176_640_000]

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(n) ⇒ SwingFactorial

Returns a new instance of SwingFactorial.



51
52
53
54
55
56
57
58
59
60
 
# File 'lib/distribution/math_extension.rb', line 51

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.



39
40
41
 
# File 'lib/distribution/math_extension.rb', line 39

def result
  @result
end

Class Method Details

.naive_factorial(n) ⇒ Object 



112
113
114
 
# File 'lib/distribution/math_extension.rb', line 112

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

Instance Method Details

#bitcount(n) ⇒ Object 



41
42
43
44
45
46
47
48
49
 
# File 'lib/distribution/math_extension.rb', line 41

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 &= 0x3f
  bc
end

#get_primorial(low, up) ⇒ Object 



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

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 



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

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

#recfactorial(n) ⇒ Object 



62
63
64
65
 
# File 'lib/distribution/math_extension.rb', line 62

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

#swing(n) ⇒ Object 



67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/distribution/math_extension.rb', line 67

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
        if q.odd?
          _p *= prime
        end
      end
      if _p > 1
        @prime_list[count] = _p
        count += 1
      end

    else
      if (n / prime).truncate.odd?
        @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