How do integers multiply in C++?

Question

I was wondering what kind of method was used to multiply numbers in C++. Is it the traditional schoolbook long multiplication? Fürer's algorithm? Toom-Cook?

I was wondering because I am going to need to be multiplying extremely large numbers and need a high degree of efficiency. Therefore the traditional schoolbook long multiplication O(n^2) might be too inefficient, and I would need to resort to another method of multiplication.

So what kind of multiplication does C++ use?

Answer 1

You seem to be missing several crucial things here:

1. There's a difference between native arithmetic and bignum arithmetic.
2. You seem to be interested in bignum arithmetic.
3. C++ doesn't support bignum arithmetic. The primitive datatypes are generally native arithmetic to the processor.

To get bignum (arbitrary precision) arithmetic, you need to implement it yourself or use a library. (such as GMP) Unlike Java, and C# (among others), C++ does not have a library for arbitrary precision arithmetic.

All of those fancy algorithms:

• Karatsuba: O(n^1.585)
• Toom-Cook: < O(n^1.465)
• FFT-based: ~ O(n log(n))

are applicable only to bignum arithmetic which are implemented in bignum libraries. What the processor uses for its native arithmetic operations is somewhat irrelevant as it's usually constant time.

---

In any case, I don't recommend that you try to implement a bignum library. I've done it before and it's quite demanding (especially the math). So you're better off using a library.