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

[litwr]

С сожалением вспоминаю, что возможно моя поспешно выбранная позиция, послужила демотиватором для уважаемого ivagor'a. Интересно было бы посмотреть на 8085 коды. Это же какая-то почти уникальнось. Сам сделал на днях код для короля 8-х процессоров 6309. С двумя 16-битными и быстрыми аккумуляторами, с аппаратным делением 32-разрядных чисел и полной совместимостью с 6809 такой чип наверное позволительно так называть. Народ до сих пор свои Коко и Драконы обновляет. Хотя все несуразности 6809 также унаследованы, но с 16 битным АЛУ они почти незаметны. На "затворе-шпиготе" 6309 показал себя в 3.62 раза быстрее, чем 6809. В 6502 бы четыре аккумулятора и аппаратные умножение с делением...

[Advertiser]

[LeoN65816]

В 6502 бы четыре аккумулятора и аппаратные умножение с делением...

Дык, у SuperCPU(65816) тоже потенциал приличный. Однако, кроме частоты этим не воспользовались...

[litwr]

65816 - в каком-то смысле позор. Такое можно было сделать и к 77-78. В 75-м 6502 рвал 8080, а 65816 рядом с 8086 выглядит бледно. Ни новых регистров, ни даже аппаратного умножения, новых команд практически нет. В режиме 16 бит всего-то процентов на 50% быстрее изначального 6502... Команды не разогнаны как на 4510. С 6309 сравнивать не совсем корректно. 65816 - 16-разрядный процессор с 8-битной шиной данных, а 6309 8-разрядный с 16-разрядным АЛУ. Можно сравнить с 65802, которым можно было заменять на плате 6502 (так и делали с Эплами). 6309 гораздо мощнее. На 1.7 МГц, на арифметике легко обгоняет 8086 на 5 МГц. 65816/02 на арифметике примерно как 8086. 65816 может с 16 МБ памяти работать, но неуклюже. R800 (который в раза 4 быстрее z80) также 6309 проигрывает на арифметике раза в два. Не давали японцам развернуться, хотя и не засудили как NEC или MOS Technology.

[blackmirror]

Из формул Мачина наиболее замечательная для i8080 будет:

32*atan(1/10)-4*atan(1/239)-16*atan(1/515)

если считать в 100-ой системе, по такому алгоритму:

a=32/10
b=4/239
c=16/515
for n=1 to len
  pi=(a-b-c)/(2n-1) ;здесь было n, что есть злобный баг
  a/=100
  b/=239 b/=239
  c/=103 c/=103 c/=25
end for

Деление на 25,103 и 239 делается по таблицам менее чем за 70 тактов на байт, а на 100 вообще делить не потребуется. Единственная сложная операция это деление на n, там получается примерно 400 тактов на байт, если делитель более 127. Но деление на n можно совместить для всех трёх слагаемых, при этом память будет требоваться для pi и трёх слагаемых. Результаты в EmuZWin для 3.5 МГц получились такие:

100 цифр - 0,2 ms (=1/5 s)
300 цифр - 2 s
1000 цифр - 25 s
4000 цифр - 418 s

В архиве текст программы и картинки, большие цифры это время в кадрах. Что касается вычислений, то там только команды i8080 используются, если нигде не зевнул. Комментариев пока нету, но если кто будет допиливать для реального i8080 могу добавить.
pi_fast.zip

[litwr]

Peзультаты - супер! Но возможно вы выложили не ту версию программы. Та, что есть, под СР/М считает неправильно 314227... - не пи. По адресу $8fcd высчитывается $1f2a1b42... И почему без бинарника? Использован ассемблер с некоторыми неожиданными особенностями типа CP A,5 и ADC 0 - первую инструкцию по стандарту Zilog пишут CP 5, а вторую ADC A,0.
Интересно уважаемый ivagor в курсе? С хорошей оптимизацией Вектор может перехватить лидерство. А с версией для 8085 может стать и недосигаемым.
Кстати, так до сих пор и не разобрался, как работают задержки на Спектруме. Вроде их нет при обращении к памяти выше $8000. У вас программа и все данные именно там. Но интересно, что происходит, если процессор обращается к памяти ниже $8000 из программы, которая выше $8000? Заранее благодарен за ответ или ссылку.

[SoftFelix]

В архиве текст программы и картинки, большие цифры это время в кадрах.

Прикольно. Неужели из топика всё же родился хоть какой-то бенч для Спекка? Хотя нет - только .asm внутри. Запилите нормальный бенч для Спекка на самом быстром алгоритме Z80! Можно будет пиписками померяться.

[litwr]

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

[blackmirror]

Peзультаты - супер! Но возможно вы выложили не ту версию программы. Та, что есть, под СР/М считает неправильно 314227... - не пи. По адресу $8fcd высчитывается $1f2a1b42... И почему без бинарника? Использован ассемблер с некоторыми неожиданными особенностями типа CP A,5 и ADC 0 - первую инструкцию по стандарту Zilog пишут CP 5, а вторую ADC A,0.

Скачал код из архива, запустил в EmuZWin, вроде вычисляется Пи, в памяти тоже Пи лежит. Всё это безобразие было написано в эмуляторе (причём Z80) без всякой CP/M, выгрузить кусок памяти в двоичный файл там можно, а в другие форматы нет. На всякий случай положил картинку в архив и 4 дампа для 100, 300, 1000 и 4000 цифр, но как их преобразовать во что-то загружаемое я не знаю.
pi_dump.zip
Самое забавное, что для большого количества цифр данный алгоритм можно еще ускорить, если и оставшееся деление(на нечётные числа которые присутствуют в разложении арктангенса) делать по таблицам, в теории можно получить ускорение в 1,5-2 раза.

[litwr]

У вас в исходнике на ассемблере после DIV_15: стоит LD HL,$4300, а в дампе вместо $43 - $56. Кроме того,расхождение в константах после INIT103: и INIT239: .
EDIT. Подставил константы из дампов и заработало! На Амстраде 1000 знаков за 30.8 секунд с печатью через медленный БДОС. Затвор тут в 6 раз тормознее. Но можно быть добрее и прописать константы в исходник, например, PI_LEN = PI_DIGITS/2+1+X... Еще бы убрать лишние цифры, которые, как правило, неверные.
Но в целом получилась очень хорошая программа. Так и до формул Чудновских можно дойти.

[blackmirror]

litwr, после DIV15 там просто индикатор прогресса, в какой-то момент я решил что лучше его разместить между строками, чем затирать цифры. А вот с INIT могут быть и проблемы, или это просто массивы куда-то переехали.
Лишней цифрой обычно оказывалась только последняя, которая живёт в одном байте с правильной предпоследней, поэтому мне было лень из разделять.
От Чудновских никаких плюшек ждать не стоит, у них тоже квадратичная сложность, и хоть за один проход они дают по 14 цифр, но там факториалы и на каждом шаге они дают десяток множителей/делителей которые не засунешь в таблицы. Два деления на 239, два на 103 еще одно на 25 и вычитания в сумме занимают меньше тактов чем одно честное деление для n>256, поэтому прорыв теперь может быть только с удвоением числа правильных цифр на каждом шаге, но не факт что это случится для менее чем 10000 цифр.

По просьбам трудящихся версия программы на Си, максимально упрощённая, но с некоторыми намёками в какую сторону оптимизировать:
pi.zip