MY CODE KILLED MY COMPUTER!!!!!

Feb 20, 2011 at 2:43am
I wrote a recursive function to solve for a number in the Fibonacci sequence:

1
2
3
4
5
6
fib(int num)
{
if (num == 1 || num == 2)
    return 1;
return fib(num-1) + fib(num-2)
}


I called it with 10000.

It killed my computer.

Why?
Feb 20, 2011 at 2:53am
closed account (3hM2Nwbp)
If it killed the computer how are you posting :-\ Maybe it just knocked it out for a little while :P

That might have overflowed your stack. Recursion is notorious for that.
Feb 20, 2011 at 3:13am
Actually the recursion depth is linear. I think your computer froze. Your code has exponential time complexity and this means that you will probably be unable to handle inputs bigger than, say 40 or smth like that. I am afraid to sound pompous, but this is not so hard to see. I looked-up in google for the exact time complexity and it is Θ(𝜙 ^ n). Now, this is not obvious to me.

Anyway, there is a linear solution (one that can handle 10000 with no effort). There is somewhat harder to understand, but still quite manageable logarithmic solution (one that can handle astronomical inputs if you have the right arithmetic support underneath).

Regards

P.S. It just occurred to me, that actually no matter what solution you use, you will be unable to compute fib(10000) without support for arbitrarily large integers.
Last edited on Feb 20, 2011 at 3:26am
Feb 21, 2011 at 5:45am
this:
return fib(num-1) + fib(num-2)
It's requesting for itself, therefore creating an infinitive loop.
Feb 21, 2011 at 6:16am
@clover leaf: It's not an infinite loop. It's recursion.
Feb 21, 2011 at 7:38am
You are using int which is 4bytes.

The limits of int are:
signed: -2147483648 to 2147483647
unsigned: 0 to 4294967295

With a signed integer you are able to compute 46 digits of the Fibonacci sequence before it goes over the int limit.

Fibonacci sequence
46 : 1836311903
47 : 2971215073
Feb 21, 2011 at 10:27am
You ALWAYS rerturn, whethert he IF statement is true or not. This function is being called infinitely, clover loaf was right.
Feb 21, 2011 at 10:29am
@pcannons: going over the INT limit does not freeze your computer, the processor simply truncates the value.
Feb 21, 2011 at 12:31pm
closed account (z05DSL3A)
Assuming the syntax errors are just typos.

Jaso333 wrote:
You ALWAYS rerturn, whethert he IF statement is true or not. This function is being called infinitely, clover loaf was right.

The function is recursive, meaning that it calls itself. It has guards to stop it from calling itself infinitely and the guards do look fine. This in borne out by calling it with a small number, it returns with the correct result.

The problem is that this algorithm explodes into a very long runtime very quickly.
A minor modification to the code will show this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int fib(int num)
{
    if (num == 1 || num == 2)
    {
        std::cout << ".";
        return 1;
    }
    return fib(num-1) + fib(num-2);
}
...

std::cout << "fib(5) = " << fib(5) << std::endl;
std::cout << "fib(10) = " << fib(10) << std::endl;
std::cout << "fib(15) = " << fib(15) << std::endl;
.....fib(5) = 5
.......................................................fib(10) = 55
..................................................................................................................................
..................................................................................................................................
..................................................................................................................................
..................................................................................................................................
..........................................................................................fib(15) = 610

As you get to very large numbers the run time will seem like the program has crashed.

Even if and when it does finish you will not get the correct answer because, as pcannons said, an int can't hold a number that big.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <deque>
#include <numeric>

double Fibonacci(unsigned int num)
{
    std::deque<double> q(2, 0);

    q[0] = 1.0;

    for(unsigned int i = 1; i < num; ++i)
    {
        q.push_front( accumulate( q.begin(), q.end(), 0.0 ) );

        q.pop_back();
    }
    return q[0];
}

void Fibonacci_sequence(unsigned int num)
{
    std::deque<double> q(2, 0);

    q[0] = 1.0;

    for(unsigned int i = 1; i < num; ++i)
    {
        std::cout << q[0] << " ";
        q.push_front( accumulate( q.begin(), q.end(), 0.0 ) );

        q.pop_back();
    }
    std::cout << std::endl;
}

int main()
{
    Fibonacci_sequence(25);

    std::cout << "Fibonacci(10)  = " << Fibonacci(10) << std::endl;
    std::cout << "Fibonacci(50)  = " << Fibonacci(50) << std::endl;
    std::cout << "Fibonacci(100) = " << Fibonacci(100) << std::endl;
    std::cout << "Fibonacci(500) = " << Fibonacci(500) << std::endl;

    return (0);
}

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368
Fibonacci(10)  = 55
Fibonacci(50)  = 1.25863e+010
Fibonacci(100) = 3.54225e+020
Fibonacci(500) = 1.39423e+104




Last edited on Feb 21, 2011 at 12:47pm
Feb 21, 2011 at 6:19pm
Oh.

Thanks for the help! I randomly assumed that since 10000 was an int, all would be well. However, I was wrong.

10000 points to Grey Wolf for the help!!!

A note to everyone reading this now that didn't post above: DON'T RUN MY CODE!!!!! DANGER WILL ROBINSON!!!!!

A note to those people who don't understand basic recursion: Since the function is calling itself with lower and lower numbers, there's no problem; it eventually ends.
Feb 22, 2011 at 4:34am
You should in most cases use a loop instead of recursion; recursion though a nice algorithm, is very memory and time wasteful. And here you are calling fib twice for every call, making this call approx. 2^n times, producing n call frames.
It's better to use a loop that builds the number upward:
1
2
3
4
5
6
7
8
9
10
int fib(int n){
	int a=0,b=1,i=1;
	while(i<n){
		int s=a+b;
		a=b;
		b=s;
		i++;
	}
	return b;
}

This code runs through the loop n-1 times, and takes only a small, constant amount of memory.
Last edited on Feb 22, 2011 at 4:35am
Feb 22, 2011 at 7:25pm
If it freezes the computer, your OS really sucks!
Feb 24, 2011 at 3:12am
The operating system doesn't affect it that much. It can slow it down by at the most, I'd estimate only a few seconds, depending on how well the OS is coded, and the features implemented in it, It shouldn't lead to a freeze. It's more likely that your code was the problem. Try adding a pause** somewhere in there so it doesn't put as much strain on your hardware. Also, if the problem persists, try getting a better processor and/or more RAM.

**
1
2
3
4
5
6
7
fib(int num)
{
Pause(#ofMillimeconds) // make sure this is BEFORE THE RECURSION CALL or it won't be effective. I've learned this from experience. (I blue screened DX)
if (num == 1 || num == 2)
    return 1;
return fib(num-1) + fib(num-2)
}





Feb 24, 2011 at 3:45am
JoR means that the scheduler is responsible to prevent a single program from freezing the entire system. Windows is quite good at letting that happen. I have always wondered why is that possible? Aren't there better scheduling algorithms?

Regards
Feb 24, 2011 at 8:57am
closed account (z05DSL3A)
pwnedu46 wrote:
It's more likely that your code was the problem. Try adding a pause** somewhere in there so it doesn't put as much strain on your hardware. Also, if the problem persists, try getting a better processor and/or more RAM.

This is very odd, if the hardware can't keep up its a software problem? I have known PCs to flake out under load, usually because of clogged up heat sinks and fans any the solution was never to use more inefficient software.

It would be nice if the OP specified what he meant by "KILLED MY COMPUTER".
Feb 24, 2011 at 7:09pm
His code doesn't kill my computer, but mine is linux.
Topic archived. No new replies allowed.