2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3, 4, 5
 
 Re: Возведение в квадрат в компьютерах.
Сообщение11.02.2020, 19:57 
Аватара пользователя
arseniiv в сообщении #1439433 писал(а):
Цитата:
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.

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

 
 
 
 Re: Возведение в квадрат в компьютерах.
Сообщение11.02.2020, 21:29 
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 тактов (спаривание). Чтения и записи памяти могут быть и бесплатными если хорошо предсказуемы (подряд вперёд/назад). Сколько времени занимает выделение памяти под новую переменную и её запись в память надо измерять отдельно, но массивы выделяются сразу большим куском и потому в расчёте на разряд время будет мало.
Скорее всего тормозить будет именно деление, все остальные операции (кроме умножения) выполнятся параллельно с ним. Это во "внутреннем цикле", без всех этих служебных структур алгоритма и стека вызовов.

 
 
 [ Сообщений: 62 ]  На страницу Пред.  1, 2, 3, 4, 5


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group