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

[balu_dark]

Э... проверено на личном опыте?

Не Прочитано в книжках. Как ненасильственный метод борьбы Ибо согласно нашему уголовному кодексу - "публичные призывы к ...." малость наказуемы
А ivagor к тому моменту не уточнил - что он хочет побороть.

[Advertiser]

[litwr]

Первое, что приходит в голову - деление. Тут и команды вычитания регистровых пар пригодятся (для ускорения восстановления остатка) и дополнительные регистры.

Слышал от знатоков z80, что быстрые программы IX, IY не используют. 16-битная разность почти бесполезна из-за отсутствия беспереносного вычитания, а ставить перенос на z80 морочно - проще складывать дополнительные коды. Система команд z80 определенный лидер конкурса некрасоты. Разве только второй набор регистров... Но их лучше возможно к прерываниям прикрепить.
Вот, например, деление на z80 - http://cpcwiki.eu/index.php/Programm...32bit_division - другого там раньше не было. Оно раз в 5-6 (!) медленнее DIV32 в программе для Радио-РК (pirk)! Кстати последний вариант pirk - это просто шедевр какой-то.
Пора посмотреть на сверхскоростной pi.rar... Но он, как понял, в отличие от pirk, 1000 знаков не считает? И где же он этот сверхскоростной на 7 сек?
Кстати программка на AMSTRAD CPC6128 с DIV32 и с умножением с таблицами на 16 KB сто знаков отсчитывает за 5.3 сек, 1000 соответственно 5.3*10^2 = 8м 50с - явно можно сделать получше, все же процессор примерно в два раза помощнее...
Возник вопрос. Зачем генерируете таблицы? Проще же готовыми их вставить или кто-то с кассеты грузит? ;-)

Для каждой точности есть свой вариант уточненной формулы Мэчина.

Эта формула вроде уже считается устаревшей, даже у Гаусса была лучше. А кроме того, в 90-е пооткрывали много поцифирных формул, сходящися по 10^n и лучше...
И кроме того, если соревнования между архитектурами, то зачем разные алгоритмы? Ясно, что система с худшим железом легко обгонит лучшую с негодным алгоритмом. Например, Радио-РК легко обгонит лучший суперкомпьютер, который будет считать число Фибоначчи по определению. А если объявить соревнования алгоритмов, то зачем тут ретроплатформы? Есть уже, например, http://benchmarksgame.alioth.debian.org/

[ivagor]

Насчет выкладывания семисекундного+ варианта - я тут обещал больше не заниматься (по крайней мере в этой теме ) паразитической оптимизацией программ b2mа, так что выкладывать очередную версию было бы непоследовательно и нехорошо. Правильнее было бы даже и не писать про нее, но эмоции переполняли. При желании быструю версию можно собрать самостоятельно, нужно только заменить умножение и деление. Умножение можно взять из pirk20 (там еще можно таблицу расположить с 0000h и избавиться от лишнего inr). Деление проще взять из предыдущего pirk, в 20 уже немного иначе сделано. Если вдруг сам реализую какой-нибудь другой вариант расчета, то выложу, но это очень маловероятно.

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

Кстати, насчет реализации умножения и деления на z80 - не новая, но очень хорошая статья. Думаю про нее большинство знает, но может кто не читал. И, конечно, то, что там написано, вполне можно адаптировать для других процессоров.

[b2m]

И где же он этот сверхскоростной на 7 сек?

Вот вариант без таблиц, но он 8.89 сек. pi.rar

[ivagor]

Умножение 16*16=32 на 8080 заметно выгоднее реализовать через два умножения 16*8=24 и сложение. Это я про без таблиц, с ними, понятное дело, еще быстрее.

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

Это я про без таблиц, с ними, понятное дело, еще быстрее

Тут я был не совсем прав. Время четырех умножений 8*8 с использованием таблицы квадратов вполне сравнимо с одним умножением 16*16, реализованным через два умножения 16*8 (с развернутыми циклами). Т.е. маленькая таблица в данном случае не особо поможет.

[b2m]

Умножение 16*16=32 на 8080 заметно выгоднее реализовать через два умножения 16*8=24 и сложение.

Да, если при этом учесть, что когда старший байт равен нулю, то можно и одним умножением обойтись. DAD H/RAL немного быстрее, чем сдвиг пар DE/HL, тут можно выиграть пару тактов, лишь бы сложение их потом не съело.

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

По совету ivagor-а переделал умножение. Теперь этот модифицированный spigot, выдающий по 4 цифры за цикл, работает 8.14269 сек.

[ivagor]

Мне именно pi32 представляется самым перспективным вариантом и по количеству рассчитываемых цифр и по возможности ускорения.
Мелкий момент - связки JNC $+4 \ INR A лучше заменить на ACI 0 (это не я придумал, прочитал в журнале МПСиС, номер не помню).

[b2m]

Да, чёт я тупанул, подумал об этом уже когда выключил комп (отлучиться надо было). Думал ты не успеешь заметить
Вот правильный вариант: pi32.rar

З.Ы. в связи с новой реализацией умножения выкинул пару MOV там, где она используется, теперь 8.117 сек.

[ivagor]

Умножение в pi32 вряд ли уже удастся заметно улучшить, теперь бы деление оптимизировать.

[litwr]

Кстати, насчет реализации умножения и деления на z80 - не новая, но очень хорошая статья. Думаю про нее большинство знает, но может кто не читал. И, конечно, то, что там написано, вполне можно адаптировать для других процессоров.

Посредственная статья. Там нет алгоритма умножения с 512-байтной таблицей, а деления хорошего вообще нет. Советую - http://cpcwiki.eu/index.php/Source_Codes#Algorithms
В z80 для арифметики реально полезна только ADC HL - всё остальное почти полная ненужность. В DIV32 заменил ADD, JP C, INC на ADC - стало peaльнo быстрее. Кстати, DIV32 ошибочна для деления чисел с 32-м разрядом.

Тут я был не совсем прав. Время четырех умножений 8*8 с использованием таблицы квадратов вполне сравнимо с одним умножением 16*16, реализованным через два умножения 16*8 (с развернутыми циклами). Т.е. маленькая таблица в данном случае не особо поможет.

Сначала не поверил, но проверил и оказалось, что вы правы. Выигрыш могут дать только таблицы 16К на 30-40% или 8К на 10-15%. На 6502 ситуация другая, там 16 разрядных операций нет, а работа с памятью быстрая.

Сделал, как кажется, последние варианты для z80 и 6502. 10000 на spigot-алгоритме не сделать, нужно 70 К для массива. Результаты:
6502 2.2Mhz 100 - 3.74c, 1000 - 5м 40.02с
z80 4MHz 100 - 4.51c, 1000 - 6м 41.92с (реальная частота 3.2, поэтому на 1.78 MHz было бы примерно 8.1 сек на 100 цифр)
Получилось, что на тяжелой арифметике 6502 на 75% и более быстрее.
Почти уверен, что z80 на одинаковой с 8080 частоте для арифметики быстрее лишь процентов на 5-10.
Нужны ли программки? Неужели кто-то их запускает? Тема интересная, плохо что не получилась популярной.