Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How do integers multiply in C++?

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?

like image 969
fdh Avatar asked Mar 10 '12 19:03

fdh


1 Answers

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.

like image 74
Mysticial Avatar answered Sep 30 '22 02:09

Mysticial