Остается вычислить сумму оставшихся элементов doubling:
answer = sum(half_double.loc[:,1])
Здесь снова используется loc. Квадратные скобки указывают, что нам нужны все строки, для чего снова применяется сокращение с двоеточием. Мы указываем, что нам нужен вектор doubling (столбец с индексом 1 после запятой). Обратите внимание: рассмотренный нами пример 89 × 18 можно было бы реализовать быстрее и проще, если бы вместо этого вычислялось произведение 18 × 89. То есть если бы значение 18 находилось в столбце halving, а значение 89 — в столбце doubling. Попробуйте самостоятельно реализовать это улучшение. В общем случае RPM работает быстрее, если меньший множитель находится в столбце деления, а больший — в столбце умножения.
Тому, кто уже запомнил таблицу умножения, алгоритм RPM может показаться бесполезным. Но помимо исторической ценности, его стоит изучить по нескольким причинам. Прежде всего, алгоритм показывает, что даже такую сухую операцию, как умножение чисел, можно выполнять по-разному, и в ней есть место для творческого подхода. Даже если вы освоили один алгоритм для какой-то задачи, это не означает, что он является единственным или лучшим алгоритмом для своей цели, — держите свой разум открытым для новых и, возможно, лучших решений.
RPM работает медленно, но требует меньших начальных усилий, поскольку вам не нужно заранее знать большую часть таблицы умножения. Иногда полезно пойти на небольшие потери скорости ради снижения затрат памяти, и этот баланс между скоростью/затратами памяти становится важным фактором во многих ситуациях с проектированием и реализацией алгоритмов.
Как и многие лучшие алгоритмы, RPM также подчеркивает отношения между разрозненными, на первый взгляд, идеями. Может показаться, что двоичное разложение представляет интерес только для создателей транзисторов, но бесполезно для обывателя или профессионального программиста. Однако RPM демонстрирует глубокую связь между двоичным разложением числа и удобным способом умножения, требующим минимальных знаний таблицы умножения. Это еще одна причина, по которой всегда следует продолжать учиться: никогда не знаешь, когда бесполезный, на первый взгляд, факт может оказаться основой для мощного алгоритма.
Алгоритм Евклида
Древние греки преподнесли человечеству много даров. Одним из самых выдающихся их изобретений стала теоретическая геометрия, которая была методично собрана великим Евклидом в серию из 13 книг, названную «Начала». Большая часть математических трудов Евклида написана в стиле «теорема/доказательство», при котором сложное предположение логически выводится из более простых. Некоторые из его работ также были конструктивными, то есть в них предоставлялся метод использования простых средств для построения полезных фигур или линий — например, квадрата с заданной площадью или касательной к кривой. И хотя сам термин «алгоритм» в то время еще не был придуман, конструктивные методы Евклида были алгоритмами, а некоторые из идей, лежащих в основе этих алгоритмов, актуальны и в наши дни.
Алгоритм Евклида вручную
Самый знаменитый алгоритм, описанный Евклидом, известен под названием алгоритма Евклида, хотя это всего лишь один из многих алгоритмов, о которых он писал. Алгоритм Евклида предназначен для нахождения наибольшего общего делителя двух чисел. Он прост и элегантен, а его реализация на Python состоит всего из нескольких строк.
Дано два натуральных (целых) числа: назовем их a и b. Допустим, a больше b (а если нет, то просто переименуйте a в b, а b в a, и тогда a будет большим). Если разделить a / b, то вы получите целое частное и целый остаток. Обозначим частное q1, а остаток c. Это можно записать так:
a = q1×b + c.
Например, если a = 105 и b = 33, то результат 105 / 33 равен 3, а остаток 6. Обратите внимание: остаток c всегда меньше как a, так и b — по определению остатка. На следующем шаге процесса мы забываем об a и концентрируемся на b и c. Как и прежде, допустим, что b больше c. Далее вычисляется частное и остаток при делении b / c. Обозначаем частное q2, а остаток d, и записываем результат:
