Почему же эта схема работает? В действительности RPM является алгоритмом внутри алгоритма. Сам столбец деления может считаться реализацией алгоритма, который находит сумму степеней 2, равную числу в первой ячейке столбца. Сумма степеней 2 также называется двоичным разложением числа 89. Двоичная система представляет собой альтернативную схему записи чисел с использованием только 0 и 1; она стала играть особенно важную роль в последние десятилетия, поскольку компьютеры хранят информацию в двоичном виде. В двоичной записи число 89 записывается в виде 1011001, с единицами в нулевой, третьей, четвертой и шестой позиции (справа налево); номера позиций соответствуют номерам нечетных строк столбца деления, а также степеням нашего уравнения. 1 и 0 в двоичном представлении можно рассматривать как коэффициенты в сумме степеней 2. Например, двоичное число 100 интерпретируется следующим образом:
1 × 22 + 0 × 21 + 0 × 20
или 4 в обычной (десятичной) записи. Двоичное число 1001 интерпретируется так:
1 × 23 + 0 × 22 + 0 × 21 + 1 × 20.
или 9 в обычной записи. После выполнения мини-алгоритма для получения двоичного разложения 89 можно легко выполнить полный алгоритм и завершить процесс умножения.
Реализация RPM на Python
Реализация RPM на Python получается относительно простой. Допустим, вы хотите умножить два числа; назовем их n1 и n2. Для начала откроем сценарий Python и определим эти переменные:
n1 = 89
n2 = 18
На следующем шаге начнем строить столбец деления. Как упоминалось выше, он начинается с одного из перемножаемых чисел:
halving = [n1]
Следующий элемент равен halving[0]/2 с игнорированием остатка. В Python для округления можно воспользоваться функцией math.floor(). Функция просто находит ближайшее целое число, которое меньше заданного. Например, вторая строка столбца деления вычисляется так:
import math
print(math.floor(halving[0]/2))
Выполнив этот код в Python, вы увидите, что результат равен 44.
Программа перебирает все строки столбца деления, при каждой итерации цикла находит следующее значение в данном столбце и останавливается при достижении 1:
while(min(halving) > 1):
halving.append(math.floor(min(halving)/2))
В цикле метод append() используется для конкатенации. При каждой итерации цикла while вектор деления объединяется с половиной его последнего значения, при этом функция math.floor() используется для игнорирования остатка.
Со столбцом умножения делаем то же самое: мы начинаем с 18 и запускаем цикл. При каждой итерации цикла в столбец умножения добавляется удвоенное последнее значение. Цикл останавливается, когда длина этого столбца достигнет длины столбца деления:
doubling = [n2]
while(len(doubling) < len(halving)):
doubling.append(max(doubling) * 2)
Наконец, эти два столбца помещаются в кадр данных half_double:
import pandas as pd
half_double = pd.DataFrame(zip(halving,doubling))
Здесь импортируется модуль Python pandas. Он упрощает работу с таблицами. В данном случае используется команда zip, которая соединяет halving с doubling подобно тому, как застежка-«молния» соединяет две полы куртки. Два набора чисел halving и doubling создаются как независимые списки, а после соединения и преобразования в кадр данных pandas сохраняются в таблице в виде двух параллельных столбцов, как показано выше в табл. 2.5. Поскольку столбцы выровнены и соединены, мы можем обратиться к любой строке табл. 2.5 (например, третьей) и получить всю строку данных, включающую элементы из halving и doubling (2 и 72). Возможность обращаться к этим строкам и работать с ними позволяет легко удалить ненужные строки, как было сделано с табл. 2.5 для преобразования ее в табл. 2.6.
Теперь необходимо удалить строки с четными значениями в столбце деления. Для проверки четности можно воспользоваться оператором % языка Python, возвращающим остаток от деления. Если число x нечетно, то x%2 будет равно 1. Следующая строка оставляет в таблице только те строки, у которых значение в столбце деления является нечетным:
half_double = half_double.loc[half_double[0]%2 == 1,:]
В данном случае для отбора только интересующих нас строк используется функциональность loc модуля pandas. При использовании loc отбираемые строки и столбцы заключаются в квадратные скобки ([]). В них нужные строки и столбцы перечисляются через запятую: [строка,столбец]. Например, если вам нужна строка с индексом 4 и столбец с индексом 1, то можно прибегнуть к записи half_double.loc[4,1]. При этом ваши возможности не ограничиваются простым указанием индексов. Можно записать логический шаблон для отбора нужных строк: нас интересуют все строки, где halving содержит нечетное значение. В нашей логике столбец halving обозначается half_double[0], то есть столбец с индексом 0. Нечетность определяется условием %2==1. Наконец, чтобы указать, что нам нужны все столбцы, после запятой ставится двоеточие — это сокращение означает, что нам нужны все столбцы.
