## Faster Fibonacci Solution - Intro to Computer Science

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

more » « less
Video Language:
English
Team:
Udacity
プロジェクト：
CS101 - Intro to Computer Science
Duration:
07:32
 Dejan Trajkovic edited 英語(米国) subtitles for 22-24 Faster Fibonacci Solution Udacity Robot edited 英語(米国) subtitles for 22-24 Faster Fibonacci Solution Udacity Robot edited 英語(米国) subtitles for 22-24 Faster Fibonacci Solution Udacity Robot edited 英語(米国) subtitles for 22-24 Faster Fibonacci Solution Cogi-Admin edited 英語(米国) subtitles for 22-24 Faster Fibonacci Solution

# English subtitles

## 改訂 Compare revisions

• Edited
Dejan Trajkovic
• API
Udacity Robot
• API
Udacity Robot
• API
Udacity Robot
• API