Calculates Fibonacci numbers with arbitrary precision. Fast doubling is used as Fibonacci alforithm which is explanied by Chun-Min Chang, and Karatsuba algoritm for multiplication inspired by the Vladimir Petrigo implementation for big numbers.
Arbitrary precision is achieved through a custom bigint class (only for
positive numbers) with multiplication, addition and subtraction operators
overloaded. Also, the std::string conversion operator is overloaded.
Use the Makefile file to build the binary. There are some targets available:
release: The default target generates de optimized binary atbin/bigfib.debug: Generates the binary for debugging withgdb.clean: Removes all the compilation files.
Feel free to update the CXX, CXXFLAGS, LIBS and LDFLAGS
variables if you need.
Usage: bin/bigfib [OPTIONS]... N...
Calculate the Fibonacci number of the given N terms.
-q, --quiet don't print the Fibonacci number
-s, --simple don't print summary.
-h, --help display this help and exit
-v, --version output version information and exit
Outputs for three terms using the quiet options to avoid the Fibonacci number printing.
bigfib -q 512 4784969 100000000Term: 512
Chunks: 12
Digits: 107
Calculating time: 0.013195 ms
Casting time: 0.015670 ms
Total time: 0.028865 ms
Term: 4784969
Chunks: 111112
Digits: 1000000
Calculating time: 220.479498 ms
Casting time: 3.840622 ms
Total time: 224.320120 ms
Term: 100000000
Chunks: 2322085
Digits: 20898764
Calculating time: 52460.604902 ms
Casting time: 76.934597 ms
Total time: 52537.539499 ms
Term: 512
Chunks: 12
Digits: 107
Calculating time: 0.010548 ms
Casting time: 0.002362 ms
Total time: 0.012910 ms
Term: 4784969
Chunks: 111112
Digits: 1000000
Calculating time: 181.037429 ms
Casting time: 2.739238 ms
Total time: 183.776667 ms
Term: 100000000
Chunks: 2322085
Digits: 20898764
Calculating time: 39561.871474 ms
Casting time: 54.250652 ms
Total time: 39616.122126 ms
Licensed under the MIT license.
Share and enjoy!