How do integers multiply in C ++?

I was wondering which method was used to multiply numbers in C ++. Is this a traditional long multiplication textbook? Fuhrer algorithm ? Toom Cook ?

I was interested because I would need to multiply extremely large numbers and need high efficiency. Therefore, the traditional multi-user tutorial O(n^2) may be too inefficient, and I will need to resort to another method of multiplication.

So what kind of multiplication does C ++ use?

+6
source share
8 answers

You seem to be missing a few important things here:

  • There is a difference between native arithmetic and bignum arithmetic.
  • It seems to you that you are interested in arithmetic bignum .
  • C ++ does not support bignum arithmetic. Primitive data types are typically native processor arithmetic.

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

All these fantastic algorithms:

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

applicable only to binum arithmetic, which are implemented in bigmoon libraries. What the processor uses for its own arithmetic operations is somewhat irrelevant, since it is usually a constant time.


In any case, I do not recommend that you try to implement the bignum library. I have done this before, and it is quite demanding (especially math). Therefore, you better use the library.

+23
source

What do you mean by "extremely large numbers"?

C ++, like most other programming languages, uses multiplication hardware built into the processor. Exactly how this works, the C ++ language is not specified. But for normal numbers and floating point numbers, you won't be able to write something faster in software.

The largest numbers that can be represented by different data types may vary between different implementations, but some typical values ​​are: 2147483647 for int , 9223372036854775807 for long and 1.79769 e + 308 for double .

+3
source

In C ++, integer multiplication is processed by the chip. There is no Perl BigNum equivalent in the standard language, although I am sure that such libraries exist.

+1
source

It all depends on the library and compiler used.

0
source

Runs in hardware. for the same reason, huge numbers will not work. The largest number of C ++ can represent in the 64-bit hardware 18446744073709551616. If you need large numbers, you need a library with arbitrary precision.

0
source

plain C ++ uses CPU mult commands (or multiplying school books using bit shifts and additions if your processor does not have such an instruction.)

if you need fast multiplication for large numbers, I would suggest looking at gmp ( http://gmplib.org ) and using the C ++ interface from gmpxx. h

0
source

If you work with large numbers, the standard integer multiplication in C ++ will no longer work, and you should use a library that provides arbitrary exact multiplication, for example GMP http://gmplib.org/

In addition, you should not worry about efficiency before writing the application (= premature optimization). These multiplications will be fast, and most likely many other components of your software will cause a significant slowdown.

0
source

How big are these numbers? Even languages ​​like python can run 1e100*1e100 with integer integers more than 3 million times per second on a standard processor. This is a multiplication by 100 significant places, occupying less than one millionth of a second. To put this in context, there are only about 10 ^ 80 atoms in the observable universe.

Write down what you want to achieve first, and optimize later if necessary.

0
source

Source: https://habr.com/ru/post/910417/


All Articles