Возведение в квадрат в компьютерах.

[B@R5uk]

arseniiv в сообщении #1439433 писал(а):

Пожалуйста: https://gmplib.org/manual/Binary-to-Radix.html

Цитата:

Above GET_STR_PRECOMPUTE_THRESHOLD a sub-quadratic algorithm is used. For an input t, powers $b^{n\cdot 2^i}$ of the radix are calculated, until a power between t and $\sqrt{t}$ is reached. t is then divided by that largest power, giving a quotient which is the digits above that power, and a remainder which is those below. These two parts are in turn divided by the second highest power, and so on recursively.

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

[Dmitriy40]

B@R5uk в сообщении #1439425 писал(а):

$7.76/2.187=3.55$

Прошу прощения, я опечатался при вычислении в калькуляторе и получил неправильный коэффициент.

(Про частоты)

B@R5uk в сообщении #1439425 писал(а):

Да нет, тактовая частота процессора и частота тактов процессора — это обычно разные вещи. Правда как правило последняя не выше первой.

Вы лезете в дебри которыми похоже владеете слабо. Зачем? На процессор подаётся обычно вообще 100-133 МГц и уже из неё внутри получаются 2ГГц (в Вашем случае) — и именно на последней работает почти весь процессор, и весь конвейер с АЛУ, и регистры, и кэш L1, и возможно и кэш L2. И так как вычисления идут на частоте 2ГГц именно её и называют тактовой частотой процессора.
Если Вы подразумевали число что выдаёт команда rdtsc, то в разных процессорах и чипсетах оно по разному привязано к скорости работы вычислительного конвейера процессора (2ГГц) и его тактовой частотой процессора не называют. Меткой времени да, но не тактовой частотой.
Ну а то что команды выполняются целое число тактов (периодов тактовой частоты процессора) наверное очевидно.

(Такты)

B@R5uk в сообщении #1439425 писал(а):

В эти 26 тактов входит куча всяких накладных действий типа выделения и инициализации памяти и вычисления сумм.

Не обязательно, процессоры давно уже суперскалярные, т.е. выполняют более одной команды каждый такт, ваш до 4 команд одновременно, две из которых вычислительные. Потому сложение/вычитание и логические операции занимают по 0.5 такта (при спаривании), сдвиги по 1 такту, умножение 1-5 тактов (спаривание), деление 15-39 или 12-20 тактов (спаривание). Чтения и записи памяти могут быть и бесплатными если хорошо предсказуемы (подряд вперёд/назад). Сколько времени занимает выделение памяти под новую переменную и её запись в память надо измерять отдельно, но массивы выделяются сразу большим куском и потому в расчёте на разряд время будет мало.
Скорее всего тормозить будет именно деление, все остальные операции (кроме умножения) выполнятся параллельно с ним. Это во "внутреннем цикле", без всех этих служебных структур алгоритма и стека вызовов.