Created
February 23, 2014 01:08
-
-
Save mnem/9165119 to your computer and use it in GitHub Desktop.
Quick and dirty calculator for the largest fibonacci sequence number which can be held in common integer widths and in a JavaScript Number. Likely only compiles on a 64 bit machine with a reasonably modern gcc or clang.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdint.h> | |
#include <inttypes.h> | |
// Uses the fibonacci sequence defined | |
// in http://oeis.org/A000045 | |
__uint128_t fib(__uint128_t n) { | |
if (n == 0) { | |
return 0; | |
} | |
__uint128_t prev = 0; | |
__uint128_t result = 1; | |
__uint128_t sum; | |
for(size_t i = 2; i <= n; ++i) | |
{ | |
sum = result + prev; | |
prev = result; | |
result = sum; | |
} | |
return result; | |
} | |
int main(int argc, char *argv[]) { | |
int hit[] = {0, 0, 0, 0}; | |
int next_hit = 0; | |
int was_hit; | |
for (int i = 0; i < 100; i++) { | |
was_hit = 0; | |
__uint128_t result = fib(i); | |
if (result > INT32_MAX && !hit[0]) { | |
was_hit = 1; | |
printf("^-- 32 bit signed int max ------------------------------\n"); | |
} else if (result > UINT32_MAX && !hit[1]) { | |
was_hit = 1; | |
printf("^-- 32 bit unsigned int max ------------------------------\n"); | |
} else if (result > UINT64_C(9007199254740992) && !hit[2]) { | |
was_hit = 1; | |
printf("^-- JavaScript Number (53 bit signed int) max ------------------------------\n"); | |
} else if (result > INT64_MAX && !hit[3]) { | |
was_hit = 1; | |
printf("^-- 64 bit signed int max ------------------------------\n"); | |
} else if (result > UINT64_MAX) { | |
printf("^-- 64 bit unsigned int max ------------------------------\n"); | |
return 0; | |
} | |
if (was_hit) { | |
hit[next_hit] = 1; | |
++next_hit; | |
} | |
printf("%d:\t%" PRIu64 "\n", i, (uint64_t)result); | |
} | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
0: 0 | |
1: 1 | |
2: 1 | |
3: 2 | |
4: 3 | |
5: 5 | |
6: 8 | |
7: 13 | |
8: 21 | |
9: 34 | |
10: 55 | |
11: 89 | |
12: 144 | |
13: 233 | |
14: 377 | |
15: 610 | |
16: 987 | |
17: 1597 | |
18: 2584 | |
19: 4181 | |
20: 6765 | |
21: 10946 | |
22: 17711 | |
23: 28657 | |
24: 46368 | |
25: 75025 | |
26: 121393 | |
27: 196418 | |
28: 317811 | |
29: 514229 | |
30: 832040 | |
31: 1346269 | |
32: 2178309 | |
33: 3524578 | |
34: 5702887 | |
35: 9227465 | |
36: 14930352 | |
37: 24157817 | |
38: 39088169 | |
39: 63245986 | |
40: 102334155 | |
41: 165580141 | |
42: 267914296 | |
43: 433494437 | |
44: 701408733 | |
45: 1134903170 | |
46: 1836311903 | |
^-- 32 bit signed int max ------------------------------ | |
47: 2971215073 | |
^-- 32 bit unsigned int max ------------------------------ | |
48: 4807526976 | |
49: 7778742049 | |
50: 12586269025 | |
51: 20365011074 | |
52: 32951280099 | |
53: 53316291173 | |
54: 86267571272 | |
55: 139583862445 | |
56: 225851433717 | |
57: 365435296162 | |
58: 591286729879 | |
59: 956722026041 | |
60: 1548008755920 | |
61: 2504730781961 | |
62: 4052739537881 | |
63: 6557470319842 | |
64: 10610209857723 | |
65: 17167680177565 | |
66: 27777890035288 | |
67: 44945570212853 | |
68: 72723460248141 | |
69: 117669030460994 | |
70: 190392490709135 | |
71: 308061521170129 | |
72: 498454011879264 | |
73: 806515533049393 | |
74: 1304969544928657 | |
75: 2111485077978050 | |
76: 3416454622906707 | |
77: 5527939700884757 | |
78: 8944394323791464 | |
^-- JavaScript Number (53 bit signed int) max ------------------------------ | |
79: 14472334024676221 | |
80: 23416728348467685 | |
81: 37889062373143906 | |
82: 61305790721611591 | |
83: 99194853094755497 | |
84: 160500643816367088 | |
85: 259695496911122585 | |
86: 420196140727489673 | |
87: 679891637638612258 | |
88: 1100087778366101931 | |
89: 1779979416004714189 | |
90: 2880067194370816120 | |
91: 4660046610375530309 | |
92: 7540113804746346429 | |
^-- 64 bit signed int max ------------------------------ | |
93: 12200160415121876738 | |
^-- 64 bit unsigned int max ------------------------------ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment