So here's a way to define Fibonacci iteratively.
[BLANK_AUDIO]
We're going to avoid all the redundant computation by keeping track as we
go. And we're going to have two variables. And I'm going to do this
in a slightly strange way, and the reason for this will become
clear soon. I want to make it so we can get the right
answer when n is 0 and when n is 1, without having
special cases. So instead of keeping track of the previous two, I'm
going to keep track of the current one and the imaginary one that's
going to be after that. And we know that the first two Fibonacci
numbers are 0 and 1, so we'll use current is
0, and the next one, we'll call after is 1.
So that's the one after the one that we're currently
doing, and now we have a loop, so we're going to
go from i in the range from 0 to n.
So we're looking for Fibonacci number n, that means we
want to start at 0. The current value is the value
for Fibonacci 0 and after is the value for Fibonacci
1, and as we go through the loop, we'll keep
updating those. And we want to update them by following the
recursive rule and so that means that the new value
of current, is the current value of after. And the new
value of after, is the sum of those two lists;
current plus after. We can do that with a multiple
assignment, that'll save us from needing a temporary variable. We
can assign current and after, to their new values. The new
value of current, is the current value of after, and the
new value of after is current plus after. So, this is
the place where a multiple assignment comes in handy. If we
didn't use a multiple assignment, we'd have to use a temporary
value to keep track of one of these while we do
the assignments. But with multiple assignment, we get both of these
values first, and then we assign them to the two variables
on the left side. So, that's all we need. And then
after the loop, we should return the value of
current, which is the current Fibonacci number if we're looking
for Fibonacci N. So let's try that. So we
should be able to see Fibonacci 0, and the result
should be 0. And that's what we get, and,
because that's the value of current, when the range is
from 0 to 0, we don't go through the loop
at all. So we get the value 1. Let's check
Fibonacci 1, and we run this, we get the value 1, which is also
what we expect. And we got that because we went through the loop once, assigning
the value of after, which started as 1 to current and that's what we
return as the value of current. And we can keep going, we'll try Fibonacci 2.
And that's also 1, as we expect and Fibonacci 3
should be 1 plus 1, gets us 2 and so forth.
[BLANK_AUDIO].
Okay, so this looks like it's working. We've tried
a few simple ones. Let's try Fibonacci 33. So
we estimated in the earlier quiz, in order to
compute fibonacci 36, we would need Fibonacci 33 calls,
using the previous recursive definition. So, why did it
take so long for that code to run? So
what's the value of Fibonacci 33? And that's what
it is, it's 3 and a half million calls.
And so even with a processor that's doing a billion instructions
a second, doing 3 and a half million recursive calls takes
quite a while. Each time through the call, is many more
than just one instruction it's many thousands of instructions. So this
starts to take enough time that we didn't see the result.
And, it wasn't only those Fibonacci 33 calls to Fibonacci 2,
we had all the other things that we had to do
to get Fibonacci 36. But let's see that now we have
our faster, internet definition of Fibonacci that isn't doing all that duplicate
work, that we can compute Fibonacci 36. And so that gives us this value,
so indicating that there would be about 15 million rabbits after 3 years
using Fibonacci's model. Let's try what we'd have after 5
years, passing in 60 months, and we
get this starting to be quite a huge
number. To try to relate to this, let's look
at how long it would take for the mass
of all the rabbits that are born to exceed
the mass of the Earth. So the mass of the Earth is 5.9722 times 10 to the 24,
and that's in kilograms, and I'm using the times
time notation. This gives us a power, so this
is 10 to the power 24. So that's one way to write 5.9 times 10 to the 24
kilograms, just to demonstrate the power notation, this is
2 to the power 10, so we'll see the result
is 1,024. That's what we get by multiplying 2
times 2 times 2 times 2 10 times. Here we're
multiplying 10 by itself 24 times and that's a good
estimate for the mass of the earth. So now to
find out how many months it takes before the
mass of the rabbits exceeds the mass of the earth,
we're going to have a for loop. We're going to loop from
Fibonacci numbers, until we get to a number that exceeds
the mass of the Earth. We also need to decide what a mass of a rabbit is, and
I'm going to assume that a rabbit weighs about 2
kilograms. And, that's a pretty good guess for how heavy
a rabbit is. That's assuming of course, a well
fed rabbit like we have today, not if the rabbits
spread as fast as Fibonacci's model would suggest that
they do. So, we'll write a loop to see when
the mass of the rabbits exceeds the mass
of the earth. We'll start with n equals 1,
and we're going to keep going until Fibonacci n
exceeds the mass of the earth. So, we'll go
while Fibonacci n times the mass of the
rabbit. So Fibonacci n gives us the numbers of
the rabbits in month end, times the mass of
the rabbit and as long as that is less
than the mass of the Earth, the Earth is
still safe for humanity, or at least there's some space
left for humans. And every time through the loop,
we'll increase n by 1. And at the end of
the loop, we'll print out the value of n,
we'll see where we got, and let's also print out
the value of Fibonacci n, to see how big the
Fibonacci number of that n is. So we'll keep going
through the loop, as long as the Fibonacci of n times
the mass of the rabbit is less than the mass of the
Earth. And once we stop the loop that means we've exceeded
the mass of the Earth and we'll see what the results is.
So let's try running that, and, we get this result. The
value of n is 119, so it'll only take 119 months, or
just less than 10 years, until the mass of the rabbits exceeds
the mass of the Earth. And this is the number of rabbits
we would have then. A pretty big number, you should
be very afraid of all these rabbits. The good news
is that Fibonacci's model, is not actually correct. That this
was a mathematical abstraction for
rabbit reproduction. Real rabbits actually die
off after some point, and if there're too many rabbits,
they don't have enough food, so they don't keep growing
like the Fibonacci numbers and take over the entire planet.
So we should be very afraid if Fibonacci's model is correct.
It would only take 10 years for the rabbits to take over the entire planet,
and weigh more than the earth does itself. The good news is, it's not a very
accurate model of how rabbits reproduce, that
they don't live forever, and once there're too
many rabbits, they start to run out of
food. So they stop reproducing, and stop surviving.