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

[litwr]

Уважаемый blackmirror, благодарю вас за исходники на си и ещё раз за саму программку. Но вопрос остался, всегда ли X = 0? В ваших экранных картинках на 1000 знаков печатается 4 лишние знака. Немного раздражает, поэтому использовал счетчик по числу цифр, чтобы печатало точное число знаков - это всего 24 тактa на сдвоенную цифру, зато чисто. При расчете 3000 знаков время вывода на экран медленными средствами ОС - это всего около 3%. А средства ОС позволяют, например, записать результат в файл. Шрифт 5х4...
Хорошо бы приспособить затвор к 100-ичной системе, тогда получили бы более дружественный алгоритм и с такой же как и по Мачину скоростью. В затворе только одно деление...

[blackmirror]

litwr, что касается точности, то в начале мы имеем целые числа, когда мы их делим на 103 или 239 мы получаем почти точные числа, ошибка представления которых не превышает единицы последнего разряда. При последующих делениях эта ошибка уползает в более младшие разряды и дальше роли уже не играет, то есть можно считать что все слагаемые представлены с точностью до единицы последнего разряда. Когда из 32/10^n вычитается 40/239^n и 160/515^n здесь ошибка уже может быть от -2 до +1 единиц, но далее идёт деление на n, которое опять сделает ошибку не более единицы младшего разряда. В общем точность результата зависит от того, сколько слагаемых суммируется, для 100 цифр берётся 50 слагаемых, и при неудачном стечении обстоятельств в теории ошибка может достигать 50 единиц, но в среднем мне кажется из этой цифры нужно извлечь корень. А может еще и на два поделить, поскольку ряд знакопеременный.
А на затвор возлагать очень большие надежды не стоит, там во первых нужно обработать все байты числа, а во вторых сделать это столько раз, сколько в нём бит, тут даже с одним делением получается больше чем у Мачина.

[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?

[Advertiser]

[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 не получится.

[zebest]

Очередная и, надеюсь, последняя версия spigota - pirk20.zip
100 знаков - 19897238 тактов - 11.19 сек (это с расчетом таблицы!)
535 знаков - 551337754 тактов - 5 мин 10 сек

PVV по моей просьбе портировал этот код от уважаемого Ivagor-a на суперсовремённый югославский компьютер.
Хоть код и для 8080, но на Z80 работает аналогично, да и интересно было сравнить совершенно разные архитектуры на одном коде :-)
Как раз таки видно, насколько сильно тормозится более лучший Z80 с программной реализацией видео-контроллера( вернее отъедается производительности процессора на эту самую реализацию). Итак, результаты для 535 знаков:
1. PVV -

8.45 время выполнения теста на моем реале. кварц 6.144, тактовая Z80
6.144/2

2. на моем не-реале тот же тест - 8:35 в обычном режиме, и 4:18 - в Турбо х2 ( но и частота процессора немного выше - 3,125 МГц)
3. В эмуляторе от b2m - 8:44 - вполне сопоставимо.

16+

Все познаеЦЦа в сравнении. Мой текущий компьютер считает миллион знаков Pi за 14.437 секунды. На одном ядре разумеется.

[свернуть]

Дополнение.
100 знаков - 20с стандартно, и 6с с отключенными прерываниями и соответственно экраном.
и да, 535 знаков с отключенным экраном считается за 3 минуты, все же сильно видеовывод тормозит проц.

[zebest]

PVV по моей просьбе портировал этот код от уважаемого Ivagor-a

на этот раз на совсем другой компьютер 1977 г.р. Tandy Radio Shack TRS-80 - Model 1, собранный на горячо любимом Z80 c тактовой частотой всего 1,77 МГц, (практически Радио-86РК
Итак, встречаем! PI80 с инструкциями only 8080 посчитал 535 знаков за , ВНИМАНИЕ! - за 5 мин 17 сек.
Но и это еще не все.
Тот же компутер, но с программой оптимизированной под Z80 те же 535 знаков посчитал за 2 мин 04 сек
И еще одна программа-рекордсмен посчитала те же и там же всего то за каких то 47 сек
ну и напоследок, авдруг.
Эти две программы, с эмулятором, (в нем я не пробовал, но думаю сопоставимо), а главное с исходниками и комментами не на нашем языке можно посмотреть тут в самом низу страницы.
http://ht.homeserver.hu/html/programprojekt.html