Я смотрел на алгоритм, который умножал 2 n бит чисел с 3 умножениями n/2 бит. Этот алгоритм считается эффективным. Хотя я понимаю, что пространство, очевидно, сохраняется, если я работаю над n-разрядной машиной, как будет улучшено n/2-битное умножение. Эти n/2-битные умножения будут преобразованы в n бит-умножений, потому что CPU может понимать только n бит-чисел.n/2 бит умножение на n бит cpu
Заранее спасибо.
Алгоритмы, подобные Karatsuba multiplication или Toom-Cook, обычно используются при реализации «bignums» - вычислений с числами неограниченного размера. Вообще говоря, чем сложнее алгоритм, тем большее число должно быть сделано, чтобы сделать это полезным.
Существует множество бонусных пакетов; одной из наиболее часто используемых является библиотека Gnu Multiprecision, gmplib, которая включает в себя большое количество различных алгоритмов умножения, выбирая подходящую по длине мультипликаторов. (Согласно wikipedia, Schönhage–Strassen algorithm, основанный на алгоритме быстрого преобразования Фурье, не используется до тех пор, пока множители не достигнут 33 000 знаков после запятой. Такие вычисления относительно редки, но когда вам нужно делать такие вычисления, вы, вероятно, заботитесь о это делается эффективно.)
хорошо, что не совсем ответит на мой вопрос. Я говорю, как n-разрядный компьютер обрабатывает n/2-разрядные вычисления? Если он обрабатывает его, то это же самое, что и n бит-вычислений, тогда нет необходимости пытаться реализовать Gauss. – user590849
@ user590849: Какова ваша ментальная модель n-разрядного компьютера? Может ли компьютер иметь, например, 64-битный ALU и 4 32-битных ALU? Или, 64-битное умножение выполняется непосредственно в кремнии, или оно микрокодировано с использованием более простых компонентов? И что бы означать «прямо в кремнии», во всяком случае ... это, конечно же, не означает таблицу с индексированным индексом с 128-битным индексом :) Но, возможно, это не то, о чем вы тоже просите. – rici
... В целом, если машина имеет код операции для умножения какого-либо размера, я бы склонен позволить этому сделать это, даже если это связано с сложным и неэффективным микрокодом на том основании, что следующее поколение тот же процессор, вероятно, сделает это лучше. С другой стороны, если n-разрядное умножение выполняется библиотекой программного обеспечения, включенной в состав компилятора, я мог бы при определенных обстоятельствах внести свой вклад в ее улучшение. – rici
Это чистая спекуляция, но звучит так, как будто это не программная техника, а аппаратная штука, т. е. у вас есть 16-разрядный блок множителей в аппаратном обеспечении, и с помощью этого алгоритма вы можете использовать эти блоки для создания чего-то похожего на 32-битный множитель снаружи. – us2012
Можете ли вы дать ссылку на алгоритм и что именно означает «эффективный»? И я полагаю, что есть некоторые условия, связанные с этим. – lurker
проверка умножения Гаусса. Обычно это делается для комплексного числа, но теория может быть применена к любым 2-битным номерам. – user590849