Учих книгата Структура и интерпретация на компютърни програмив свободното си време. Книгата използва езика за програмиране 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). Мислех, че е готин пример и исках да го споделя с всички вас. Надявам се и на вас да ви е интересно. Благодаря за четенето!