kealon(Ruslan)...
если о цели: я может чего не понимаю, но какой смысл выполнять обычный алгоритм "умножение столбиком"?

ничего общего от слова совсем:
столбик сформулирован в терминах позиционного представления числа
а египетскому умножению (он же - russian peasant algorithm) до лампады представление числа.
Он работает в терминах удвоения, деления пополам и определения четности.
К тому, что понятно как удваивать - 100% шансы применить этот алгоритм.
Попробуйте применить столбик к размножению строк.
А египетское умножение отменно обеспечивает умножение целых чисел, возведения их в степень,
возведение в степень квадратных матриц, кватернионов и строк, а как бонус еще и вычисление чисел Фибоначчи.
Возведения в целую степень вообще всего, что может быть мыслимо как полугруппа с ассоциативной операцией.
Книжка эта про обобщенное программирование, а египетское умножение - базовый алгоритм, на примере которого и раскрывается представление об обобщенном программировании.

kealon(Ruslan)Basil A. Sidorov,

я в плане алгоритма, зачем использовать заведомо O(n^2), можно для начала взять хотя бы тот же алгоритм Карацубы
Зря вы это сказали.
Алгоритмы анализируются в ценах элементарных (базовых для анализа) операций.
Для этого алгоритма элементарной операцией является операция сложения.
И выполняется она Log(n) раз.
То есть, с точки зрения выполнения базовых операций, с ростом масштаба задачи, данный алгоритм масштабируется
как суперконстанта по отношению к числу выполняемых базовых операций.
Надо совсем не иметь представления об обсуждаемом предмете, чтобы задавать вопрос - зачем рассматривать такой алгоритм.

maytonЗависимые функции четности и деления пополам - half(),odd() я поскипаю. Они тривиальны.
Дело не в том, тривиальны они или нет, а в том, какое поведение они ожидают от применяемого к ним параметра.
В данном случае - поведение (целого) числа.
Именно это и определяет направление дальнейшего будущего обобщения.
Поэтому таким алгоритмом имеет смысл возводить квадратные матрицы в целую степень или размножать строки целое число раз, при условии, что базовая операция умножения матрицы или склейки строк будет предоставлена той полугруппой, которую представляет соответствующий параметр функции.
А вот умножать строки на строки, или матрицы на матрицы таким алгоритмом нельзя.

mayton,

не знаю, зачем ты это написал.
Если ты опять про "элементарность реализации", то я опять о том, что существо дела в другом.

Параметры, передаваемые в алгоритм неравноценны и обобщаются по разному.
Для n здесь нет толкового обобщения, отличного от смысла целого числа.

Т.е. параметры у алгоритма неравноценны:
а - может быть представлено любым типом, обеспечивающим поведение полугруппы
n - может быть только типом, эквивалентным целому числу.