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

[litwr]

Поработал немного с кодом для z80, скорость повысилась почти на 10%. Удалось использовать уникальную z80-инструкцию RLD и даже улучшить (точнее специализировать) почти идеальный код DIV32.
Последние данные по Amstrad 6128: 100 - 4.2 c, 1000 - 367.7 c (6m 7.7c), 3000 - 3274.8 (54m 24.8c).
http://litwr2.atspace.eu/cpc.html
DSUB, ARHL, ... за 10 и менее тактов делают 8085 определенно быстрее z80. Был бы хотя бы один массовый компьютер на основе 8085, тогда бы коды для него смотрелись гораздо интереснее.
Джорж Вашингтон стрессы снимал, перебирая крупу, - оптимизировать все же увлекательнее.

Формула Бэйли-Боруэйна-Плаффа (BBP-формула, Формула ББП)

http://mathworld.wolfram.com/PiFormulas.html
Лучше сразу брать по степеням 65536, только у этих формул общая проблема - перевод в 10-й вид. Может с BCD быстрее будет?
http://www.cadaeic.net/naraven.htm - Велимиру Хлебникову такое бы показали...

Уважаемый ivagor, снимаю перед вами шляпу. Попробовал запустить ваш код superbest на Amstrad-e - почти шокирован скоростью: 100 цифр за 2.99 с, 1000 - 274.3 (4m 34.3s) - у вас не коды, а какой-то мастер-класс. Попробую на праздниках поразбираться, благодарю за предоставленную возможность. А еще про запас остаётся treediv! Извините, если раньше, что не так написал...

[ivagor]

litwr, спасибо за высокую оценку
Это не предел, пока еще есть надежда выйти на векторе из 3 сек для 100 и из 5 мин для 1000

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


100 - 2.9768 сек
1000 - 298.9832 - 4 мин 58.9832 сек

UPD: Заменил на версию с более точным подсчетом времени (само вычисление пи не менял) - теперь учитывается, что кадровая частота вектора не 50 Гц, а 50.08 Гц.

[CodeMaster]

100 цифр - 2.98 сек
1000 цифр - 299.46 сек

Линейная функция - 0,03 сек на 1 цифру. Прошлые алгоритмы не были такими линейными.

[ivagor]

Увеличил точность подсчета времени

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

0,03 сек на 1 цифру

Это для 100 цифр, для 1000 в среднем 0,3 сек/цифру

[CodeMaster]

Это для 100 цифр, для 1000 в среднем 0,3 сек/цифру

А, блин точно ;-)

[litwr]

Заменил на версию с более точным подсчетом времени

Ваши коды мне напоминают записи прохождений мастеров по думу - уровень чемпионов. Ещё бы выкладывали версии и для других компьютеров Радио-86РК, Корвета, ... А если сделать коды для Спектрума (а может и для MSX с Амстрадами и т.п.), то можно было бы пошокировать и мировую общественность.
У меня пока Амстрад тормозит у отметки 3.97 c за 100 и это при том, что z80 слегка (10%?) побыстрее 8080. Ваш код пока не запускал, но должно быть около 2.56 с за 100 - Амстрад обгонит Коммодор +4 - тот пока гонит только 2.73 - партия поклонников z80 ликует!
Возник вопрос. В википедии написано, что эффективная частота Вектора около 2.33 МГц, но разница по скорости на superbest для 100 цифр на Амстраде только 16%, что делает эффективную частоту близкой к 2.74 МГц. Откуда такая разница? Видео отключаете? Также удивляет разница по данным на 1000 цифр - тут при сравнение с Амстрадом (Амстрад уже на 27% быстрее) эффективная частота Вектора падает до 2.50 МГц. Как такое может быть?!
Для Амстрада идёт разработка операционной системы FutureOS - она совместима с фирменной, а отличается только скоростью, т.е. энтузиасты пишут совместимые со старыми вызовы, но максимально всё разгоняют. Вам бы в такой проект, уверен процентов 20-30 везде бы дожали.

[Advertiser]

[ivagor]

litwr, опять же спасибо на добром слове, прямо чувствую как развивается мания величия.
Насчет версий для других компов - я и так нарушил свое обещание не оптимизировать программы b2mа (по крайней мере в этой теме). Для вектора b2m выдал мне индульгенцию, а я еще распространил её действие и на клоны вектора. Может он и не стал бы делать pi32, если бы знал, как я буду её извращать.
Отмечу, что финальную векторовскую версию уже не на любой комп с 8080 можно перенести дословно. В рк, микрошу, да и в специалист не влезет, придется резать таблицы. С другой стороны, таблицы дали максимум процентов 10, т.ч. и без них будет неплохо.

В википедии написано, что эффективная частота Вектора около 2.33 МГц

Однако дотянулся vladtru до wiki. Мое личное мнение такое, что оценки "эффективной частоты" нельзя использовать для предсказания быстродействия программ с кодом произвольного состава, т.к. она очень зависит от конкретных используемых команд. Но её можно использовать для оценки эффективности оптимизации под конкретный комп с тормозами - первые версии pi32 для вектора показывали что-то в районе "2.25 МГц". Для финальной версии "эффективная частота" 2.4356 МГц (т.к. условный вектор без тормозов посчитал бы 100 цифр с ее помощью за 2.4168 сек). Видео в векторе отключить нельзя, можно только аккуратно выбирать команды, стараясь уменьшить применение самых торозных (mov, inr/dcr, inx/dcx - amstradу cpc и ПК-6128Ц с их процами полегче, у них то mov и inr/dcr по 4 такта).
То, что в финальной версии времена подсчета 100 и 1000 цифр отличаются почти точно в 10 раз (как и должно быть в теории) считаю признаком хорошей оптимизации.

[perestoronin]

Дальнейшая оптимизация скорости расчета числа Пи для 100 знаков возможна только подбором алгоритма расчета под конкретные процессоры.
И действительно, сначала путем перевода "с Бейсика на ассемблер" получили ускорение в 10 раз. Затем шаманскими манипуляциями получили еще 10 кратное ускорение. Итого от перехода с Бейсика (Java, Си++) на ассемблер со сравнительно небольшими издержками в затратах в часах, можно получить ускорение во всех расчетных модулях как минимум в 100 раз!
А теперь представьте что Ваш любимый гаджет может перестать быть тормозным, а точнее мог бы и не быть никогда тормозным вовсе.

Как я ранее отмечал для 8080 достигнут абсолютный максимум по скорости для выбранного алгоритма. Хотим новых рекордов? Нужно искать новый алгоритм, более подходящий под 8080, чем ранее выбранный.

[litwr]

почти точно в 10 раз

Т.е. в 100 раз?
И вы уверены, что эмулятор даёт правильную частоту кадров? Все известные мне эмуляторы БК вместо положенных 48.5 Гц упрямо дают 50.

стараясь уменьшить применение самых торозных

Вы ещё и на этом оптимизируете?! Вам надо сайт какой-то сделать, сохранить коды для Истории. Был до ваших разъяснений уверен, что 8080 и z80 по тактам одинаковы, оказалось нет... INC на z80 быстрее, а ADD HL наоборот медленнее...

[litwr]

почти точно в 10 раз

Т.е. в 100 раз?
И вы уверены, что эмулятор даёт правильную частоту кадров? Все известные мне эмуляторы БК вместо положенных 48.5 Гц упрямо дают 50.

стараясь уменьшить применение самых торозных

Вы ещё и на этом оптимизируете?! Вам надо сайт какой-то сделать, сохранить коды для Истории. Был до ваших разъяснений уверен, что 8080 и z80 по тактам одинаковы, оказалось нет... INC на z80 быстрее, а ADD HL наоборот медленнее...

ассемблер со сравнительно небольшими издержками в затратах в часах, можно получить ускорение во всех расчетных модулях как минимум в 100 раз!

Скорее раз в 10 для 8-биток. Давал ссылку на компилятор си для Амстрада - тот при включении оптимизации даёт код, примерно раз в 8 медленнее лучшего из пока сделанных. И затрат в часах для такого небольшого кода нужно очень немало: уверен, что уважаемый ivagor при случае это подтвердит.