Когда C умножает два целых числа n-bits, использует ли он обычный алгоритм умножения O(n^2) или использует вариацию алгоритма умножения Карацаба O(n^log_2(3))?Использует ли C внутренний алгоритм Карацубы для умножения двух целых чисел?
№. Накладные расходы на «хранение книги» алгоритма Карацубы слишком высоки и слишком сложны. Это будет гораздо больше кремния, чем множитель, даже если это будет достижение безубыточной рекурсивной глубины на уровне машинного слова. Аппаратный крипто-ускоритель или FPGA может сделать его стоящим достаточно большим n. Даже тогда безубыточность может быть слишком высокой, чтобы быть полезной для криптографических потребностей. Нет бесплатного обеда.
На другом конце спектра, мы можем посмотреть на gmp-mparam.h файлы в GMP library, которые определяют пороговые значения, при которых асимптотически быстрые алгоритмы фактически начинают окупаться. «Карацуба» - это случай 2x2 более общего алгоритма Тоом-Кук. Даже на таких монстрах, как Broadwell и Skylake CPU, порог составляет около 28 слов, или 1792 бит. Это связано с накладными расходами (рекурсивно), добавляющими 3 результата назад вместе с переносом переноса. Эти пороговые значения будут продолжать увеличиваться по мере увеличения пропускной способности инструкций.
Стандарт C сам по себе не диктует такие детали реализации. Каждый компилятор выбирает соответствующие инструкции для каждой целевой архитектуры, поэтому он будет зависеть от этого набора команд. – StoryTeller
C - нет. Компилятор - возможно, нет. Базовая архитектура HW - может быть. –
C не имеет n-битовых целых чисел. – melpomene