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

Мне было интересно, какой метод использовался для умножения чисел на C++. Является ли это традиционным учебником длительного умножения? Fürer's algorithm? Toom-Cook?Как целые числа умножаются на C++?

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

Итак, какое умножение использует C++?

источник

2012-03-10 fdh

+13

Независимо от того, что делает чип, он делает. – bmargulies

Название заставило меня задуматься о целых числах, воспроизводящих :) – harold

@harold Сначала они должны сделать что-то, называемое «знакомства». – Manish

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

Там разница между родной арифметического и bignum арифметике.
Вы, кажется, заинтересованы в bignum арифметика.
C++ не поддерживает bignum арифметика. Обычно примитивными типами данных являются родной арифметика для процессора.

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

Все эти фантазии алгоритмов:

Карацуба: O(n^1.585)
Тоом-Кук: < O(n^1.465)
FFT на основе: ~ O(n log(n))

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

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

источник

2012-03-10 19:08:56 Mysticial

+1 для угадывания намерений OP :-) – hirschhornsalz

Пока вы не дойдете до очень больших чисел, метод, который вы изучили в начальной школе, будет лучше работать на практике. Конечно, вы используете большую базу, чем 10.:-) В зависимости от ваших потребностей 2^32, 2^64 или 10^9 делают удобные базы (полезная сила 10 - синтаксический анализ/печать ваших чисел в базе 10 важна для оптимизации, а 10^9 - это наибольшая мощность, которая соответствует 32 бит). –

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

источник

2012-03-10 19:07:07 gangelo

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

источник

2012-03-10 19:07:59 Joel

To nitpick: Не обязательно. Вполне возможно, что реализации могут включать в себя числовые типы (даже 'int', хотя *, которые должны быть довольно редкими), которые ориентированная архитектура не поддерживает, и вместо этого реализует арифметические операции над ними как вызовы в некоторую библиотеку времени исполнения. Рассмотрим 128-битные целые числа или, возможно, 64-битные целые числа в 32-битных системах. Кроме того, там было много чипов без единицы с плавающей запятой (FPU). – delnan

@delnan: Редкий, но не несуществующий: 8-разрядный процессор 6502 не имеет 16-разрядных арифметических команд, поэтому компилятор CC65 C должен реализовать арифметику 'int' через последовательности 8-битных инструкций и вызовов библиотеки. – han

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

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

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

источник

2012-03-10 19:08:37

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

источник

2012-03-10 19:09:42 Dani

Как насчет двухместных? Кроме того, точный размер большинства типов данных зависит от компилятора. Я также считаю, что некоторые компиляторы предлагают 128-битные целочисленные типы. – delnan

обычного C++ использует инструкцию процессора Mult (или Учебник умножение с использованием bitshifts и дополнения, если ваш процессор не имеет такую инструкцию.)

, если вам нужно быстро умножение для больших чисел, я хотел бы предложить, глядя на ГМПЕ (http://gmplib.org) и использовать ++ интерфейс с из gmpxx.h

источник

2012-03-10 19:11:27

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

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

источник

2012-03-10 19:12:37 johanvdw

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

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

источник

2012-03-10 19:21:45 Dunes

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

ответ

Смежные вопросы