On Jul 13, 2006, at 3:48 PM, Robert D. wrote:
which means that you have to compute 2**n (2 is an approximation of
sqrt(5)), right?
which is O(?) ?
sqrt(5) can be pre-computed.
– Elliot T.
On 7/14/06, Douglas McNaught [email protected] wrote:
I challange this, as there is no algorithm to compute c**n in O(1) it is
O(log n).OT, but…
Classroom Resources - National Council of Teachers of Mathematics
-Doug
which means that you have to compute 2**n (2 is an approximation of
sqrt(5)), right?
which is O(?) ?
On 7/14/06, Elliot T. [email protected] wrote:
Given you have an reasonably exact approximation of the square
Classroom Resources - National Council of Teachers of Mathematics
-Doug
which means that you have to compute 2**n (2 is an approximation of
sqrt(5)), right?
which is O(?) ?sqrt(5) can be pre-computed.
obviously my didactic powers are limited 
In order to compute f(n), you need to compute sqrt(5)**n, which is O(log
n).
Cheers
Robert
– Elliot T.
–
Deux choses sont infinies : l’univers et la bêtise humaine ; en ce qui
concerne l’univers, je n’en ai pas acquis la certitude absolue.
- Albert Einstein
BTW How would I then access $fib to puts an output of the sequence eg. 0
1 1 2 3 5 8 13 etc.
The best I could do was something like:
printf("Enter a number: “)
i = gets
puts “The #{i.to_i} Fibonacci number is #{fib(i.to_i)} "
0.upto(i.to_i){|k| printf(” #{$fib[k]}”) }
Daniel M. wrote:
“Erik V.” [email protected] writes:
You could use “case” as well (see version 2). It’s faster.
Using an ordinary if…else (without the elsif part) is faster
(see version 3). And version 4 is once again faster.4 is faster than 3 is faster than 2 is faster than 1…
All of these suffer from the problem that they make approximately fib(n)
function calls to compute fib(n). Why not remember the value of
fib(n) the ruby way, with a Hash that computes it naturally?$fib = Hash.new{|h,k| h[k] = h[k-2] + h[k-1]}
$fib[0] = 0
$fib[1] = 1def fib(n)
$fib[n]
endThis will be faster, and O(n), rather than O(fib(n)). Also note that
the base cases of 0 and 1 are handled simply and declaratively without
messing up the main body of the code.(Of course, now someone will respond with one of the O(log(n))
algorithms for computing fib(n))
Well whilst my orginal exercise was just to get recursion working in
ruby, I have to say this solution is very quick to calculate any result
and is recursive in a way that is quite “foriegn” to me. The problem for
me is that I find it difficult to understand what is happening in this
code. I would have though the stack would collapse due to referencing
something that is not defined yet. eg. h[k-2] for example in the intial
state of the $fib hash would not be found unless the k was 3 or 2. eg
$fib(30) would return "I dont have any thing to reference for h[30] =
h[28] + h[29], has h[28] and h[29] havent been defined.
BTW How would I then access $fib to puts an output of the sequence eg. 0
1 1 2 3 5 8 13 etc.
On 7/14/06, Glenn C. [email protected] wrote:
code. I would have though the stack would collapse due to referencing
something that is not defined yet. eg. h[k-2] for example in the intial
state of the $fib hash would not be found unless the k was 3 or 2. eg
$fib(30) would return "I dont have any thing to reference for h[30] =
h[28] + h[29], has h[28] and h[29] havent been defined.
The block form of Hash.new calls the block for every
nonexistent-hash-key access. So $fib[30] looks for the key 30, doesn’t
find it, and calls the block instead, passing it $fib and 30. The
block tries to return h[29] + h[28], but since they don’t exist
either, the calls to [] will again call the block, and so on.
martin
i = gets
puts “The #{i.to_i} Fibonacci number is #{fib(i.to_i)} "
0.upto(i.to_i){|k| printf(” #{$fib[k]}") }
maybe
fib = Hash.new{|h,k| h[k] = h[k-2] + h[k-1]}
fib[0], fib[1] = 0, 1
print "Enter a number: "
i = gets.to_i
puts “The #{i} Fibonacci number is #{fib[i]}”
puts (0…i).map{|k| fib[k]}.join(’ ')
cheers
Simon
fr simon:
puts (0…i).map{|k| fib[k]}.join(’ ')
cool. only one puts speeds things up.
On 7/14/06, Glenn C. [email protected] wrote:
The problem for
me is that I find it difficult to understand what is happening in this
code.
When I am confused (which happens all too often), I like to “see” what
is happening. Below is the same algorithm with a slightly different
implementation (I used class variables rather than a global). I also
provided a simple accessor to the class variable.
Good Luck
pth
class Integer
@@fib = Hash.new do |h,k|
puts “Calculate fib[#{k}]”
h[k] = h[k-2] + h[k-1]
end
@@fib[0] = 0
@@fib[1] = 1
def fib
@@fib[self]
end
def self.fibs
@@fib
end
end
puts 10.fib
puts 7.fib.fib
p Integer.fibs
----- Output ------
Calculate fib[10]
Calculate fib[8]
Calculate fib[6]
Calculate fib[4]
Calculate fib[2]
Calculate fib[3]
Calculate fib[5]
Calculate fib[7]
Calculate fib[9]
55
Calculate fib[13]
Calculate fib[11]
Calculate fib[12]
233
{5=>5, 11=>89, 0=>0, 6=>8, 12=>144, 1=>1, 7=>13, 13=>233, 2=>1, 8=>21,
3=>2, 9=>34, 4=>3, 10=>55}
On Jul 14, 2006, at 4:32 AM, Glenn C. wrote:
fib(n)
result
BTW How would I then access $fib to puts an output of the sequence
eg. 0
1 1 2 3 5 8 13 etc.
(I hate when the email doesn’t get through)
I first saw this Hash trick in a RubyQuiz solution. I’ve used it in
different ways since, but here’s some amazing evidence as to it’s power:
I ran the comparisons locally to try things out. Basically, you just
can’t beat memoization with a Hash for something this simple (it’s
just addition after all). I did adjust some of the implementations
so that they produced the same sequence: fib(0) = 0, fib(1) = 1, fib
(2) = 1, fib(3) = 2, etc. (Some of them had fib(0) == fib(1) == 1)
100.times { 0.upto(30) { |n| fib(n) } }
user system total real
fib1.rb: if 682.070000 1.850000 683.920000 (689.604829)
fib2.rb: case 631.260000 1.380000 632.640000 (636.994644)
fib3.rb: simple if 512.770000 0.860000 513.630000 (515.151776)
fib4.rb: simple ?: 498.760000 0.470000 499.230000 (499.626195)
fib6.rb: Hash 0.000000 0.000000 0.000000 ( 0.007612)
fib7.rb: formula 0.030000 0.000000 0.030000 ( 0.023598)
fib8.rb: BigMath 2.750000 0.010000 2.760000 ( 2.762493)
user system total real
fib1.rb: if 100.000 % 1.850000 683.920000 (689.604829)
fib2.rb: case 92.550 % 1.380000 632.640000 (636.994644)
fib3.rb: simple if 75.178 % 0.860000 513.630000 (515.151776)
fib4.rb: simple ?: 73.124 % 0.470000 499.230000 (499.626195)
fib6.rb: Hash 0.000 % 0.000000 0.000000 ( 0.007612)
fib7.rb: formula 0.004 % 0.000000 0.030000 ( 0.023598)
fib8.rb: BigMath 0.403 % 0.010000 2.760000 ( 2.762493)
Let’s peel those fast ones apart a bit:
10_000.times { 0.upto(30) { |n| fib(n) } }
user system total real
fib6.rb: Hash 0.240000 0.000000 0.240000 ( 0.246511)
fib7.rb: formula 2.610000 0.010000 2.620000 ( 2.635959)
fib8.rb: BigMath 302.950000 0.810000 303.760000 (306.202394)
What about when the numbers get bigger? Does the formula start to
have an advantage?
1000.times { 0.upto(300) { |n| fib(n) } }
user system total real
fib6.rb: Hash 2.310000 0.010000 2.320000 ( 2.322534)
fib7.rb: formula 45.720000 0.090000 45.810000 ( 46.018314)
Uh, not really.
Let’s see them all together again:
fib1.rb: if for 30: 832040
fib2.rb: case for 30: 832040
fib3.rb: simple if for 30: 832040
fib4.rb: simple ?: for 30: 832040
fib6.rb: Hash for 30: 832040
fib7.rb: formula for 30: 832040
fib8.rb: BigMath for 30: 832040
1000.times { 0.upto(30) { |n| fib(n) } }
user system total real
fib1.rb: if 6158.150000 3.740000 6161.890000 (6167.126104)
fib2.rb: case 5702.300000 5.630000 5707.930000 (5722.498983)
fib3.rb: simple if 4837.140000 3.320000 4840.460000 (4846.447905)
fib4.rb: simple ?: 4969.330000 5.540000 4974.870000 (4986.140834)
fib6.rb: Hash 0.020000 0.000000 0.020000 ( 0.021521)
fib7.rb: formula 0.240000 0.000000 0.240000 ( 0.245543)
fib8.rb: BigMath 27.740000 0.040000 27.780000 ( 27.828623)
==> fib.rb <==
require ‘benchmark’
include Benchmark
require ‘…/constantize.rb’
fibsto = ENV[‘FIBS_UPTO’] || 30
fibrep = ENV[‘FIB_REPTS’] || 1000
algorithms = [ ]
Dir.glob(ARGV.empty? ?
‘fib[1-46-9].rb’ :
ARGV.each { |p| Regexp.quote(p) }.unshift(‘{’).push
(‘}’).join(%{,})) do |f|
require f
mod = constantize(File.basename(f,‘.rb’).capitalize)
include mod
algorithms << Hash[ :description => “#{f}: #{mod.module_eval
{ description }}”,
:alg => lambda { fibrep.times { 0.upto(fibsto)
{ |n| mod.fib(n) } } },
:fib => lambda { |n| mod.fib(n) }
]
end
algorithms.each do |a|
fibsto.upto(fibsto) do |n|
puts “#{a[:description]} for #{n}: #{a[:fib].call(n)}”
end
end
puts “#{fibrep}.times { 0.upto(#{fibsto}) { |n| fib(n) } }”
bm(1 + algorithms.inject(9) { |mx,h| mx<h[:description].length ? h
[:description].length : mx }) do |x|
algorithms.each do |a|
x.report(a[:description]) { a[:alg].call }
end
end
==> fib1.rb <==
VERSION 1
module Fib1
def description; “if”; end
def self.fib(n)
# puts “#{File.basename(FILE,‘.rb’)}(#{n})”
if n == 0
return 0
elsif n == 1
return 1
else
return fib(n-1) + fib(n-2)
end
end
end
==> fib2.rb <==
VERSION 2
module Fib2
def description; “case”; end
def self.fib(n)
# puts “#{File.basename(FILE,‘.rb’)}(#{n})”
case n
when 0
0
when 1
1
else
fib(n-1) + fib(n-2)
end
end
end
==> fib3.rb <==
VERSION 3
module Fib3
def description; “simple if”; end
def self.fib(n)
# puts “#{File.basename(FILE,‘.rb’)}(#{n})”
if n<=1
n.zero? ? 0 : 1
else
fib(n-1) + fib(n-2)
end
end
end
==> fib4.rb <==
VERSION 4
module Fib4
def description; “simple ?:”; end
def self.fib(n)
# puts “#{File.basename(FILE,‘.rb’)}(#{n})”
n<=1 ? (n.zero? ? 0 : 1) : fib(n-1) + fib(n-2)
end
end
==> fib5.rb <==
Version 5
module Fib5
def description; “lambda”; end
fib = lambda{|n|
# puts “#{File.basename(FILE,‘.rb’)}(#{n})”
n<=1 ? (n.zero? ? 0 : 1) : fib[n-1] + fib[n-2]
}
end
==> fib6.rb <==
Version 6
module Fib6
def description; “Hash”; end
$fib = Hash.new{|h,k| h[k] = h[k-2] + h[k-1]}
$fib[0] = 0
$fib[1] = 1
def self.fib(n)
# puts “#{File.basename(FILE,‘.rb’)}(#{n})”
# puts “#{File.basename(FILE,‘.rb’)}(#{n}) => #{$fib[n]}” if
n == 30
$fib[n]
end
end
==> fib7.rb <==
Version 7
Weisstein, Eric W. “Binet’s Fibonacci Number Formula.” From
MathWorld–A Wolfram Web Resource.
Binet's Fibonacci Number Formula -- from Wolfram MathWorld
module Fib7
def description; “formula”; end
SQRT5 = Math.sqrt(5)
def self.fib(n)
# puts “#{File.basename(FILE,‘.rb’)}(#{n})”
(((1+SQRT5)**n - (1-SQRT5)n)/(2n * SQRT5)).round
end
end
==> fib8.rb <==
Version 8
Weisstein, Eric W. “Binet’s Fibonacci Number Formula.” From
MathWorld–A Wolfram Web Resource.
Binet's Fibonacci Number Formula -- from Wolfram MathWorld
require ‘bigdecimal’
require ‘bigdecimal/math’
include BigMath
module Fib8
def description; “BigMath”; end
SQRT5 = BigMath.sqrt(BigDecimal(“5”),20)
def self.fib(n)
# puts “#{File.basename(FILE,‘.rb’)}(#{n})”
(((1+SQRT5)**n - (1-SQRT5)n)/(2n * SQRT5)).round.to_i
end
end
==> …/constantize.rb <==
from Jim W. (based on email correspondence)
def constantize(camel_cased_word)
camel_cased_word.
sub(/^::/,‘’).
split(“::”).
inject(Object) { |scope, name| scope.const_get(name) }
end
==> timing.txt <==
user system total real
fib1.rb: if 682.070000 1.850000 683.920000 (689.604829)
fib2.rb: case 631.260000 1.380000 632.640000 (636.994644)
fib3.rb: simple if 512.770000 0.860000 513.630000 (515.151776)
fib4.rb: simple ?: 498.760000 0.470000 499.230000 (499.626195)
fib6.rb: Hash 0.000000 0.000000 0.000000 ( 0.007612)
fib7.rb: formula 0.030000 0.000000 0.030000 ( 0.023598)
fib8.rb: BigMath 2.750000 0.010000 2.760000 ( 2.762493)
user system total real
fib1.rb: if 100.000 % 1.850000 683.920000 (689.604829)
fib2.rb: case 92.550 % 1.380000 632.640000 (636.994644)
fib3.rb: simple if 75.178 % 0.860000 513.630000 (515.151776)
fib4.rb: simple ?: 73.124 % 0.470000 499.230000 (499.626195)
fib6.rb: Hash 0.000 % 0.000000 0.000000 ( 0.007612)
fib7.rb: formula 0.004 % 0.000000 0.030000 ( 0.023598)
fib8.rb: BigMath 0.403 % 0.010000 2.760000 ( 2.762493)
10_000.times
user system total real
fib6.rb: Hash 0.240000 0.000000 0.240000 ( 0.246511)
fib7.rb: formula 2.610000 0.010000 2.620000 ( 2.635959)
fib8.rb: BigMath 302.950000 0.810000 303.760000 (306.202394)
0.upto(300)
user system total real
fib6.rb: Hash 2.310000 0.010000 2.320000 ( 2.322534)
fib7.rb: formula 45.720000 0.090000 45.810000 ( 46.018314)
fib1.rb: if for 30: 832040
fib2.rb: case for 30: 832040
fib3.rb: simple if for 30: 832040
fib4.rb: simple ?: for 30: 832040
fib6.rb: Hash for 30: 832040
fib7.rb: formula for 30: 832040
fib8.rb: BigMath for 30: 832040
1000.times { 0.upto(30) { |n| fib(n) } }
user system total real
fib1.rb: if 6158.150000 3.740000 6161.890000 (6167.126104)
fib2.rb: case 5702.300000 5.630000 5707.930000 (5722.498983)
fib3.rb: simple if 4837.140000 3.320000 4840.460000 (4846.447905)
fib4.rb: simple ?: 4969.330000 5.540000 4974.870000 (4986.140834)
fib6.rb: Hash 0.020000 0.000000 0.020000 ( 0.021521)
fib7.rb: formula 0.240000 0.000000 0.240000 ( 0.245543)
fib8.rb: BigMath 27.740000 0.040000 27.780000 ( 27.828623)