A blazingly fast C++23 implementation of Fibonacci number calculation using compile-time generated lookup tables with 128-bit integer support.
- Compile-time lookup table generation using C++23 constexpr capabilities
- O(1) complexity for all Fibonacci number lookups
- Sub-nanosecond performance (typically 0.04-0.08ns per lookup)
- Extended range support up to F(186) using unsigned 128-bit integers
- Cache-optimized with proper alignment and prefetching
- Zero runtime computation - all values pre-computed at compile time
- Throughput: 238-243 million operations per second
- Latency: 0.04-3.1 nanoseconds per lookup
- Range: F(0) to F(186)
- F(0) to F(93): 64-bit unsigned integers
- F(94) to F(186): 128-bit unsigned integers
The implementation uses two compile-time generated lookup tables:
- 64-bit table for F(0) to F(93) - the largest Fibonacci numbers that fit in
uint64_t - 128-bit table for F(0) to F(186) - extended range using
unsigned __int128
- Cache line alignment (64 bytes) for optimal memory access
- Forced inlining for critical paths
- Branch prediction hints using
__builtin_expect - Manual loop unrolling for throughput benchmarks
- Prefetching support for bulk operations
- Link-Time Optimization (LTO) enabled
- C++23 compatible compiler (GCC 11+ or Clang 13+)
- Make
make clean
make
./fibFor debug build:
make debug% ./fib
Optimized Fibonacci micro-benchmark (Maximum Performance Edition):
Complete Fibonacci Sequence with Performance Metrics (F(0) to F(93)):
===========================================================================
F( 0) = 0 | 0.3330 ns | 3003.0M ops/sec
F( 1) = 1 | 0.3340 ns | 2994.0M ops/sec
F( 2) = 1 | 0.3750 ns | 2666.7M ops/sec
F( 3) = 2 | 0.3330 ns | 3003.0M ops/sec
F( 4) = 3 | 0.2920 ns | 3424.7M ops/sec
F( 5) = 5 | 0.2910 ns | 3436.4M ops/sec
F( 6) = 8 | 0.3340 ns | 2994.0M ops/sec
F( 7) = 13 | 0.3330 ns | 3003.0M ops/sec
F( 8) = 21 | 0.3330 ns | 3003.0M ops/sec
F( 9) = 34 | 0.3340 ns | 2994.0M ops/sec
F(10) = 55 | 0.2920 ns | 3424.7M ops/sec
F(11) = 89 | 0.3330 ns | 3003.0M ops/sec
F(12) = 144 | 0.3330 ns | 3003.0M ops/sec
F(13) = 233 | 0.3340 ns | 2994.0M ops/sec
F(14) = 377 | 0.3750 ns | 2666.7M ops/sec
F(15) = 610 | 0.2910 ns | 3436.4M ops/sec
F(16) = 987 | 0.3340 ns | 2994.0M ops/sec
F(17) = 1597 | 0.3340 ns | 2994.0M ops/sec
F(18) = 2584 | 0.2920 ns | 3424.7M ops/sec
F(19) = 4181 | 0.2920 ns | 3424.7M ops/sec
F(20) = 6765 | 0.2920 ns | 3424.7M ops/sec
F(21) = 10946 | 0.3340 ns | 2994.0M ops/sec
F(22) = 17711 | 0.3340 ns | 2994.0M ops/sec
F(23) = 28657 | 0.2910 ns | 3436.4M ops/sec
F(24) = 46368 | 0.2910 ns | 3436.4M ops/sec
F(25) = 75025 | 0.2910 ns | 3436.4M ops/sec
F(26) = 121393 | 0.3330 ns | 3003.0M ops/sec
F(27) = 196418 | 0.3330 ns | 3003.0M ops/sec
F(28) = 317811 | 0.3330 ns | 3003.0M ops/sec
F(29) = 514229 | 0.3340 ns | 2994.0M ops/sec
F(30) = 832040 | 0.2920 ns | 3424.7M ops/sec
F(31) = 1346269 | 0.3330 ns | 3003.0M ops/sec
F(32) = 2178309 | 0.2910 ns | 3436.4M ops/sec
F(33) = 3524578 | 0.2910 ns | 3436.4M ops/sec
F(34) = 5702887 | 0.3330 ns | 3003.0M ops/sec
F(35) = 9227465 | 0.2920 ns | 3424.7M ops/sec
F(36) = 14930352 | 0.2920 ns | 3424.7M ops/sec
F(37) = 24157817 | 0.2910 ns | 3436.4M ops/sec
F(38) = 39088169 | 0.2910 ns | 3436.4M ops/sec
F(39) = 63245986 | 0.3330 ns | 3003.0M ops/sec
F(40) = 102334155 | 0.3330 ns | 3003.0M ops/sec
F(41) = 165580141 | 0.3330 ns | 3003.0M ops/sec
F(42) = 267914296 | 0.3340 ns | 2994.0M ops/sec
F(43) = 433494437 | 0.2910 ns | 3436.4M ops/sec
F(44) = 701408733 | 0.2920 ns | 3424.7M ops/sec
F(45) = 1134903170 | 0.2920 ns | 3424.7M ops/sec
F(46) = 1836311903 | 0.4160 ns | 2403.8M ops/sec
F(47) = 2971215073 | 0.3340 ns | 2994.0M ops/sec
F(48) = 4807526976 | 0.3330 ns | 3003.0M ops/sec
F(49) = 7778742049 | 0.2920 ns | 3424.7M ops/sec
F(50) = 12586269025 | 0.3340 ns | 2994.0M ops/sec
F(51) = 20365011074 | 0.2920 ns | 3424.7M ops/sec
F(52) = 32951280099 | 0.3330 ns | 3003.0M ops/sec
F(53) = 53316291173 | 0.3330 ns | 3003.0M ops/sec
F(54) = 86267571272 | 0.2920 ns | 3424.7M ops/sec
F(55) = 139583862445 | 0.2920 ns | 3424.7M ops/sec
F(56) = 225851433717 | 0.2920 ns | 3424.7M ops/sec
F(57) = 365435296162 | 0.3340 ns | 2994.0M ops/sec
F(58) = 591286729879 | 0.2920 ns | 3424.7M ops/sec
F(59) = 956722026041 | 0.2910 ns | 3436.4M ops/sec
F(60) = 1548008755920 | 0.3330 ns | 3003.0M ops/sec
F(61) = 2504730781961 | 0.2910 ns | 3436.4M ops/sec
F(62) = 4052739537881 | 0.2920 ns | 3424.7M ops/sec
F(63) = 6557470319842 | 0.3330 ns | 3003.0M ops/sec
F(64) = 10610209857723 | 0.3340 ns | 2994.0M ops/sec
F(65) = 17167680177565 | 0.3340 ns | 2994.0M ops/sec
F(66) = 27777890035288 | 0.3750 ns | 2666.7M ops/sec
F(67) = 44945570212853 | 0.2910 ns | 3436.4M ops/sec
F(68) = 72723460248141 | 0.2920 ns | 3424.7M ops/sec
F(69) = 117669030460994 | 0.3330 ns | 3003.0M ops/sec
F(70) = 190392490709135 | 0.2910 ns | 3436.4M ops/sec
F(71) = 308061521170129 | 0.3340 ns | 2994.0M ops/sec
F(72) = 498454011879264 | 0.3330 ns | 3003.0M ops/sec
F(73) = 806515533049393 | 0.3330 ns | 3003.0M ops/sec
F(74) = 1304969544928657 | 0.2920 ns | 3424.7M ops/sec
F(75) = 2111485077978050 | 0.3330 ns | 3003.0M ops/sec
F(76) = 3416454622906707 | 0.3330 ns | 3003.0M ops/sec
F(77) = 5527939700884757 | 0.2910 ns | 3436.4M ops/sec
F(78) = 8944394323791464 | 0.4160 ns | 2403.8M ops/sec
F(79) = 14472334024676221 | 0.2910 ns | 3436.4M ops/sec
F(80) = 23416728348467685 | 0.3330 ns | 3003.0M ops/sec
F(81) = 37889062373143906 | 0.3330 ns | 3003.0M ops/sec
F(82) = 61305790721611591 | 0.2920 ns | 3424.7M ops/sec
F(83) = 99194853094755497 | 0.2920 ns | 3424.7M ops/sec
F(84) = 160500643816367088 | 0.2920 ns | 3424.7M ops/sec
F(85) = 259695496911122585 | 0.2910 ns | 3436.4M ops/sec
F(86) = 420196140727489673 | 0.2920 ns | 3424.7M ops/sec
F(87) = 679891637638612258 | 0.2910 ns | 3436.4M ops/sec
F(88) = 1100087778366101931 | 0.2910 ns | 3436.4M ops/sec
F(89) = 1779979416004714189 | 0.3330 ns | 3003.0M ops/sec
F(90) = 2880067194370816120 | 0.2920 ns | 3424.7M ops/sec
F(91) = 4660046610375530309 | 0.3330 ns | 3003.0M ops/sec
F(92) = 7540113804746346429 | 0.2920 ns | 3424.7M ops/sec
F(93) = 12200160415121876738 | 0.3330 ns | 3003.0M ops/sec
===========================================================================
Testing extended range with 128-bit support (F(94) to F(186)):
---------------------------------------------------------------------------
F( 94) = 19740274219868223167 | 0.9160 ns | VALID
F( 100) = 354224848179261915075 | 0.7500 ns | VALID
F( 110) = 43566776258854844738105 | 0.7500 ns | VALID
F( 120) = 5358359254990966640871840 | 0.7500 ns | VALID
F( 130) = 659034621587630041982498215 | 0.8340 ns | VALID
F( 140) = 81055900096023504197206408605 | 0.7920 ns | VALID
F( 150) = 9969216677189303386214405760200 | 0.8330 ns | VALID
F( 160) = 1226132595394188293000174702095995 | 1.0000 ns | VALID
F( 170) = 150804340016807970735635273952047185 | 1.0830 ns | VALID
F( 180) = 18547707689471986212190138521399707760 | 1.0420 ns | VALID
F( 185) = 205697230343233228174223751303346572685 | 1.0000 ns | VALID
F( 186) = 332825110087067562321196029789634457848 | 0.9170 ns | VALID
F( 187) = 0 | 0.7500 ns | OUT OF RANGE
F( 200) = 0 | 0.7500 ns | OUT OF RANGE
F(1000) = 0 | 0.7910 ns | OUT OF RANGE
F(10000) = 0 | 0.7500 ns | OUT OF RANGE
Random valid values performance test:
---------------------------------------------------------------------------
F( 7) = 13 | 0.3330 ns | 3003.0M ops/sec
F(23) = 28657 | 0.3330 ns | 3003.0M ops/sec
F(31) = 1346269 | 0.3330 ns | 3003.0M ops/sec
F(47) = 2971215073 | 0.3330 ns | 3003.0M ops/sec
F(59) = 956722026041 | 0.2920 ns | 3424.7M ops/sec
F(67) = 44945570212853 | 0.3330 ns | 3003.0M ops/sec
F(71) = 308061521170129 | 0.2920 ns | 3424.7M ops/sec
F(83) = 99194853094755497 | 0.2910 ns | 3436.4M ops/sec
F(89) = 1779979416004714189 | 0.3330 ns | 3003.0M ops/sec
F(91) = 4660046610375530309 | 0.3330 ns | 3003.0M ops/sec
===========================================================================
Targeted benchmarks with prefetching:
F(20) = 6765 [0.410 ns avg]
F(40) = 102334155 [0.840 ns avg]
F(60) = 1548008755920 [0.830 ns avg]
F(80) = 23416728348467685 [0.420 ns avg]
F(93) = 12200160415121876738 [0.410 ns avg]
Throughput test (10M iterations):
F(10) avg: 0.2774 ns | 3604.6M ops/sec
F(50) avg: 0.2889 ns | 3461.9M ops/sec
F(93) avg: 0.2801 ns | 3569.8M ops/sec
Benchmark sink: 13005075975939170324
Fibonacci fib;
// Standard 64-bit lookup (backwards compatible)
uint64_t f50 = fib(50); // Returns 12586269025
// Extended 128-bit lookup
auto f100 = fib.get128(100); // Returns 354224848179261915075
// Get as string (handles full 128-bit range)
std::string f186 = fib.get_string(186); // "332825110087067562321196029789634457848"
// Unsafe access (no bounds checking, maximum performance)
uint64_t f93 = fib.unsafe_get(93); // F(93) = 12200160415121876738
// Prefetch range for better cache utilization
fib.prefetch_range(20, 10); // Prefetch F(20) through F(29)- F(93) = 12,200,160,415,121,876,738 (largest that fits in 64-bit unsigned)
- F(186) = 332,825,110,087,067,562,321,196,029,789,634,457,848 (largest that fits in 128-bit unsigned)
- F(187) and beyond return 0 (would overflow 128-bit)
The lookup tables are generated at compile time using immediately invoked lambda expressions (IILE) with C++23's relaxed constexpr rules. This means:
- Zero runtime initialization cost
- Tables are embedded in the binary's read-only section
- No dynamic memory allocation
- Tested on macOS (ARM64/Apple Silicon)
- Should work on any platform with C++23 support and 128-bit integer extensions
- Compiler flags optimized for native architecture (
-march=native)
- Maximum supported index is 186 (due to 128-bit integer overflow at F(187))
- Binary size increases due to embedded lookup tables
- Requires compiler support for
unsigned __int128(GCC/Clang extension)
This is a demonstration/educational project. Feel free to use and modify as needed.
Traditional recursive Fibonacci: O(2^n) complexity Dynamic programming approach: O(n) complexity Matrix exponentiation: O(log n) complexity This implementation: O(1) complexity ✨
The lookup table approach trades memory (approximately 3KB for both tables) for exceptional performance, making it ideal for applications that need frequent Fibonacci number calculations within the supported range.