AlgorithmO #12 - Бързо умножение

Днешният алгоритъм, който ще се опитам да ви обясня, е... умножение на числа!? Е, не точно, тук става дума за "бързо умножение", т.е. как по-бързо да умножим някои по-големи числа без да се тормозим излишно.

---

ОПИСАНИЕ:

Това е алтернативен алгоритъм за умножение на числа, който е по-подходящ за големи числа. При имплементация се счита за по-ефективен от традиционния начин за умножение (имащ сложност О(n^2)).

При този алгоритъм използваме само умножение и деление на 2 и събиране. Също така, алгоритъмът е доста удобен при работа с двоична бройна система (понеже можем да заменим умноженията и деленията на 2 с побитови операции изместване наляво и надясно, които са доста бързи).


АЛГОРИТЪМ:

1) Направете таблица с 3 колони:
- в първата напишете първото число
- във втората - второто
- третата остава празна засега.

2) Започнете да делите първото число на 2, като взимате само цялата част.
    Записвайте резултатите последователно в първата колонка докато не стигнете до 1. 

3) Умножете второто число по 2, толкова пъти колкото сте разделили първото.
     Отново записвайте резултатите последователно. 

4) В третата колонка прехвърлете всички резултати от втората колонка, 

     които стоят до НЕЧЕТНО число от първата колона.

5) Съберете числата от третата колона и това е вашият резултат.


ПРИМЕР:

455 * 259 = ?

Първата стъпка е да си създадем таблицата. В началото тя ще изглежда така:

Колона 1	Колона 2	Колона 3
455	259

Следващата стъпка подсказва, че предстои да работим с първата колонка. Делим 455 на 2 и вземаме цялата част от това деление. Записваме резултата отдолу. Продължаваме да делим този резултат на 2 и записваме новия резултат отдолу. Така продължаваме докато не стигнем резултат 1 (т.е. на последния ред на 1-вата колона трябва да стои стойността 1):

След като приключим с тази стъпка от алгоритъма, таблицата ни ще изглежда така:

Колона 1	Колона 2	Колона 3
455	259
455 / 2 = 227
227 / 2 = 113
113 / 2 = 56
56 / 2 = 28
28 / 2 = 14
14 / 2 = 7
7 / 2 = 3
3 / 2 = 1

Сега започваме работа с втората колонка! Просто умножаваме 259 по 2, след това умножаваме резултата по 2 и така продължаваме докато не добавим стойност на последния ред (до 1-цата от колона 1).

След като приключим с тази стъпка от алгоритъма, таблицата ни ще изглежда така:

Колона 1	Колона 2	Колона 3
455	259
455 / 2 = 227	259 * 2 = 518
227 / 2 = 113	518 * 2 = 1036
113 / 2 = 56	1036 * 2 = 2072
56 / 2 = 28	2072 * 2 = 4144
28 / 2 = 14	4144 * 2 = 8288
14 / 2 = 7	8288 * 2 = 16576
7 / 2 = 3	16576 * 2 = 33152
3 / 2 = 1	33152 * 2 = 66304

Нищо сложно! Сега остава да преместим стойностите от Колона 2, които стоят до нечетна стойност от Колона 1, в Колона 3. 

Виждаме, че това са стойностите: 

- 259 (стои до 455, което е нечетно число)

- 518 (до 227)

- 1036 (до 113)

- 16576 (до 7)

- 33152 (до 3)

- 66304 (до 1)

След като приключим с тази стъпка от алгоритъма, таблицата ни ще изглежда така:

Колона 1	Колона 2	Колона 3
455	259	259
455 / 2 = 227	259 * 2 = 518	518
227 / 2 = 113	518 * 2 = 1036	1036
113 / 2 = 56	1036 * 2 = 2072
56 / 2 = 28	2072 * 2 = 4144
28 / 2 = 14	4144 * 2 = 8288
14 / 2 = 7	8288 * 2 = 16576	16576
7 / 2 = 3	16576 * 2 = 33152	33152
3 / 2 = 1	33152 * 2 = 66304	66304

Приключихме с работата си по таблицата! Сега просто остава да съберем всички стойности от Колона 3 и това ще е нашият краен резултат:

259 + 518 + 1036 + 16576 + 33152 + 66304 = 117845

=> 455 * 259  = 117845

ИМПЛЕМЕНТАЦИЯ (Java):

Следващата имплементация може да бъде значително оптимизирана. 

Тя е просто пример как бихме представили алгоритъма като програмен код.

---

Това е за днес! Сигнализирайте ако видите някоя неточност!