Algorithms - Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2006)

Перемножаем так:

Выписываем в столбик первое число по следующим правилам: умножаем на соответствующую цифру второго числа (идём с конца) со сдвигом 0, 1, 2, …, n - 1. Короче, как обычные числа, только в 2 системе счисления.

Complexity: O(n^2)

Al Khwarizmi algorithm

Выпиши 2 числа. Первое делим на 2 с отбрасыванием дробной части (если нужно), второе умножаем на 2. Потом вычеркиваем строки с четными левыми цифрами и складываем все незачеркнутые цифры справа.

Algorithms - Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2006)

Algorithms - Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2006)