Учих книгата Структура и интерпретация на компютърни програмив свободното си време. Книгата използва езика за програмиране Scheme, за да обясни и изследва концепциите в програмирането и компютърните науки. Това е страхотна книга с много дълбочина и силно я препоръчвам на всеки, който се интересува от някоя от тези области на изследване.
Едно от упражненията в книгата е да се създаде процедура, която може да умножи две числа (без използване на умножение или деление) за O(log n) времеи използвайки O(1) интервал силен>. Решението е наистина страхотно! Начинът, по който процедурата манипулира числата, е едновременно умен и елегантен. Нека да разгледаме как работи.
Постановка на проблема
Предполага се, че нашият език може само да събира и изважда, а не да умножава и дели. В такъв език целочисленото умножение може да се извърши чрез многократно добавяне. Следващата процедура демонстрира това и има времева сложност, която е линейна по b (O(n) времева сложност).
(define (* a b) (if (= b 0) 0 (+ a (* a (- b 1)))))
Като се има предвид този пример, упражнението в книгата се представя на читателя по следния начин:
Да предположим сега, че включваме, заедно със събиране, операции
double
, която удвоява цяло число, иhalve
, която дели (четно) цяло число на 2. Използвайки ги, проектирайте процедура за умножение, аналогична наfast-expt
, която използва логаритмичен брой стъпки.
По аналогия с fast-expt
, предишно упражнение в книгата, авторите просто имат предвид, че процедурата трябва да развие итеративен процес, който заема O(1) място и също трябва да предприеме логаритмичен брой стъпки.
Ето решението, което написах:
(define (* a b) (if (or (= a 0) (= b 0)) 0 (fast-mult-iter a b 0))) (define (fast-mult-iter a b sum) (cond ((= b 0) sum) ((even? b) (fast-mult-iter (double a) (halve b) sum)) (else (fast-mult-iter a (- b 1) (+ a sum))))) #| It is assumed that double and halve are implemented by the language. The following procedures are meant to simulate such implementations. |# (define (double n) (+ n n)) (define (halve n) (/ n 2))
TL;DR
Процедурата се редува между два модела: разполовяване на b
и удвояване на a
, докато b
стане странно; след това изваждане на 1 от b
и увеличаване на sum
с a
.
Как работи
По принцип процедурата работи, като разполовява b
и удвоява a
, докато b
стане нечетно число. Това е възможно поради асоциативните и комутативните свойства на умножението. След това изважда едно a
и го добавя към променлива на състоянието sum
чрез изваждане на 1 от b
. Сега b
отново ще бъде четно и процедурата може да продължи този модел: разполовяване на b
и удвояване на a
, докато b
стане нечетно, след което изваждане на 1 от b
и увеличаване на сумата с a
. Този модел продължава, докато b
стане нула, в който момент процедурата връща sum
.
Нека разгледаме това по-отблизо с пример. Да предположим, че прилагаме процедурата *
към 10 и 12. Тоест a
е 10, а b
е 12. Следната диаграма илюстрира този пример. Започвайки от горния ред и четейки диаграмата ред по ред, се демонстрира как променливите a
, b
и sum
се променят през жизнения цикъл на извикването на процедурата.
Ще разделим наполовина b
и ще удвоим a
, докато b
вече не е четно. Така a
става 20 и b
става 6. Тогава a
става 40 и b
става 3. Умножението е трансформирано в 40 x 3, което може да бъде представено като 40 + 40 + 40. Ако извадим едно 40 и го преместим в sum
, оставаме с 40 + 40 или 40 * 2 и b
отново е четно. Сега продължаваме модела на разполовяване и удвояване, така че a
да стане 80 и b
да стане 1. Тъй като b
вече е нечетно, можем да извадим едно 80 и да го преместим в sum
, така че да останем с a
от 80, b
от 0 и sum
от 80 + 40 = 120. Сега в последната итерация на процедурата, тъй като b
е нула, се връща сумата от 120.
Това е сравнително проста процедура, но наистина харесвам начина, по който манипулира числата с два преплетени модела. Предизвикателството при проектирането на алгоритъма беше ограничението за времева сложност O(log n) и пространствена сложност O(1). Мислех, че е готин пример и исках да го споделя с всички вас. Надявам се и на вас да ви е интересно. Благодаря за четенето!