BloggEd

Ok, maybe the title has a bit too much grandeur in it, but let me get to the point.

One of Ruby’s major strength lies in it’s use of blocks. They allow the programmer to benefit from lazy evaluation, or to use the proper CS term, closures.

When dealing with mathematical formulas, I’d like to express those as naturally as possible. Last when I had to solve certain problem dealing with recurrence, I immediately thought of how easy it would be to express sigma (sum) and pi (product) expressions in Ruby. For example, one should be able to count sum of all integers in the range [1 .. 100] by saying something like (sorry, no MathML or images)

∑ (1 .. 100) i

With Ruby, you could just say (1..100).inject(0) {|acc, i| acc +i}. Rails even has the helper sum(). (And if you didn’t sleep at your math class, you know that Gauss could compute the answer in his head and come up with the right answer (101*50 = 5050) in a split second.)

However, to be able to evaluate expressions repeatedly with new values for each summation index, you can’t just stash the expression in a variable and use that with inject (because the expression is usually dependent on index).

Enter closures through Ruby blocks.

1
2
3
4
5

module MathExt
  def sigma(range, &block)
    range.inject(0) {|sum, i| sum + block.call(i)} 
  end
end

Now you can sum more complex stuff as well, like sigma(50..100) {|i| 1.0/(2*(i+1))}. The crucial point here is that the expression 1.0/(2*(i+1)) is not evaluated in the calling program before entering sigma definition, but once for each element in range. Closures are very powerful—using them one can take advantage of deferred evaluation, where different parts of the expression belong to separate contexts. The expression is evaluated inside the sigma method, but using the partial context of caller (everything in the expression except the variable i)

Implementing product (Π) would be equally easy:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

module MathExt
  def sigma(range, &block)
    range.inject(0) {|sum, i| sum + block.call(i)} 
  end

  def pi(range, &block)
    range.inject(1) {|prod, i| prod*block.call(i)}
  end
end
...
irb(main) > include MathExt
=> Object
irb(main) > pi(1..5) {|i| i+2}
=> 60

Ok, maybe sigma and especially pi are not that good names for the methods, but I didn’t bother to think of better names at the moment. Gotta dig Ruby, huh?

A bit fancier: often one of the bounds in an expression is infinity. The problem is that you can’t just iterate through Infinite number of entries. On the other hand, trying to deduce actual outcome by finding out limes expression would be quite hard programming wise. So, one solution would be to bail out after successive iterations differ only by a very tiny amount. Then we could do something like the following (assuming we use RSpec):

1
2
3
4

  include MathExt
  # compute well-known value of series 1 + 1/2 + 1/4 + 1/8 + ... + 1/n
  res = sigma(0..INF, :threshold => 0.000001) {|i| 2.0**-i}  
  res.should be_close(2.0, 0.00001) # => true

We were able to do that with the simple definition of sigma:

1
2
3
4
5
6
7
8
9
10
11
12
13

  INF = 1.0/0 # Ruby way of expressing infinity
  EPSILON = 1.0E-9 # default epsilon

  def sigma(range, opts={}, &block)
    sum = prev = 0
    threshold = opts[:threshold] || EPSILON
    range.each {|i|
      sum += block.call(i)
      break if (sum-prev).abs < threshold
      prev = sum
    } 
    sum
  end

There’s still one obvious problem. If the expression isn’t bound by some limit and INF is used, the method never returns. Another caveat is that when you use INF in the end of the range. the function concerned is expected to be monotonic, ie. it should be either non-increasing or non-decreasing, otherwise breaking out after the epsilon delta becomes small enough could return an erroneous result.

That said, I still believe that given methods could be useful for certain tasks.