Tetrahedral Numbers

Here's another one from Programming Praxis this one on tetrahedral numbers. I'll leave you to read the description and just jump straight into the ruby solution. The interesting thing here is to use a lambda to create a method that we can pass around. Here's the entire program ...

def linear(target, f)
    n = 1
    while ( f.call(n) != target)
        n = n + 1
    end
    n
end

def binary(target, f)
    low, high = 1, 2
    while (f.call(high) < target) do high = high*2 end
    mid = (high + low) / 2
    while (fmid = f.call(mid)) != target do
        fmid < target ?  (low, mid = mid, (mid + high) / 2) : (high, mid = mid, (low + mid) / 2)
    end
    mid
end


tetrahedral = lambda { |n| n * (n + 1) * (n + 2) / 6 }

1.upto(10) { |i| puts tetrahedral.call(i) }

puts linear(169179692512835000, tetrahedral)
puts binary(169179692512835000, tetrahedral)

We start out with two methods linear and binary which are pretty straightforward with the exception that both take a function (in this case f) as a parameter. For linear, we start at 1 and continue calling f until the value of f(n) is the same as target. binary is similar, but here we keep doubling the high value until we're above the target and then we calculate the fmid and use it as a high or low value until we converge.

The tetrahedral function itself is created with a lambda so that we can pass it to the other two methods. The next lines are simply tests. Note how much longer the linear method takes than the binary.

As always, let me know if you have questions or comments.