Ruby beats them all

ruby-talk
21

this one is in haskell:

fibonacci n = round((phi ** (x + 1) - (1 - phi) ** (x + 1)) / (sqrt 5))
  where phi = (1 + sqrt 5) / 2
        x = (fromInteger n)::Float

22

Matt O'Connor wrote:

jwesley wrote:

If Ruby properly handled tail-recursion, then the "accumulator passing"
style work for any number:

def fib n
  fib_helper( n, 1, 1)
end

def fib_helper n, next_val, val
  n < 1 ? val : fib_helper( n-1, next_val + val, next_val)
end

the above code (in accumulator-passing style) only works through about
n=1300 for me.

Though a more "functional approach" is to hide the helper function:

def fib n
  def fib_helper n, next_val, val
    n < 1 ? val : fib_helper( n-1, next_val + val, next_val)
  end
  fib_helper( n, 1, 1)
end

An alternative implementation might even use only one subroutine.

def fib n, p1 =1, p2 =1
  n < 1 ? p2 : fib( n - 1, p1 + p2, p1 )
end

23

Sadly, that doesn't really hide the helper function. fib_helper will be at the same scope as fib, Ruby doesn't currently do nested function definitions.

···

On Dec 15, 2005, at 8:46 PM, Matt O'Connor wrote:

jwesley wrote:

If Ruby properly handled tail-recursion, then the "accumulator passing"
style work for any number:
def fib n
  fib_helper( n, 1, 1)
end
def fib_helper n, next_val, val
  n < 1 ? val : fib_helper( n-1, next_val + val, next_val)
end
the above code (in accumulator-passing style) only works through about
n=1300 for me.

Though a more "functional approach" is to hide the helper function:

def fib n
  def fib_helper n, next_val, val
    n < 1 ? val : fib_helper( n-1, next_val + val, next_val)
  end
  fib_helper( n, 1, 1)
end

Matt

24

i'm sorry for reviving an old topic, but hows this:

def fib(n)
    list=[0,1]
    2.upto(n-1) do |s|
        list << (list[s-2]+list[s-1])
    end
    list
end

greetings, Dirk.

25

fibs :: [Int]
fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]

E

···

On 2005.12.16 11:51, "ako..." <akonsu@gmail.com> wrote:

this one is in haskell:

fibonacci n = round((phi ** (x + 1) - (1 - phi) ** (x + 1)) / (sqrt 5))
  where phi = (1 + sqrt 5) / 2
        x = (fromInteger n)::Float