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):

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

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

	/* Optimization ideas:
	- use less data structures
	- use less loops etc.
	*/
	import java.util.Scanner;
	import java.util.List;
	import java.util.ArrayList;
	public class Solution {
	public static void main(String[] args) {
	Scanner read = new Scanner(System.in);
	int firstNumber = read.nextInt();
	int secondNumber = read.nextInt();
	/*
	1) Направете таблица с три колони,
	в първата напишете първото число, а
	във втората - второто.
	Третата остава празна за момента.
	*/
	List<Integer> firstColumn = new ArrayList<Integer>();
	List<Integer> secondColumn = new ArrayList<Integer>();
	List<Integer> thirdColumn = new ArrayList<Integer>();
	firstColumn.add(firstNumber);
	secondColumn.add(secondNumber);
	/*
	2) Започнете да делите първото число на две,
	като взимате само цялата част.
	Записвайте резултатите последователно в първата колонка,
	докато не стигнете до 1.
	*/
	while (firstNumber != 1) {
	firstNumber /= 2;
	firstColumn.add(firstNumber);
	}
	/*
	3) Умножете второто число по две,
	толкова пъти колкото сте разделили първото и
	отново записвайте резултатите последователно.
	*/
	int numberOfDivisions = firstColumn.size()-1;
	for (int i = 0; i < numberOfDivisions; ++i) {
	secondNumber *= 2;
	secondColumn.add(secondNumber);
	}
	/*
	4) В третата колонка
	прехвърлете всички резултати от втората колонка,
	които стоят до нечетно число от първата колона.
	*/
	for (int i = 0; i < secondColumn.size(); ++i) {
	if (firstColumn.get(i) % 2 != 0) {
	int currentElementFromSecondColumn = secondColumn.get(i);
	thirdColumn.add(currentElementFromSecondColumn);
	}
	}
	// 5) Съберете числата от третата колона и това е вашият резултат.
	int result = 0;
	for (int i = 0; i < thirdColumn.size(); ++i) {
	int currentElementFromThirdColumn = thirdColumn.get(i);
	result += currentElementFromThirdColumn;
	}
	// Print end result
	System.out.println(result);
	// Close scanner
	read.close();
	}
	}

view raw ALGORITHMO-12-Fast-Multiplication-Algorithm-Implementation.java hosted with ❤ by GitHub

---

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