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

[ivagor]

? Насколько могу судить, реализованные алгоритмы умножения и, особенно, деления (blackmirror) для 8080 самые быстрые. А деление так и для z80 самое быстрое, или есть быстрее? Для универсальности нужно кое-что добавить, но это не принципиально.

- - - Добавлено - - -

Пару слов о широте охвата процессоров. Я лично за максимальный охват, массовые и экзотические, простые и сложные - чем больше тем лучше. Могу только повторить респект litwrу за многопроцессорность.

[SoftFelix]

Парни, так для Спектрума (Z80) есть готовый исполняемый супер-пупер-оптимизированный бинарник с запросом "сколько цифр считать" и подсчётом времени выполнения?

[perestoronin]

некие универсальные вычислительные алгоритмы для 8-битных процов

за максимальный охват

Универсальные не требуются, т.к. скорости от них, как после написания программы на Си и её первичной оптимизации руками после перевода на ассемблер.
Что делать с примерами "чрезмерно" оптимизированными к примеру на КР580ВМ80А, это уже решать тем, кому этот пример достанется.
Самое лучшее что можно рекомендовать, это сопроводить грамотными краткими комментариями свои шедевры.
А универсальные в нашем случае не дадут максимальной скорости.
Все что сейчас требуется, используя найденные самые быстрые реализации умножения и деления для КР580ВМ80А (впрочем и КР1858ВМ* /Z80) в частности), подобрать самые быстрые алгоритмы собственно расчета 100 цифр числа Пи.
Аналогичное после можно будет проделать и для остальных процессоров, к примеру для 6502 и КР1801ВМ*.
После чего можно будет констатировать "действительные" скорости и вычислительные возможности этих доступных сейчас в России и Китае ретропроцессоров.
Эти же подходы и алгоритмы позволят оптимизировать и другие, ранее не самые быстрые программки.
Расчет числа Пи самое простое что можно было предложить, и суть расчета чего понятна и гуру и новичку, и результат достигается достаточно быстро и наглядно А главное какой прогресс - с минуты до нескольких секунд! И главное, уверен, 3 секунды это еще не предел, при выборе другого алгоритма, при удачном выборе, возможно получить более лучший результат.

[ivagor]

с нескольких минут

Все же первый вариант на ассемблере считал быстрее минуты

[perestoronin]

для Спектрума (Z80) есть готовый исполняемый супер-пупер-оптимизированный бинарник

Не припомню. В шапке темы нет ? Сюда бы Alone, он бы выдал нагора суперПи для Z80
Но вроде бы его сейчас волнуют больше земные ценности, а не спектрумовские, чуть позже возможно присоединится и тогда будет желаемое здесь.
Особенно интересен результат на 20МГц на Профи, впрочем и на 14МГц для ZX-Evo тоже будет интересен.

14МГц (мега турбо режим с WAIT)

Все же первый вариант на ассемблере считал быстрее минуты

Верное замечание, поправил.

[litwr]

Дошло, тут тема 8080, а все остальное сбоку. Хотя быстрый вывод на экран проблема частная, неинтересная, присущая и БК, и Спектруму, и Амстраду, ... И поднимать её было немного по моему скромному мнению не совсем прилично. Типа "защитим наши Жигули" от Вольво (Коммодора) и Москвича (Корвета) - 100% политика. А делать можно просто для 1000 и больше знаков и нет проблемы.
Похоже надвигается смена алгоритма. С текущим версия для Амстрада под СР/М может до 8000 знаков считать.
Но пока использовал предложенный уважаемым ivagor супер-алгоритм для деления в версии для Амстрада и получил новые цифры (для 100, 1000, 3000). Для коммодора деления ещё не перенёс, но кое-что улучшил.
Коммодор +4 - 1.72 - 172 - 1545
Амстрад 6128 - 2.48 - 186.5 - 1646.8
В коммодоровской версии использовал разные банки памяти, что позволило считать до почти 8000 цифр, но замедлило на несколько процентов. Не смог психологически использовать для умножения на 10000 32 килобайта в таблицах как делают некоторые. Использовал таблицу на 768 байт - это отнимает у версии Амстрада примерно 30 тактов в каждом цикле.
Удивительно, но Амстрад обогнал Коммодор 128. В некоторых частных случаях (копирование памяти, деление 32/16, ...) z80 показывает отличную эффективность, уступая не более 50% 6502. Хотя с переносом супер-деления 6502 наверное доведет перевес до 70-80%.
БК по-прежнему никто не тестирует. :-( Уважаемый ММ помог не так давно по теме с бейсиком...

100К цифр

Коммодору понадобится всего-то 172*100² с ≈ 20 суток.

[perestoronin]

БК по-прежнему никто не тестирует.

Все БКшники находятся на отдыхе до 10 января

Для коммодора

результаты обновил в шапке

Дошло, тут тема 8080

Тут тема для всех процессоров, которые доступны, а остальные уже как получится, если есть кому проверить, написать, то и на том благодарствуем владельцам иномарок, только вот не понимаю почему молчат те, кто нажил иномарки в России непосильным трудом

[ivagor]

Амстрад 6128 - 2.48 - 186.5 - 1646.8

Какой сильный перекос для 100 и 1000 цифр. То ли умножение на 10000 сказывается, то ли вывод на экран, но ПК-6128Ц и вектор с z80 считают 100 цифр быстрее, а 1000 медленнее.

почти 8000 цифр

Посчитать можно, а как их контролировать? На экран вектора в 512x256 одновременно можно вывести 5376 символов 4x6 (надо еще написать процедуру вывода). Выводить с прокруткой, сохранять на диск?

понадобится всего-то 172*100² с

С учетом увеличения разрядности умножения и деления скорее всего будет дольше

[perestoronin]

Посчитать можно, а как их контролировать?

Много цифр пока рано считать. А контроль можно наладить уже сейчас, например по какой-нибудь быстрой короткой хэш-функции, коих море и которые на выходе выдают для длинного входного массива двоичных данных контрольное относительно короткое число - как результат хэш-функции. Его же заранее обсчитать для 100 цифр результата и сравнивать с результатом аналогичной функции. Кстати в рамках задачи по расчету числа Пи очень полезное упражнение, причем не сложнее чем собственно алгоритмы расчета числа Пи. Эти функции тоже желательно заоптимизировать. Рекомендую начать с устаревшей md5sum и затем продолжить с более надежной sha256sum. Кстати они, как и подпрограммы быстрого деления и умножения длинных чисел (десятки и сотни цифр в числе), будут очень полезны не только как наглядное пособие для изучающих программирование на ретропроцессорах.
Заниматься же оптимизацией вывода результата на экран тоже нужно, но эту задачку, относительно простую, лучше отложить, сделав предположение что вывод уже давно заоптимизирован дальше не куда Тем более мы договорились время вывода из памяти результат расчета на экран исключить из рейтинга алгоритмов расчета.

Отправными точками можно считать следующие реализации на ассемблере алгоритмов упомянутых хэш-функций для оффтопика
http://www.nayuki.io/res/fast-sha2-h...embly/sha256.S
http://www.nayuki.io/page/fast-sha2-...n-x86-assembly

http://www.nayuki.io/res/fast-md5-ha...bly/md5-fast.S
http://www.nayuki.io/page/fast-md5-h...n-x86-assembly

[ivagor]

md5, sha256 - не крутовато ли для данного применения? ИМХО вполне хватит crc-16 или, если очень хочется, crc-32. Хотя мне вариант с контрольной суммой не особо нравится.