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

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.



48
49
50
51
52
53
54
55
56
57
 
# File 'lib/distribution/math_extension.rb', line 48

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.



36
37
38
 
# File 'lib/distribution/math_extension.rb', line 36

def result
  @result
end

Class Method Details

.naive_factorial(n) ⇒ Object 



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

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

Instance Method Details

#bitcount(n) ⇒ Object 



38
39
40
41
42
43
44
45
46
 
# File 'lib/distribution/math_extension.rb', line 38

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 



94
95
96
97
98
99
100
101
 
# File 'lib/distribution/math_extension.rb', line 94

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 



103
104
105
 
# File 'lib/distribution/math_extension.rb', line 103

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

#recfactorial(n) ⇒ Object 



59
60
61
62
 
# File 'lib/distribution/math_extension.rb', line 59

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

#swing(n) ⇒ Object 



64
65
66
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
 
# File 'lib/distribution/math_extension.rb', line 64

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
        _p *= prime if q.odd?
      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