blob: 1002d72094a255e6a583a7b1bc0b44b8b6da5516 (
plain)
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
/*static unsigned long long cache[256] = {0};*/
// cache[0]
// cache[1]
//
/*unsigned long long fib(unsigned int n)*/
/*{*/
/*if (n <= 1)*/
/*return n;*/
/*return fib(n-2) + fib(n-1);*/
/*}*/
/*unsigned long long fib(unsigned int n)*/
/*{*/
/*if (n <= 1)*/
/*return n;*/
/*if (cache[n-1] == 0)*/
/*cache[n-1] = fib(n - 1);*/
/*if (cache[n-2] == 0)*/
/*cache[n-2] = fib(n - 2);*/
/*return cache[n-2] + cache[n-1];*/
/*}*/
unsigned long long fib(unsigned int n)
{
unsigned long long x = 0; // n-2
unsigned long long y = 1; // n-1
unsigned long long tmp = 0;
if (n <= 1)
return n;
for (unsigned int i = 1; i < n; i++)
{
tmp = x;
x = y;
y = x + tmp;
}
return y;
}
/*
How do I represent a number that is greater
than the largest number that my computer can
represent using a primitive data type?
1. research
2. data structures -> different way smaller problem
218922995834555169026
|10^1|10^0|
| 10| 1|
|2|1|8|9|2|2|9|9|5|8|3|4|5|5|5|1|6|9| 0| 2| 6|
100
+010
----
110
*/
int main(int argc, char *argv[])
{
/*assert(fib(0) == 0);*/
/*assert(fib(1) == 1);*/
/*assert(fib(2) == 1);*/
/*assert(fib(3) == 2);*/
/*assert(fib(4) == 3);*/
/*assert(fib(12) == 144);*/
/*assert(fib(25) == 75025);*/
/*assert(fib(49) == 7778742049);*/
/*assert(fib(50) == 12586269025);*/
/*assert(fib(99) == 218922995834555169026);*/
/*getchar();*/
for (int i = 0; i < 50; i++) {
printf("%3d: %20llu\n", i, fib(i));
}
printf("YAY!\n");
return 0;
}
// no cache: real 3m21.146s
// cache: real 0m0.001s
|
