2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5
 
 Re: Возведение в квадрат в компьютерах.
Сообщение11.02.2020, 19:57 
Аватара пользователя


26/05/12
1534
приходит весна?
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 
Заслуженный участник


20/08/14
11066
Россия, Москва
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

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group