CSCE 222 Lecture 1

« previous | Wednesday, January 19, 2010 | next »

Introduction

We'll be using Ruby!!!!

… with a lot of math symbols

Fibonacci Numbers

$f_{n}={\begin{cases}0&n=0\\1&n=1\\f_{n-1}+f_{n-2}&n>1\end{cases}}$

def fib(n)
  return n if n <= 1
  fib(n-1) + fib(n-2)
end

11.times { |i| puts fib(i) }

how long will fib(40) take? (A long time)

Recursion and Benchmarking

• fib(n) calls f(n-1) and f(n-2)
  • fib(n-1) calls fib(n-2) and fib(n-3)
  • fib(n-2) calls fib(n-3) and fib(n-4)

f(n-3), for example, is called multiple times for duplication; time needed grows exponentially.

Exponential ratio eventually converges to the golden ratio:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{Time\left(f_n\right)}{Time\left(f_{n-1}\right)}\approx\frac{1+\sqrt{5}}{2}\approx1.618033988}

A better function

def fib(n)
  return n if n <= 1
  @res ||= fib(n-1) + fib(n-2)
end

Dramatic speed enhancement

Even better function

@res = []
def fib(n)
  return n if n <= 1
  @res[n] ||= fib(n-1) + fib(n-2)
end