CS¶ ↑

Computer Science Module for Ruby

This is a gem containing some algorithms useful for computer science and math. I’m writing it to teach myself how to write well-performing, well-structured Ruby code, as well as to get some practice maintaining a Ruby Gem (and, it must be said, to gain some little bit of visibility in the Ruby world).

The first version is very small, offering two algorithms to compute Fibonacci numbers:

Matrix exponentiation

This is the fastest way I’ve found to compute Fibonacci numbers.

It makes use of the fact that if M = Matrix[[0, 1], [1, 1]], then the lower right element of M**k contains the (k + 1)‘th Fibonacci number. This is very fast if the Matrix.** operation is optimized to use successive squaring rather than individual multiplications. Ruby’s implementation of Matrix.** does exactly this, fortunately.

Simple addition

This is a simple loop that computes F(n) by adding F(0) + F(1) + … + F(n - 1).

For n < 5000, this seems to perform about as well as the matrix exponentiation. But, thereafter it is MUCH slower (at least, in the benchmarks we performed).

Using CS¶ ↑

The algorithms are available as module methods, and you (currently) get all (two) of them by requiring ‘cs.rb’:

require 'rubygems'
require 'cs'
y = CS::fibonacci(6) # returns F(6) which is 8 = 5 + 3, using matrix algorithm by default

An optional parameter selects the algorithm to be used. By default, the matrix exponentiation algorithm is used. However, you can choose one or the other as follows:

y_more_slowly = CS::fibonacci(6, CS::ADDITION)

As a convenience, the method is also available as an instance mixin for the class Integer:

require 'rubygems'
require 'cs_fibonacci'
y = 6.fibonacci # use default algorithm
y_slower = 6.fibonacci(CS::ADDITION) # specify a different algorithm

Obtaining the gem from github¶ ↑

gem sources -a http://gems.github.com
gem install dgoldhirsch-cs

This is Still Half-Baked¶ ↑

Obviously, this is a beginner’s gem which is in an infant state. Comments and suggestions are very welcome.

CSW Web Application¶ ↑

In addition to learning how to write a decent gem, I wanted to write my first Ruby Web application. So, I wrote CSW which is a Web application that provides interactive testing of the CS library. It, too, is on github:

www.github.com/dgoldhirsch/csw

For now you can read its README there. When/if I finish it and get it hosted somewhere (e.g., heroku), you’ll be able to use it for yourself. I’m hoping that CSW will make it easy and fun for other programmers to extend and contribute to the CS library. CS will then be a real, open-source project!

Copyright¶ ↑

Copyright © 2009 David C. Goldhirsch. See LICENSE for details.