Алгоритм умножения
Алгоритм умножения — это алгоритм (или метод) умножения двух чисел. В зависимости от размера чисел используются разные алгоритмы. Эффективные алгоритмы умножения существовали с момента появления десятичной системы.
Если используется позиционная система счисления , естественный способ умножения чисел преподается в школах как длинное умножение , иногда называемое умножением в начальной школе , иногда называемое стандартным алгоритмом : умножьте множимое на каждую цифру множителя , а затем сложите все правильные числа. сдвинутые результаты. Это требует запоминания таблицы умножения для однозначных цифр.
Это обычный алгоритм умножения больших чисел вручную по основанию 10. Человек, выполняющий длинное умножение на бумаге, запишет все произведения, а затем сложит их вместе; пользователь счетов будет суммировать произведения, как только будет вычислено каждое из них.
В этом примере используется длинное умножение для умножения 23 958 233 (множимое) на 5 830 (множитель) и получается 139 676 498 390 в результате (произведение).
Ниже псевдокод описывает процесс вышеуказанного умножения. Он сохраняет только одну строку для сохранения суммы, которая в конечном итоге становится результатом. Обратите внимание, что оператор '+=' используется для обозначения суммирования существующего значения и операции сохранения (аналогично таким языкам, как Java и C) для компактности.
Некоторые чипы реализуют длинное умножение аппаратно или в микрокоде для различных целых чисел и слов с плавающей запятой. В арифметике произвольной точности обычно используется длинное умножение с основанием, равным 2 w , где w — количество битов в слове, для умножения относительно небольших чисел. Чтобы умножить два числа из n цифр с помощью этого метода, нужно примерно n 2 операций. Более формально, умножение двух n -значных чисел с использованием длинного умножения требует Θ ( n 2) однозначные операции (сложения и умножения).
