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

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

kealon(Ruslan)Basil A. Sidorov,

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

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

mayton,

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

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

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

ок

точно.

Для строгой хвостовой рекурсии есть железобетонный, гарантированный алгоритм разворота
в простой цикл.
Поэтому, в таком случае, программист имеет право писать "красиво", а обученный компилятор
сделает "как надо".

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

petrav,

тут дела так стоят:
Использование рекурсии вообще какой-то - неотделимо от императивного программирования.
Заявить несовместимость рекурсии с языком эквивалентно заявлению о неспособности
реализовать в этом языке циклический алгоритм произвольного вида.

Рекурсия вообще - это идея циклического алгоритма вообще.
Специальные случаи вроде строгой хвостовой позволяют свести алгоритм к простому циклу.
Например, свести самому программисту (и не ошибиться при этом), даже если компилятор этого делать не умеет.
Делать это или нет - вопрос борьбы за время организации вызова и передачи параметров.

booby,

ну, для каких-то случаев - еще и за размер стека.