Very slow compared to the GNU MP Bignum Library

[2catycm]

https://gmplib.org/manual/Installing-GMP
I am learning c++, and doing an course assignment which require big integer
I ‘ve done a test for this BigInt library and GNU MP Bignum Library
this library is nearly O(n^2), while the gmp is only O(n) .
It seems the karatsuba algortithm in this library does not work well.

Multiplication Algorithms (GNU MP 6.2.1) (gmplib.org)

[perlun]

See #24. I'm not sure if this would cause the time complexity to go down to O(n), but it would at least make things faster. @faheel, any thoughts from your end on this part?

[faheel]

@2catycm This project is still in development and is not the most performant big integer library right now, especially compared to GMP which includes optimised assembly code for certain CPUs to extract the most performance.

I started it as an educational project, and so haven't been spending much time recently in maintaining it. I'll get back to improving things in the future when time permits. Until then I would recommend using GMP for serious use cases.

@perlun Yes, that's right. Changing the underlying representation from a string to a vector of integers will make things much faster as described in #24.

Apart from that, if someone can review the current multiplication implementation and suggest improvements it would be great!

[perlun]

What I ended up doing was to rewrite the BigInt implementation to use libtommath under the hood instead. The result is essentially a C++ wrapper (using the same public API as this lib) but using libttommath as "backend" for the actual arithmetic operations. 🙂

I also ended up removing some functions which are no longer needed (for me), and changed the const std::string& constructor to take a const char* parameter instead, since my use case is a bit C-oriented) so the end result is not 100% compatible with this lib... but here's the link anyway, if anyone wants or needs something similar: perlang-org/perlang#425

[perlun]

What I ended up doing was to rewrite the BigInt implementation to use libtommath under the hood instead. The result is essentially a C++ wrapper (using the same public API as this lib) but using libttommath as "backend" for the actual arithmetic operations. 🙂

In case anyone is interested in using this for some of their needs, here is my current implementation, based on @faheel's code. 🙏

• bigint.h
• bigint.cc

To compile this, you'll also need the libtommath sources (public domain-licensed). For inspiration on how to integrate this in your project, feel free to use my CMake file as reference: https://gitlab.perlang.org/perlang/perlang/-/blob/master/src/stdlib/CMakeLists.txt