Вычисление числа Пи на ассемблере

[litwr]

А для заинтересовавшихся с другими процессорами хорошо бы и алгоритм на ЯВУ выложить...

[Advertiser]

[blackmirror]

Поскольку в теме про Быстрое умножение на 10000 мой алгоритм раскритиковали:

Приведен пример красивого алгоритма. Если посмотреть на него в контексте расчета π, то мне кажется, что уважаемый blackmirror реализовал не самый быстрый расчёт

пришлось его допилить. Без потерь не обошлось, и для 100 цифр он стал считать медленнее, но для 300 цифр ускорился в полтора раза, а для 1000 и далее в ДВА (офигеть!). Если посмотреть любимую нашу табличку, то затвор на MSX показывает в 10 раз худшие результаты, а Мачин позволяет приблизиться к microPDP-11/83 и Commodore SuperCPU-64(кстати, есть ли у них аппаратное умножение?). Самый интересный результат может получиться, если запустить Мачина на MSX turbo R, хотя это будет совсем не спортивно.
В архиве программка на 4К цифр, и две картинки с результатами для 100,300,1K-10К цифр(более 4К цифр может считать другая версия), время вывода не учитывается, поскольку pi не влезает на экран.
pi_4k.zip

[litwr]

Потрясающе! А ещё если заоптимизировать, то ещё можно почти наверняка 10-30% выжать. На отстойном 65816 нет аппаратного умножения. Но если переписать вашу программку на другие платформы, то опять получится картинка как и по затвору. Подозреваю, что формула типа 48·arctan(1/49) + 128·arctan(1/57) − 20·arctan(1/239) + 48·arctan(1/110443) будет ещё быстрее. Немного истории http://www.ams.org/journals/mcom/196...-0136051-9.pdf Следующий шаг - 100000? Кстати, кое-кто научился делать арктангентсы без деления - https://www.msx.org/forum/msx-talk/d...t-atan2?page=0

[blackmirror]

Самое неоптимальное там это прямое деление, но оно используется только для 19% множителей, а по количеству обрабатываемых байт это вообще 3.5%, но если его ускорить с 400 тактов до 300, то перейти на него можно будет раньше. Как по затвору точно не получится, поскольку по числу операций родственник затвора это формула atan(1/2)+atan(1/3), а в ней делить на N нужно в 3.22 раз больше. Сейчас по общим затратам времени:
формирование 32/10^n - 2% (в общем почти даром)
вычисление 40/239^n с инверсией - 18%
вычисление вычисление 160/515^n с вычитанием - 23% (хоть таких слагаемых и меньше, но дополнительное деление на 25 и честное вычитание дают о себе знать)
деление на N занимает - 43% (по прежнему самая затратная операция)
добавление к pi - 15% (нужно бы развернуть все вычитания, но лень)
Увеличение первого делителя до 49 позволит сократить количество последних двух операций на 40%, то есть выиграть 25% от общего времени, но если оставаться в 100-ой системе, то по прикидкам деление на 49 займёт 28% времени, а еще нужно делить на 110443 и в итоге мы полностью пролетаем. А искать арктангенсы без деления у нас не получится, поскольку числа существенно длиннее.

[litwr]

Писал о том, что если взять любой алгоритм по числу π и перенести его на разные платформы, то результат будет примерно такой же как и по затвору. Основательно с Мачином разобрались. Прямое деление за 300 тактов?! Это сколько разрядов в делителе и делимом? Неужели 16 и 32?

[blackmirror]

litwr, Ну для других алгоритмов такой обширной таблички пока еще нет, кроме того для разных машин могут быть удобны разные формулы Мачина.
Ну а для i8080 перед делением 16 разрядный остаток по таблице умножается на 100, получается 24 разряда, к нему добавляется очередная цифра, далее старшие 16 бит делятся при помощи 8 блоков ADD HL,HL/ADD HL,DE/JR C,XXX/ADC A, которые выполняются за 33/38 тактов, ну а в конце добавляется оставшийся байт и за примерно 400 тактов получается новый остаток.
Корректно деление работает только с остатками до 2^14, чего при выбранной формуле хватает для вычисления 16000+ десятичных цифр, но тогда для табличек места не остаётся. Основной упор алгоритм делает на табличное деление: числа 239 и 103 хороши тем, что они больше 100 и влезают в байт, поэтому после сложения сразу ясно нужна ли коррекция. Число 25 кратно 100, что тоже упрощает деление, а вот деление на 57 не настолько удобно, поскольку в некоторых случаях требует дополнительную проверку и коррекцию остатка и частного. За счёт использования 100-ой системы деление на 239^2=57121 выполняется примерно за 120 тактов на байт, а деление на 515^2=265225 выполняется примерно за 170 тактов на байт.

[ivagor]

Тему после перерыва практически не читал, только последнюю страницу. Похоже есть значительные успехи, но сложно с ходу сориентироваться, на сколько конкретно.
Обращу внимание, что в pi_4k.zip blackmirrora написано "использует только инструкции 8080". При беглом просмотре увидел несколько инструкций, уникальных для z80, т.е. просто откомпилировать и запустить на 8080 не получится.

[ivagor]

Тем более не стоит сравнивать эффективность систем команд 8080 и z80 на примере разных алгоритмов (даже не модификаций одного алгоритма).

[Lethargeek]

Тем более не стоит сравнивать эффективность систем команд 8080 и z80 на примере разных алгоритмов (даже не модификаций одного алгоритма).

зато вполне можно сделать вывод об эффективности по востребованности новых команд z80
если их при оптимизации применяют - значит, с ними эффективнее, чем без них
несогласные могут попытаться переписать исходники z80 в более быстрый код 8080 (удачи им)))

[ivagor]

зато вполне можно сделать вывод об эффективности по востребованности новых команд z80
если их при оптимизации применяют - значит, с ними эффективнее, чем без них

Сделать вывод об эффективности команд можно при сравнении процедур, реализующих один алгоритм и оптимизированных соответственно для 8080 и z80. В сравнении разные алгоритмы + и там и там далеко не самые оптимизированные процедуры. Т.е. то сравнение нельзя использовать для формулирования конкретных выводов об эффективности (какие команды и на сколько эффективнее). А общие слова "некоторые новые команды z80 эффективнее 8080" стоят мало, с ними никто и не спорил (в конверсиях z80->8080 постоянно возникала проблема переделки критичных мест, если там используются уникальные возможности z80).