search

faheel / BigInt

Arbitrary-sized integer class for C++
https://faheel.github.io/BigInt
MIT License
383 stars 131 forks source link

Very slow compared to the GNU MP Bignum Library #69

Open 2catycm opened 2 years ago

2catycm commented 2 years ago

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 commented 10 months ago

See https://github.com/faheel/BigInt/issues/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 commented 10 months ago

@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 commented 6 months ago

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. :slightly_smiling_face:

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: https://github.com/perlang-org/perlang/pull/425