Return to Video

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
    we had all the other things that we had to do
  • 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
    of the earth. We'll start with n equals 1,
  • 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

English subtitles

改訂 Compare revisions