Как умножаются целые числа в C ++?

Question

Мне было интересно, какой метод использовался для умножения чисел в C ++.Это традиционное учебное пособие с длинным умножением? Алгоритм Фюрера ? Toom-Cook ?

Мне было интересно, потому что мне нужно будет умножать чрезвычайно большие числа и нужна высокая степень эффективности.Следовательно, традиционное умножение в длинных книгах O(n^2) может быть слишком неэффективным, и мне нужно будет прибегнуть к другому методу умножения.

Answer 1

Кажется, вам здесь не хватает нескольких важных вещей:

1. Существует разница между нативным арифметическим и bignum арифметика.
2. Вы, кажется, интересуетесь bignum арифметика.
3. C ++ не поддерживает bignum арифметика.Примитивные типы данных, как правило, собственные арифметические для процессора.

Чтобы получить арифметику bignum (произвольная точность), вам нужно реализовать ее самостоятельно или использоватьбиблиотека.(например, GMP ) В отличие от Java и C # (среди прочих), C ++ не имеет библиотеки для арифметики произвольной точности.

Все эти причудливые алгоритмы:

• Карацуба: O(n^1.585)
• Toom-Cook: < O(n^1.465)
• На основе БПФ: ~ O(n log(n))

применимы только к арифметике bignum, котораяреализованы в библиотеках bignum.То, что процессор использует для своих собственных арифметических операций, несколько не имеет значения, поскольку обычно это постоянное время.

---

В любом случае, я не рекомендую вам пытаться реализовать библиотеку bignum.Я делал это раньше, и это довольно сложно (особенно математика).Так что вам лучше использовать библиотеку.

Answer 2

Что вы подразумеваете под "чрезвычайно большими числами"?

C ++, как и большинство других языков программирования, использует аппаратное обеспечение умножения, встроенное в процессор.Как это работает, не определено языком C ++.Но для обычных целых чисел и чисел с плавающей точкой вы не сможете писать что-то быстрее в программном обеспечении.

Наибольшие числа, которые могут быть представлены различными типами данных, могут различаться в разных реализациях, но некоторые типичные значения2147483647 для int , 9223372036854775807 для long и 1.79769e + 308 для double .

Answer 3

В C ++ целочисленное умножение обрабатывается чипом.В стандартном языке нет эквивалента Perl BigNum, хотя я уверен, что такие библиотеки существуют.

Answer 4

Насколько большими будут эти цифры? Даже такие языки, как python, могут выполнять 1e100*1e100 с произвольными целыми числами точности более 3 миллионов раз в секунду на стандартном процессоре. Это умножение на 100 значимых мест, занимающих менее одной миллионной секунды. Чтобы поместить это в контекст, есть только приблизительно 10 ^ 80 атомов в наблюдаемой вселенной.

Сначала напишите, чего вы хотите достичь, и, при необходимости, оптимизируйте позже.

Answer 5

Если вы работаете с большими числами, стандартное целочисленное умножение в c ++ больше не будет работать, и вам следует использовать библиотеку, обеспечивающую умножение с произвольной точностью, например GMP http://gmplib.org/

Кроме того, вам не следует беспокоиться о производительности донаписание вашего приложения (= преждевременная оптимизация).Эти умножения будут быстрыми, и, скорее всего, многие другие компоненты в вашем программном обеспечении вызовут гораздо большее замедление.

Answer 6

plain c ++ использует многопроцессорные инструкции CPU (или умножение в школьных учебниках с использованием битовых сдвигов и сложений, если у вашего CPU такой инструкции нет.)

если вам нужно быстрое умножение для больших чисел, я бы посоветовал посмотреть на gmphttp://gmplib.org) и используйте интерфейс c ++ из gmpxx.h

Answer 7

Выполняется аппаратно.по той же причине огромное количество не будет работать.Наибольшее число, которое c ++ может представлять в 64-битном оборудовании, - 18446744073709551616. Если вам нужны большие числа, вам нужна библиотека произвольной точности.

Answer 8

Все зависит от используемой библиотеки и компилятора.