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

[ivagor]

ПК-6128Ц позволил поставить рекорд по количеству цифр Пи для 8-битных ретрокомпьютеров - 8928! Ну и скорость по сравнению с 06Ц повыше за счет ВМ85.


100 цифр - 2.34 секунды
1000 цифр - 207.18 секунды = 3 минуты 27.18 секунды
3000 цифр - 1855.32 секунды = 30 минут 55.32 секунды
8928 цифр - 17150.96 секунды = 4 часа 45 минут 50.96 секунды
Для 8928 цифр пришлось увеличить число экранов до 3 (по окончанию расчета переключаются клавишами '1'-'3'). Зато раз уж 3 экрана, то цифры можно сильно не ужимать, 6 и 9 здесь "широкие".

[ivagor]

Немного дополню. Ранееприведенный spigot для 6128 ставит рекорд по количеству цифр среди известных мне программ. Однако существуют могучие 8-битные ретромашинки, которые способны посчитать в разы больше цифр, но таких программ для них (пока?) не написали. Более того, можно посчитать больше цифр и на 6128, но скорость уменьшится.
После версии для 6128 сообразил, как резко увеличить число цифр для 06Ц (без квазидиска или других расширений памяти) при сохранении возможности проверки всех цифр. 8192 цифры - рекорд для 8080 среди известных мне программ, хотя есть компы с 8080 у которых больше памяти и они в принципе могут превзойти. Эта версия еще и чуть быстрее, поэтому две предыдущие (57 и 59) удалил.
Особенности отображения цифр - до трех экранов (по окончанию расчета переключаются кнопками '1'-'3'), причем на первом цифры занимают только правую половину. При расчете 8192 цифр в левую часть экрана залезает конец буфера, но потом эта половина очищается от "мусора".
Привожу скриншоты только для 8192 цифр, в архиве бинарники (и исходник) для расчета всех вариантов.

100 цифр - 2.78 секунды
1000 цифр - 238.94 секунды = 3 минуты 58.94 секунды
3000 цифр - 2134.18 секунды = 35 минут 34.18 секунды
8192 цифры - 16947.38 секунды = 4 часа 42 минуты 27.38 секунды

[litwr]

Немного дополню. Ранееприведенный spigot для 6128 ставит рекорд по количеству цифр среди известных мне программ. Однако существуют могучие 8-битные ретромашинки, которые способны посчитать в разы больше цифр, но таких программ для них (пока?) не написали. Более того, можно посчитать больше цифр и на 6128, но скорость уменьшится.
После версии для 6128 сообразил, как резко увеличить число цифр для 06Ц (без квазидиска или других расширений памяти) при сохранении возможности проверки всех цифр. 8192 цифры - рекорд для 8080 среди известных мне программ, хотя есть компы с 8080 у которых больше памяти и они в принципе могут превзойти. Эта версия еще и чуть быстрее, поэтому две предыдущие (57 и 59) удалил.
Особенности отображения цифр - до трех экранов (по окончанию расчета переключаются кнопками '1'-'3'), причем на первом цифры занимают только правую половину. При расчете 8192 цифр в левую часть экрана залезает конец буфера, но потом эта половина очищается от "мусора".
Привожу скриншоты только для 8192 цифр, в архиве бинарники (и исходник) для расчета всех вариантов.

100 цифр - 2.78 секунды
1000 цифр - 238.94 секунды = 3 минуты 58.94 секунды
3000 цифр - 2134.18 секунды = 35 минут 34.18 секунды
8192 цифры - 16947.38 секунды = 4 часа 42 минуты 27.38 секунды

Впечатляющий результат! 10-летний распил затворного алгоритма привел к созданию чего-то почти шедеврального. Одноко слово "почти" совсем не лишнее. Автор похоже как всегда не смог избежать соблазна использовать сомнительные трюки, похожие на мелкое шулерство, в частности:
1) трюк издевательства над пользователем путём показа ему мелкомелких цыфирок. Нормальные цифры замедлили бы расчет совершенно незначительно и особенно для большого числа знаков;
2) использование какого-то ненастоящего алгоритма-затвора, в настоящем алгоритме Вагона-Рабиновича на цифру числа π должно выделяться ровно 7 байт;
3) в отсутствие алгоритма на ЯВУ, в отличие, например, от @blackmirror, который выложил сначала свой супербыстрый алгоритм в общем виде.
А тем временем британцы начали проект других затворов. Мачина они явно с этим догнать не смогут, а вот перегнать код для Вектора скорее должны.

ДОПОЛНЕНИЕ. Поспешил с претензиями 2 и 3 - это похоже тот самый затвор, извиняюсь. Но такое большое количество цифр сбивает с толку. Респект Вам @ivagor, но цифирки можно и побольше.

[litwr]

ПК-6128Ц позволил поставить рекорд по количеству цифр Пи для 8-битных ретрокомпьютеров - 8928!

Англичане на своей бибисишке с 32 КБ ОЗУ смогли высчитать 16200 цифр за примерно 7.4 часов. Но Мачин уважаемого blackmirror'a пока в 4 раза быстрее на 1000 знаков. Однако Вектор они обогнали во всём как абсолютно, так и относительно. Особенно хорошо они всё оформили, прямо хоть в энциклопедию!
Коды уважаемого ivagor'a спровоцировали моё желание улучшить свой порт для компьютеров на базе 8080. В результате получился код более чем на целый процент быстрее, чем у уважаемого ivagor'a, - сам этому удивился, так как часть его кодотрюков до сих пор не понял. Не понял, в частности, что он cделал с делением уважаемого blackmirror'a - сам его просто закопипастил.
Итак, на 3000 цифр версия 61 кода уважаемого ivagor'a требует 2278 секунд, а версия 6 кода litwr'a - 2254. Запускал не исходную программу уважаемого ivagor'a, а её модификацию под СР/М или Монитор. Этот модифицированный код прикрепляется. Из-за плохого знания клинописи на 8080 перевел также её на более привычный язык Z80.
Таким образом, исходный код для bare metal от уважаемого ivagor'a по прежнему абсолютный Вектор-чемпион по затвору Вагона-Рабиновича, но это не из-за превосходного качества кодов, а из-за выбранной системы, точнее отказа от любой операционной системы. За bare metal процедуру печати мелких циферок ускорение всего-то менее полпроцента на 3000 знаков, а вот кастомный мини-обработчик прерываний даёт заметный прирост в более 6%.
Сам хотел сделать такой обработчик, но монитор не делает скроллинга без стандартного тормозного обработчика. А делать bare metal с нормальным шрифтом пока не готов, не считаю себя ещё истинным вектористом. Но если делать, то цифр должно бы получиться чуть больше (на несколько десятков), чем у уважаемого ivagor'a.
К сожалению, так и не понял, как использовать деление уважаемого blackmirror'a для отрицательных делителей, поэтому использовал код, который возможно хуже, чем у уважаемого ivagor'a, но этот код задействуется только при числе цифр большем 4680, что не входит в таблицу результатов. Однако, буду признателен за подсказки. Стараюсь собирать в проекте только лучшие коды.
pi-8080-6.zip

[ivagor]

Еще немного ускорил и сократил версию для вектора. Уменьшение размера программы позволило увеличить ширину цифр 6 и 9 при сохранении возможности расчета 8192 цифр пи, что резко повысило удобство чтения результатов. 8192 цифры теперь на 4 экрана (после окончания расчета переключать кнопками 1-4) вместо 3. Версия 65 по всем показателям уступает, убрал.
100 цифр - 2.72 секунды
1000 цифр - 233.62 секунды
3000 цифр - 2087.26 секунды
8192 цифры - 16620.02 секунды

[ivagor]

Если согласиться на уменьшение максимального числа цифр, то можно еще немного ускорить.
100 цифр - 2.70 секунды
1000 цифр - 231.90 секунды
3000 цифр - 2071.46 секунды
7172 цифры - 12256.14 секунды
В 67 максимум 3 экрана (кнопки 1-3), не 4.
В версии 66 можно ускорить расчет 8192 цифр, но результаты 100-3000 не изменятся, мне интереснее было подтянуть "базовые" цифры.

[Advertiser]

[CodeMaster]

то можно еще немного ускорить.

Я всё жду, что в результате исследования тёмной энергии удастся преодолеть скорость света :-)

[ivagor]

Вероятно можно еще чуть-чуть ускорить или чуть-чуть увеличить максимальное количество цифр, но не одновременно и всего лишь на единицы процентов. Для преодоления скорости света или хотя бы ускорения в разы надо переходить к более эффективным алгоритмам.

[ivagor]

Сишный Мэчин blackmirrora, откомпилированный для вектора с использованием z88dk, правильно считает 3001 цифру за примерно 3780 секунд, что медленнее ассемблерного супероптимизированного spigota менее чем в 2 раза. Понятно, что ассемблерный Мэчин в разы опередит spigot на большом количестве цифр.

[litwr]

Если согласиться на уменьшение максимального числа цифр, то можно еще немного ускорить.
100 цифр - 2.70 секунды
1000 цифр - 231.90 секунды
3000 цифр - 2071.46 секунды
7172 цифры - 12256.14 секунды
В 67 максимум 3 экрана (кнопки 1-3), не 4.
В версии 66 можно ускорить расчет 8192 цифр, но результаты 100-3000 не изменятся, мне интереснее было подтянуть "базовые" цифры.

Да, опять обогнали мой код на целых 2%, нашел уважаемый ivagor возможность сократить 10-20 тактов. Надеюсь, что не раскруткой циклов.
Похоже, что благодаря усилиям ivagor'a тема может дать ещё много интересного. Как-то думал, что мой код для БК близок к оптимальному, но замечание ivagor'a заставили внимательнее с кодом поработать и получить ускорение в более 15%. Аналогичным образом удалось ускорить и код для z80, но только на чуть более 10%. А для 8085 почти на 32%.
Вместо самого быстрого алгоритма расчёта числа π фактически в этой теме были созданы наискорейшие алгоритмы деления для многих архитектур. Жаль, что алгоритм уважаемого blackmirror'a невозможно использовать на 6502. Для меня было неожиданно, что код для 8080 на Z80 лишь чуть-чуть на π-затворе медленнее, кода на всех инструкциях z80. Разница в смешных 3%. Хотя по размеру код для Z80 заметно меньше.
А скорее неприятным сюрпризом оказалось, что код деления для 8085, медленнее кода для 8080! Не понятно, почему уважаемый ivagor использовал для Вектора 128 код, где использует много EX DE,HL/ RL DE/ EX DE,HL - что намного медленнее ADD HL,DE. Может только для экономии памяти? Или для ускорения расчётов с отрицательным делителем? У меня в коде π-затворa для Tandy 100 удалось найти место только одной инструкции 8085. Там памяти всего менее 32 КБ, поэтому отрицательные делители не нужны.