bigint

C++20 implementation of arbitrary precision integer arithmetic.

This implementation is a re-implementation from:

https://sites.google.com/site/indy256/algo_cpp/bigint

However, this site is no more reachable.

You can get back past snapshots from the Internet Archive:

https://web.archive.org/web/20210301000000*/https://sites.google.com/site/indy256/algo_cpp/bigint

March 19 2021:

https://web.archive.org/web/20210319023614/https://sites.google.com/site/indy256/algo_cpp/bigint

October 24 2011:

https://web.archive.org/web/20111024050800/https://sites.google.com/site/indy256/algo_cpp/bigint

February 8 2011:

https://web.archive.org/web/20110208155854/https://sites.google.com/site/indy256/algo_cpp/bigint

Snapshot from March 19 2921 can be found in the folder src/original

Requirements

cmake 3.26.3 is used to compile the sources.

The cmake files compile with -std=c++20. It does not compile for C++17.

The unit tests are implemented in googletest: be sure you have installed googletest to compile.

To compile the example fibonacci, you need to install Boost's libboost-filesystem-dev, libboost-program-options-dev.

Install and Run Unit Tests

$ git clone https://github.com:massimo-marino/bigint.git
$ cd bigint
$ mkdir build
$ cd build
$ cmake ..
$ make
$ cd src/unitTests
$ ./bigint-unit-tests

Example: Fibonacci

To run the example:

$ cd build/src/fibonacci
$ ./fibonacci --help
[main] USAGE: ./fibonacci options
Options:
  -n [ --n ] [=arg(=1)] (=1)            the fib number we want to compute
  -t [ --test ] [=arg(=1)] (=0)         test fib algorithms; no result is
                                        printed or saved on file
  -w [ --write-to-file ] [=arg(=1)] (=0)
                                        write the result to file
  -h [ --help ]                         Print this help message

$ ./fibonacci -n 100
[main] fib(100) = 354224848179261915075
of length 21
$ ./fibonacci -w -n 1000000
[main] fib(1000000) of length 208988 digits written to file fib-1000000.txt

If you want to verify the results, there's a Julia script fib.jl in src/fibonacci/julia/

From there (and after having installed Julia), run:

$ julia -i fib.jl

julia> fib(100)
354224848179261915075

julia> fib(1000000)
195328212870775773163201494759625633...omitted...411568996526838242546875

julia>

In src/fibonacci/fibmemo/ an implementation using memoization. Note that it will crash for a big number due to memory constraints depending on the algorithm chosen. See the code for the details.

$ cd build/src/fibonacci/fibmemo
$ ./fibmemo --help
[main] USAGE: ./fibmemo options
Options:
  -n [ --n ] [=arg(=1)] (=1) the fib number we want to compute
  -h [ --help ]              Print this help message
$ ./fibmemo -n 1000
fibmemo(1000): 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875 took 0.00843339 sec.
memo size: 1001

How to Use it

See the source code and the unit tests for examples of use.