Module: CS

Defined in:
lib/cs.rb

Overview

Title

Computer Science Library for Ruby

Author

David C. Goldhirsch

Copyright © 2009, David C. Goldhirsch

Constant Summary collapse

MATRIX =

Fibonacci Algorithms

:matrix
ADDITION = 
:addition
Fibonacci_algorithms = 
[MATRIX, ADDITION]

Class Method Summary collapse

Class Method Details

.additive_fibonacci(n) ⇒ Object

This is a simple, additive loop to compute F(n) by computing F(0) + F(1) + … + F(n-1). Our spotty benchmark/profiling suggests that this is always worse in CPU time and general response time than the linear_matrix_fibonacci algorithm. (And, surprisingly, this seems to be true even for very low values of n.) We provide it for purposes of information, and as a point of comparison for performance.



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

def self.additive_fibonacci(n)
  return 0 if n <= 0
  b = 0 # F(0)
  result = 1 # F(1)
  (n - 1).times do
    a = b
    b = result
    result += a # i.e., result = a + b
  end
  return result
end

.fibonacci(n, algorithm = MATRIX) ⇒ Object

Generalized Fibonacci generator. Return the integer value of F(n) for any integer n, where F(0) = 0 F(1) = 1 F(k > 1) = F(k - 1) + F(k - 2) Starting with F(0), the first few Fibonacci values are 0, 1, 1, 2, 3, 5, 8, …

Usage: CS::fibonacci(anInteger, aSymbol = CS::MATRIX) in which anInteger is any integer (but anything less than 0 will be interpreted as 0), and aSymbol optionally specifies the algorithm to be used. See this module’s Fibonacc_algorithms constant for the possible algorithm names. By default, the fastest known algorithm will be used.



27
28
29
30
31
32
33
 
# File 'lib/cs.rb', line 27

def self.fibonacci(n, algorithm = MATRIX)
  # The following seems to be the fastest algorithm, perhaps because
  # Ruby's Matrix.** operation is smart enough to use squares of squares
  # to minimize the number of multiplications.
  return matrix_fibonacci(n) if algorithm == MATRIX
  return additive_fibonacci(n) if algorithm == ADDITION
end

.lower_right(matrix) ⇒ Object

Matrix utility to return the lower, right-hand element of a given matrix.



37
38
39
40
 
# File 'lib/cs.rb', line 37

def self.lower_right matrix
  return nil if matrix.row_size == 0
  return matrix[matrix.row_size - 1, matrix.column_size - 1]
end

.matrix_fibonacci(n) ⇒ Object

Matrix exponentiation algorithm to compute Fibonacci numbers. Let M be Matrix [[0, 1], [1, 1]]. Then, the lower right element of M**k is F(k + 1). In other words, the lower right element of M is F(2) which is 1, and the lower right element of M**2 is F(3) which is 2, and the lower right element of M**3 is F(4) which is 3, etc.

This is a good way to compute F(n) because the Ruby implementation of Matrix.** uses an O(log n) optimized algorithm (*). Computing M**(n-1) is actually faster (**) than using a simple while/for loop to compute F(0) + F(1) + … + F(n-1).

We found this algorithm in Introduction To Algorithms (Second Edition), by Cormen, Leiserson, Rivest, and Stein, MIT Press (mitpress.mit.edu), in exercise 3-31 on pages 902, 903.

(*) Ruby’s Matrix.**(k) works by computing partial = ((m**2)**2)… as far as possible, and then multiplying partial by M**(the remaining number of times). E.g., to compute M**19, compute partial = ((M**2)**2) = M**16, and then compute partial*(M**3) = M**19. That’s only 3 matrix multiplications of M to compute M*19.

(**) “Faster” means on the workstations we tried, the matrix algorithm takes less total time (see Ruby’s Benchmark::bmbm) than a simple, additive loop. But the space complexity may well be larger for the matrix algorithm, which in turn may affect the likelihood of garbage collection in large cases. Therefore, as with almost everything else, a different algorithm may be better suited to any particular environment or situation. This is why we provide the optional, alternative algorithms.



68
69
70
71
72
73
 
# File 'lib/cs.rb', line 68

def self.matrix_fibonacci(n)
  return 0 if n <= 0 # F(0)
  return 1 if n == 1 # F(1)
  # To get F(n >= 2), compute M**(n - 1) and extract the lower right element.
  return CS::lower_right(M**(n - 1))
end