(Първо публикувано на 14.01.2017)
Днешният алгоритъм, който ще се опитам да ви обясня, е… умножение на числа!? Е, не точно, тук става дума за “бързо умножение”, т.е. как по-бързо да умножим някои по-големи числа без да се тормозим излишно.
ОПИСАНИЕ:
Това е алтернативен алгоритъм за умножение на числа, който е по-подходящ за големи числа. При имплементация се счита за по-ефективен от традиционния начин за умножение (имащ сложност О(n²)).
При този алгоритъм използваме само умножение и деление на 2 и събиране. Също така, алгоритъмът е доста удобен при работа с двоична бройна система (понеже можем да заменим умноженията и деленията на 2 с побитови операции изместване наляво и надясно, които са доста бързи).
АЛГОРИТЪМ:
1) Направете таблица с 3 колони:
- в първата напишете първото число
- във втората — второто
- третата остава празна засега.
2) Започнете да делите първото число на 2, като взимате само цялата част.
Записвайте резултатите последователно в първата колонка докато не стигнете до 1.
3) Умножете второто число по 2, толкова пъти колкото сте разделили първото.
Отново записвайте резултатите последователно.
4) В третата колонка прехвърлете всички резултати от втората колонка, които стоят до НЕЧЕТНО число от първата колона.
5) Съберете числата от третата колона и това е вашият резултат.
ПРИМЕР:
455 * 259 = ?
Първата стъпка е да си създадем таблицата. В началото тя ще изглежда така:
Следващата стъпка подсказва, че предстои да работим с първата колонка. Делим 455 на 2 и вземаме цялата част от това деление. Записваме резултата отдолу. Продължаваме да делим този резултат на 2 и записваме новия резултат отдолу. Така продължаваме докато не стигнем резултат 1 (т.е. на последния ред на 1-вата колона трябва да стои стойността 1):
След като приключим с тази стъпка от алгоритъма, таблицата ни ще изглежда така:
Сега започваме работа с втората колонка! Просто умножаваме 259 по 2, след това умножаваме резултата по 2 и така продължаваме докато не добавим стойност на последния ред (до 1-цата от колона 1).
След като приключим с тази стъпка от алгоритъма, таблицата ни ще изглежда така:
Нищо сложно! Сега остава да преместим стойностите от Колона 2, които стоят до нечетна стойност от Колона 1, в Колона 3.
Виждаме, че това са стойностите:
259 (стои до 455, което е нечетно число)
518 (до 227)
1036 (до 113)
16576 (до 7)
33152 (до 3)
66304 (до 1)
След като приключим с тази стъпка от алгоритъма, таблицата ни ще изглежда така:
Приключихме с работата си по таблицата! Сега просто остава да съберем всички стойности от Колона 3 и това ще е нашият краен резултат:
259 + 518 + 1036 + 16576 + 33152 + 66304 = 117845
→ 455 * 259 = 117845
ИМПЛЕМЕНТАЦИЯ (Java):
Следващата имплементация може да бъде значително оптимизирана.
Тя е просто пример как бихме представили алгоритъма като програмен код.
—
Това е за днес! Сигнализирайте, ако видите някоя неточност!
Top comments (0)