Алгоритмы неформально. Инструкция для начинающих питонистов - [11]

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. Наконец, чтобы указать, что нам нужны все столбцы, после запятой ставится двоеточие — это сокращение означает, что нам нужны все столбцы.

Остается вычислить сумму оставшихся элементов doubling:

answer = sum(half_double.loc[:,1])

Здесь снова используется loc. Квадратные скобки указывают, что нам нужны все строки, для чего снова применяется сокращение с двоеточием. Мы указываем, что нам нужен вектор doubling (столбец с индексом 1 после запятой). Обратите внимание: рассмотренный нами пример 89 × 18 можно было бы реализовать быстрее и проще, если бы вместо этого вычислялось произведение 18 × 89. То есть если бы значение 18 находилось в столбце halving, а значение 89 — в столбце doubling. Попробуйте самостоятельно реализовать это улучшение. В общем случае RPM работает быстрее, если меньший множитель находится в столбце деления, а больший — в столбце умножения.

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