Просмотр полной версии : Вычисление числа Пи на ассемблере
perestoronin
01.11.2015, 12:48
Эта тема создана как ответвление темы "Отечественные компьютеры: быстродействие" (http://zx-pk.ru/showthread.php?t=25778)
Очень настаиваю очень важные философские вопросы поднимать не здесь, а в отдельной теме во флейме "Пожужжим о "расчете числа Пи" (http://zx-pk.ru/showthread.php?t=25945)
"Вычисление числа Пи с заданной точностью на ассемблере как тест для процессоров", надеюсь полная постановка задачи всем известна.
Для сверки результата можно использовать 10 миллионов цифры по ссылке под спойлером - осторожно 10 миллионов символов это ТРАФИК!:
Взял Пи вот тут (http://pi.karmona.com/)
Желающие запостить свои творения в эту тему - прошу не стесняться своего кода, надеюсь никто смеяться не будет и гуру помогут выправить код.
Для Z80 расчет числа Пи, приславший пожелал остаться неизвестным, автор программы в архиве указан.
Прошу протестировать на реалах и эмуляторах. Особенно интересен результат на процессорах КР1858ВМ*
54895
Результаты:
1801ВМ2 @ 10MHz EIS On (HMUL=1, HDIV=1):
100 знаков 0,50 сек (было 0,58)
PDP-11/83(18 МГц).
100 знаков - 0.2
Реальный 1801ВМ1Г 5МГц (+MUL)
100 знаков - ~2,1 сек
ДВК-3:
100 знаков- 0,7сек
Вектор:
100 - 2.7568 сек
Коммодор +4 (MOS 8501 @ 1.76 МГц) - 1.72
Amstrad CPC6128 (Z80, @ 4 Мгц) - 2.48
Commodore 64/PAL (MOS 6510 @ 1,023 МГц) - 4.03
Commodore 128/PAL (MOS 8502 @ 2 МГц & Z80 @ 4 МГц) - 2.2
http://litwr2.atspace.eu/retropc.html
РК86:
Самый первый результат конечно же был прислан для
Радио-86РК, 100 знаков, 53 секунды, впоследствии улучшен
вариант без таблиц, 8.89 сек. pi.rar (http://zx-pk.ru/attachment.php?attachmentid=54896&d=1447524812)
с новой реализацией умножения теперь 8.117 сек 54904
Очередная и, надеюсь, последняя версия spigota - 54829
100 знаков - 19897238 тактов - 11.19 сек (это с расчетом таблицы!)
535 знаков - 551337754 тактов - 5 мин 10 сек
Запускать нужно G4200
Получается, что на "тяжёлой" арифметике 6502 только раза в полтора побыстрее на одинаковой частоте.
Адаптируйте и проверьте пожалуйста счастливые обладатели Агатов 7 и 9 и собранного Apple I (http://mdesk.ru/a1/). Кстати реплика не планируется 9ки ?
18.11.2015: впервые портирована простая реализация расчета числа Пи на БК (процессор К1801ВМ1 (https://ru.wikipedia.org/wiki/К1801ВМ1), Система команд по ОСТ 11 305.909-82 (может у кого есть скан этого документа?, поделитесь им в этой теме) (http://vak.ru/doku.php/proj/bk/1801vm-series) ):
Сделал программку для БК (http://forum.pk-fpga.ru/viewtopic.php?f=15&t=5427). Запускал в эмуляторе BK-TERAK.
На этом эмуляторе 100 цифр за 6 сек, 1000 - за 9м 21с.
Прикрепляю и файлы для "иностранцев" с исходниками и файлами для эмуляторов или для переноса на железо.
54932
54931
54930
Но для других архитектур хотя и не было представлено результатов, но были присланы программы и их исходники для тестирования на реалах и эмуляторах.
Для Z80 расчет числа Пи, приславший пожелал остаться неизвестным, автор программы в архиве указан.
Прошу протестировать на реалах и эмуляторах. Особенно интересен результат на процессорах КР1858ВМ*
Как вариант можно рассмотреть быстрый алгоритм:
https://en.wikipedia.org/wiki/Machin-like_formula
https://upload.wikimedia.org/math/f/1/5/f15dc3d39c473c4bd718e3a98145da0d.png (https://en.wikipedia.org/wiki/Machin-like_formula)
И библиотеку z88dk
http://www.z88dk.org/wiki/doku.php?id=libnew:examples:pi
В связи с таким расчетом запустил на стандартном консольном калькуляторе на Raspberry Pi c 900 МГц
time echo 'scale=1000;16*a(1/5)-4*a(1/239)'|bc -l
т.е. 1000 знаков - отсчитано с 1.5 сек.
Сопоставлять результаты будем когда накопится с 10 различных платформ, но уже видно, то ARM у нас 32 разрядный, а не 8 разрядный и частота в 250 раз выше чем у zx. Т.е. в 1000 раз производительнее, и результат полученный на ARM при сравнении с zx нужно делить примерно на 1000.
https://en.wikipedia.org/wiki/Approximations_of_π
На заметку, по этой ссылке собран анализ всех рассмотренных нами алгоритмов, и дан обзор других, более современных и возможно ещё более быстрых на ретро-железках, главное подобрать теперь под каждый из процессоров ту формулу, которая будет для конкретного процессора самой быстрой :)
Походу исследований на эту тему никто еще не делал :)
Для каждой точности есть свой вариант уточненной формулы Мэчина.
Самая простая формула обладает невысокой точностью, но при этом является более быстрой.
Думаю, что упущен момент с расчетом неких констант, выраженный в этой программе на бейсике:
; This BASIC program was used to calculate the equates for PIF.ASM.
; DEFDBL A-Z
; INPUT "Digits required"; A
; MPVSize = 32 * ((A / (LOG(2) / LOG(10)) + 255) \ 256)
; PRINT "NumDigits = "; A + 64
; PRINT "MPVSize = "; MPVSize
; k = A / .69897
; k = INT(15 + (k + k * .1)) 'floor 1
; PRINT "Last1 = "; k
; k = INT(15 + (A / 2.37)) 'floor 2
; PRINT "Last2 = "; k
;
numDigits=164
mpvSize=74
last1=172
last2=57
https://sites.google.com/site/richgel99/index/286-assembler-machin-series-pi-calculator
А бонусом у нас должны получиться быстрые программы умножения и деления для всех ретро-процессоров, которые сгодятся и для других отличных от академических целей.
Левенталь и Гудыменко нам в помощь:
Скачать Левенталь Вар.1 (https://yadi.sk/d/y0VRFLFhmLqrb)
Скачать Левенталь Вар.2 (https://disk.yandex.net/disk/public/?hash=9d5g6WO3oeNa0p12nZIhpStH//Y1BPLVgqEnPcEsJwc%3D)
Скачать Левенталь Вар.3 (https://yadi.sk/d/NZXlY8FqmLr65)
Скачать Гудыменко Вар.1 (https://yadi.sk/d/QXDKJ4c5mLrML)
Левенталь 6502 Подпрограммы на ассемблере (книга на английском). (http://www.s100computers.com/Software%20Folder/6502%20Monitor/6502%20Assembler.zip)
Цифры - просто для истории и справки:
Новый рекорд вычисления числа Пи: 5 трлн знаков (http://geektimes.ru/post/101210/)
Дополнительные материалы и ссылки под спойлером ниже:
Также будут интересны результаты и для КР580ВМ* и КР1858ВМ* (http://transistor.by/forum/index.php?topic=646.0), но думаю они будут неутешительными - у них нет команд целочисленного умножения и деления, но в случае реализации процессора Z80 на ПЛИС это можно обойти добавив пару недостающих команд в набор команд. Такой результат тоже засчитывать будем :) Тем более что такие обсуждения три года назад уже поднимались (http://zx-pk.ru/showthread.php?t=18233), в идеале можно взять за основу возможности сопроцессоров am9511, am9512, National Semiconductor MM57109N (https://ru.wikipedia.org/wiki/Zilog_Z80).
Интересная заметка в вики (https://en.wikipedia.org/wiki/Zilog_Z80) по поводу как можно уменьшить время выполнения умножения и деления на Z80 используя его архитектуру
+ еще полезные ссылки по реализации умножения и деления на Z80
аппратные на ПЛИС (подобные командам Z180 и выше):
http://opencores.org/project,y80e
http://homepage3.nifty.com/z80/
программные:
http://z80-heaven.wikidot.com/math
http://sgate.emt.bme.hu/patai/publications/z80guide/part4.html
http://chilliant.blogspot.ru/2010/12/modulo-arithmetic-in-z80-assembler.html
Общая информация
http://www.z80.info/
полезные ссылки про архитектуру 1801ВМ2 и ему подобных:
http://yavix.ru/вики 1801BMx
http://www.wikiwand.com/ru/Союз-Неон_ПК-11/16
Алгоритм заточенный на многоядерность:
http://www.numberworld.org/y-cruncher/algorithms.html
Интересная статистика упомянутых алгоритмов:
http://members.shaw.ca/francislyster/pi/pi.html
Индексатор ссылок на ресурсы с исходниками некоторых других реализаций вычисления числа Пи
http://www.pi314.net/eng/programmes.php
На процессорах 6502:
На форуме 6502 в топике http://forum.6502.org/viewtopic.php?f=2&t=2239 есть архивчики для процессоров 6500 и 6502:
http://forum.6502.org/download/file.php?id=159&sid=11abefe5280c12cc3562659b6ca3a9f8
http://forum.6502.org/download/file.php?id=160&sid=11abefe5280c12cc3562659b6ca3a9f8
Интересно, как долго будет считаться число Пи на Денди :)
реализации умножения и деления на z80 - не новая, но очень хорошая статья (http://ivr.webzone.ru/articles/dop_ar/). Думаю про нее большинство знает, но может кто не читал. И, конечно, то, что там написано, вполне можно адаптировать для других процессоров.
деление на z80 (http://cpcwiki.eu/index.php/Programming:Integer_Division#32bit_division)
Кое-что из книги на BASIC.
http://s017.radikal.ru/i434/1511/2e/a22ef93bc011.jpg (http://radikal.ru/big/98a90e67764c4c838fee91f4c71a2c96)
>прошу архитектуру х86 не рассматривать вовсе
Извиняюсь, но на писишке оно выключилось на шаге 65536. Мож на БКшке или УКНЦ дойдёт до 32768 (там, где 16-битные процессоры стоят)?
balu_dark
01.11.2015, 23:15
Блин в советском учебнике истории- было упомянуть что число ПИ получалось делением двух чисел(дробь). Но уже лет 16 ищу - и не могу найти каких именно.
Упоминалось если не изменяет склероз - в контексте древней Греции вроде.
Тема была что то про астрономию и про первые обсерватории в виде глубоких колодцев.
На тот момент я проверял на калькуляторе эту дробь - выходила точность до последнего знака в калькуляторе.
Найти бы ее - и все логарифмы,квадратные корни и экспоненты - стали бы не нужны! Там простое деление было.
Вот есть много чего про Пи
http://bizikov.ru/posts/history-of-pi/
---------- Post added at 23:15 ---------- Previous post was at 23:06 ----------
Среди примечательных результатов предыстории числа
π отметим довольно грубое приближение
π= (31/8), которым пользовался
известный римский архитектор Витрувий (живший в I в. до н. э.)
(ему приходилось проектировать сооружения внушительных размеров, например, знаменитый Римский театр, и надо полагать, что
используемое им грубое значение для
π приводило к недочётам в
строительстве), и выдающийся результат китайского математика
и астронома Цзу Чунчжи (V в. н. э.)
π = 355/113, дающий семь точных десятичных знаков числа
π.
π= (31/8), которым пользовался
известный римский архитектор Витрувий
Что-то сильно уж грубо. Знаменитое 22/7 гораздо точнее отражает суть Пи.
Извиняюсь, но на писишке оно выключилось на шаге 65536. Мож на БКшке или УКНЦ дойдёт до 32768 (там, где 16-битные процессоры стоят)? Проверил на эмуляторе ДВК. Как видно, доходит до 65536 но после 16384 значение не меняется.
http://s008.radikal.ru/i305/1511/81/a7ea88d99114.jpg (http://radikal.ru/big/2bf4fc2396eb40538c36f0eb73db051f)
Около темы статейка
http://geektimes.ru/post/101210/
Kakos_nonos
02.11.2015, 16:45
Вот алгоритм вычисления числа пи (1000+ цифр) использующий только целочисленную арифметику. Вполне можно реализовать на ретрокомпьютерах.
http://habrahabr.ru/post/188700/
Kakos_nonos
02.11.2015, 17:29
Вот ещё Гоблин подсказал: http://scepticalinq.blogspot.ru/2015/04/314159265358979323846264338327950288419.html
---------- Post added at 17:29 ---------- Previous post was at 17:25 ----------
но в нем тоже требуются операции умножения и деления, которые придется программно реализовывать.
Это не так трудно как вычисления с плавающей точкой, в книге Левинталя есть описания, но там, кажется 16-битные, это даст меньший размер числа. Но можно реализовать и 32-х. Умножение реализуется просто, а с делением и остатком надо подумать.
Точность 5 знаков очень маленькая, для старта рассматриваем 10 знаков. Прога на Паскале.
http://s018.radikal.ru/i512/1511/a3/508729fda793.jpg (http://radikal.ru/big/633c3dbc64c14457a3244d5f252f6b0e)
Эээ, подождите...
По этой распечатке просчитаны были только 5 знаков после запятой, да и то на эмуле.
В железе еще вообще никто не считал.
Есть ли смысл так гнать ?
В железе протестировал первую программу на писюке на квикбейсике, о чём отписался выше. Однако эта прога почему-то при просчёте свыше 65565 начала уменьшать (!) значение после запятой! Посему это не более, чем тест. Пробую запрограммить формулы Плуффе и Беллара на своей восьмибитке, но оно времени требует...
(ага, хлестанулся громкими фразами ;))
Первые результаты :)
Радио-86РК, 100 знаков, 53 секунды
Проверялось в эмуляторе, на реале возможно будет немножко другое время.
http://zx-pk.ru/attachment.php?attachmentid=53975&stc=1&d=1446502436
После оптимизации умножения 25.59 секунды.
Вероятнее всего скорее это непредельный результат
Шутишь? Разве что ivagor найдёт изъяны и оптимизирует на пару тактов :)
А вообще, было бы интересно, если кто-либо предложил бы свой, более быстрый, вариант.
Viktor2312
03.11.2015, 01:52
найдёт изъяны и оптимизирует на пару тактов
Думаю, что и на 100 можно оптимизоровать, тактов.
Кстати, по поводу пределов: максимально возможное число знаков для этого алгоритма, использующего только 16-битную арифметику = 534. Сколько будет считать - незнаю, но сложность этого алгоритма O(N²), так что будет раз в 28-29 дольше.
[OFFTOPIC ON]
Надеюсь злостных оверов тут нет, поэтому может кому то интересно узнать,
про ихний сайт www.hwbot.org и одну из дисциплин меряния эмм..., ну вобщем кто быстрее посчитает SUPERPI - 1M и SUPERPI - 32M.
http://hwbot.org/benchmark/superpi_-_1m/
Лучшие резальты справа.
комуу интересно, можете на своих числодробилках запустить, чтобы иметь представление, насколько совремённые процессоры считают быстрее их предшественников :)
Собственно сам бенч (http://url.hwbot.org/1x9EUxE) под винду.
На ретро-процах, типа первых пеньков - вполне тоже работает.
Upd: PiFast (http://hwbot.org/benchmark/pifast/) из той же оперы...
[/OFFTOPIC OFF]
Оригинал b2m: 90802464 тактов - 51 сек
После оптимизации умножения: 51124904 тактов - 27.76 сек
Может еще пару тактов удастся сбросить
Сообщите пожалуйста что было исправлено
Я догадываюсь, что он сделал. Если проанализировать алгоритм, то основная масса умножений будет на число, меньшее 256. Поэтому количество сдвигов в этих случаях можно уменьшить вдвое (переместив младший байт множителя в старший).
---------- Post added at 16:31 ---------- Previous post was at 16:10 ----------
Заменил pi.rar, теперь 34 секунды. ivagor круче :)
---------- Post added at 16:51 ---------- Previous post was at 16:31 ----------
Заменил умножение на 10 (без вызова п/п умножения). Теперь 26 секунд. Я круче :)
---------- Post added at 17:04 ---------- Previous post was at 16:51 ----------
Если я правильно понял алгоритм, там q тоже всегда меньше 256, так что можно ещё пару тактов сэкономить.
Утром пришлось прерваться на самом интересном месте. Было видно, что еще можно немного дожать. Хотелось в 2 раза обогнать, но не успел, b2m уже оптимизировал.
Тем не менее, предлагаемый вариант выполняется за 43499204 такта - 24.47 сек
Вашу бы энергию на написание крутых демо-эффектов или хотя бы игр)
ё-маё, b2m уже успел и умножение на 10 оптимизнуть
Для Z80 расчет числа Пи
Интересно, что деление выполнено обычным циклом с вычитанием. Видимо для данного алгоритма это быстрее (т.к. результат деления маленький). Можно попробовать и с моим кодом так поиграть...
---------- Post added at 17:29 ---------- Previous post was at 17:21 ----------
ё-маё, b2m уже успел и умножение на 10 оптимизнуть
Развернул таки цикл в последовательность :)
Кстати, один из множителей всегда меньше 256, иначе было бы переполнение.
---------- Post added at 17:32 ---------- Previous post was at 17:29 ----------
Я думаю, если кардинальных оптимизаций больше не будет, на этом и остановимся.
Кстати, один из множителей всегда меньше 256, иначе было бы переполнение.
С учетом этого еще минус почти секунда.
если кардинальных оптимизаций больше не будет
Деление желательно бы попробовать ускорить
деление выполнено обычным циклом с вычитанием. Видимо для данного алгоритма это быстрее
Да, быстрее: 35742085 тактов - 20.1 сек
Остановился на 34405448 тактов - 19.35 сек
Сначала надо размяться. иначе будет на выходе лишь мишура без изящества кода и алгоритмов. Да и кто сказал что ретро-вычислители предназначены для одних лишь игр и демок ?
Вот увидишь - разомнутся и разойдутся)
perestoronin
04.11.2015, 00:01
разомнутся и разойдутся)
Конечно же после разминки разойдутся и поймут что ассемблер - это не тайна за семью печатями, и явят ещё одну Колибри, но уже для РК-86.
Кстати вот новый (точнее незамеченный старый путь) для совершенствования расчета числа Пи, сдавала студентка и я её даже хорошо знаю, в 2009 году, причем успешно:
; Зачетная задача: пользуясь рядом Тейлора для arctg, подсчитать число пи
; с 100 знаками после запятой.
;
; Расчет числа Пи сделаем по формуле Мачина
;
; 1 1
; pi = 16 arc tg --- -4 arc tg---
; 5 239
;
; arc tg будем вычислять по формуле Тейлора:
;
; 3 5 7 9
; x x x x
; arc tg x = x - --- + --- - --- + --- - ...
; 3 5 7 9
.186
stack segment stack
dw 512 dup (?)
stack ends
data segment
; -------------------------------------------------------------------------------
; Следующие числа указывают сколько цифр числа Пи нужно вычислять
; Я использовала программу MAKESZES.BAS чтобы вычислить эти значения
; в выводимом на экране результате только первые А (в нашем случе 100цифр) являются верными
; This BASIC program was used to calculate the equates for PIF.ASM.
; DEFDBL A-Z
; INPUT "Digits required"; A
; MPVSize = 32 * ((A / (LOG(2) / LOG(10)) + 255) \ 256)
; PRINT "NumDigits = "; A + 64
; PRINT "MPVSize = "; MPVSize
; k = A / .69897
; k = INT(15 + (k + k * .1)) 'floor 1
; PRINT "Last1 = "; k
; k = INT(15 + (A / 2.37)) 'floor 2
; PRINT "Last2 = "; k
;
numDigits=164
mpvSize=74
last1=172
last2=57
Думаю из этого куцего описания будет понятно куда можно попробовать дальше двинутся ? Или для ретро-процессоров это не по силам ?
Авторство программки конечно же не студентки, а уважаемого гуру:
; ASMPI by Rich Geldreich, December 1992 - June 1993
; (A FAST all-assembly PI calculator.)
; Thanks to Victor Yui for suggesting the division optimization.
; (This program has only been verified to 10,000 digits.)
https://sites.google.com/site/richgel99/
https://sites.google.com/site/richgel99/index/286-assembler-machin-series-pi-calculator
Все что сделала студентка, так это покоцала оригинал (под процессор 286) до требований курса использовать процессор 86.
Теперь же надо тоже самое сделать, но уже покоцав оригинал до уровня команд любимых ретро-процессоров, причем глубокие оптимизации даже приветствуются.
Замечу, что схожие алгоритмы лежат в основе всех TOP-вычислителей числа Пи, но нам более чем будет достаточно для счастья и этого достаточно быстрого алгоритма, мне бы хотелось увидеть результат дальнейшего роста производительности нашей РК-86 в разы!
Остановился на 34405448 тактов - 19.35 сек
А поделитесь, пожалуйста, непокоцанным исходником реализации на Си.
Попробовал дожать spigot b2mа: 26539359 такта - 14.93 сек
54778
Появилось желание повыпендриваться и сделал еще версию оптимизированную для 580ВМ1 и 8085 - в ней используются только общие для этих процов команды. Индивидуально для них можно оптимизировать лучше.
Оптимизированная версия:
на 580ВМ1: 24938659 тактов - 14.03 сек
на 8085: 24082312 такта - 13.55 сек
100 знаков считаются слишком быстро, вот результаты расчета 535 знаков:
1) Версия для 8080
8080 и 580ВМ1 - 755784115 тактов - 7 мин 5 сек;
8085 - 734253062 такта - 6 мин 53 сек;
2) Версия для ВМ1 и 8085
580ВМ1 - 709984370 тактов - 6 мин 39 сек;
8085 - 685592137 тактов - 6 мин 26 сек;
54779
А поделитесь, пожалуйста, непокоцанным исходником реализации на Си
Насколько я понимаю, b2m использовал исходник отсюда (http://scepticalinq.blogspot.ru/2015/04/314159265358979323846264338327950288419.html) (надо промотать вниз).
- - - Добавлено - - -
Забыл сразу написать. Еще резервы есть в использовании самомодифицирующегося кода (попробовал, а потом убрал). Кроме того, данный вариант может работать при разрешенных прерываниях, если не на РК (хитрое использование стека также в резерве).
Кардинального ускорения расчета большого количества знаков наверное лучше добиваться использованием другого алгоритма.
Программа для z80 http://www.z88dk.org/wiki/doku.php?id=libnew:examples:pi 800 знаков считает за несколько минут и написана на си.
Интересно, пригодятся ли при таком расчете команды z80, отсутствующие у 8080?
Пользователи БК жалко отсутствуют. Радио-РК БК определенно должна обогнать, а вот Спектрум скорее всего нет.
В связи с таким расчетом запустил на стандартном консольном калькуляторе на Raspberry Pi :) c 900 МГц
time echo 'scale=1000;16*a(1/5)-4*a(1/239)'|bc -l
т.е. 1000 знаков - отсчитано с 1.5 сек.
Обратите внимание на ПРАВИЛЬНУЮ ФОРМУЛУ - в материалах выше плюс перепутан с минусом.
Рожица после ссылки вставилась сама - движок не должен делать подстановки в ссылках!
Рожица после ссылки вставилась сама - движок не должен делать подстановки в ссылках!
Об этом надо написать в тему о переезде форума, тут это могут не заметить.
perestoronin
08.11.2015, 13:10
Программа для z80 http://www.z88dk.org/wiki/doku.php?id=libnew:examples
Благодарю за найденную ошибку, за ссылку на готовую библиотеку и за результаты для ARM, ARM конечно же бесспорный лидер :)
Опробуйте пожалуйста на z80 при 100 знаках точных цифр. Сколько секунд получилось и при какой частоте ?
Про БК, если программу переписать на ассемблере macro11 и использовать команду целочисленного умножения (есть такая у процессора КР1801ВМ1Г и его можно впаять вместо штатного КР1801ВМ1А), то еще вопрос кто вырвется в лидеры. Также интересен результат и для процессоров ВМ2, у которых более богатые команды целочисленного умножения и деления.
Может кто на эмуляторах БК попробует ?
https://en.wikipedia.org/wiki/Machin-like_formula
Согласно вики, в файле действительно ошибка в комментариях:
https://upload.wikimedia.org/math/f/1/5/f15dc3d39c473c4bd718e3a98145da0d.png (https://en.wikipedia.org/wiki/Machin-like_formula)
Сопоставлять результаты будем когда накопится с 10 различных платформ, но уже видно, то ARM у нас 32 разрядный, а не 8 разрядный и частота в 250 раз выше чем у zx. Т.е. в 1000 раз производительнее, и результ полученный на ARM при сравнении с zx нужно делить примерно на 1000.
движок не должен делать подстановки в ссылках!
Просто при расширенном режиме окна редактирования в низу поставьте галочку
в пункте
Отключить смайлы в тексте
При включении, :) НЕ будет заменён на :)
Почитал, насколько быстро считает сишная прога на z80 и оптимизировал умножение в pirk14. Теперь 535 знаков считает на полминуты быстрее (6 мин 33 сек), кроме того прога стала короче.
- - - Добавлено - - -
Переделал умножение на сложение двух произведений по таблице 5*8 (16 Кб). В итоге 535 знаков стал считать еще на 45 секунд быстрее - 5 мин 47 сек. Из них примерно 1 сек - расчет таблицы. Для 535 знаков это не критично, а для 100 знаков таблицу можно и заранее отдельно посчитать.
Этого Мачина на асме 8080 я бы тоже с интересом посмотрел.
Насчет сравнения скорости spigot для разного числа знаков: 535 в 28.6 раз медленнее 100 (b2m приводил подобную оценку), 800 в 2.2 раза медленнее 535 (если не учитывать необходимости увеличения разрядности части операций). Небольшие отличия вносит вывод на экран. Возможно стоит разделить расчет и вывод на экран.
Метод цифра за цифрой хорош когда есть жесткие требования к размеру доступной памяти
Что-то мне кажется, что метод:
/* A spigot algorithm for the Digits of \pi, Stanley Rabinowitz
and Stan Wagon, Amer.Math.Monthly, March 1995, 195-203 */
На базе которого в этой ветке пишут тесты, не является методом "цифра за цифрой". Там именно идет добавление очередного члена ряда к длинному числу, которое находится в массиве, при этом еще идет одновременное умножение всего числа на 10, чтобы выцепить очередную цифру мантиссы в десятичном виде.
Прочитал, что принятая в русской литературе транскрипция фамилии автора - Мэчин. И что это не самый быстрый способ. Но, имхо, он вполне заслуживает реализации, повторюсь, я бы с интересом посмотрел. Только не надо никого заставлять :)
Сишная программа (http://algolist.manual.ru/maths/count_fast/pi.php) для вычисления с использованием арктангенсов, в т.ч. Мэчина.
- - - Добавлено - - -
примерно 1 сек - расчет таблицы
Это было просто неприлично. Ускорил расчет таблицы в четыре с половиной раза, теперь рк сосчитает её примерно за четверть секунды. И сократил на 28 байт. Т.е. даже для расчета 100 знаков не обязательно заранее отдельно генерировать таблицу.
Что-то мне кажется, что метод:
На базе которого в этой ветке пишут тесты, не является методом "цифра за цифрой". Там именно идет добавление очередного члена ряда к длинному числу, которое находится в массиве, при этом еще идет одновременное умножение всего числа на 10, чтобы выцепить очередную цифру мантиссы в десятичном виде.
Нету там никакого добавления очередного члена ряда. Там просто преобразование числа Pi из одной системы счисления в другую (в данном случае десятичную), по одной цифре (умножая на 10 и выделяя цифру). Просто не все знают, что есть система счисления в которой число Pi равно 2.222222222222...
Нету там никакого добавления очередного члена ряда
А вот это что:
x = 10*a[i-1] + q * i;
Имхо, это добавление переноса от умножения предыдущего разряда на 10 и деления на 2i-1.
думаю что перевод числа из двоичного вида в десятичное можно вынести за рамки оценки производительности алгоритма получения самого числа Пи
Есть формула, по которой считается очередная 16-ичная цифра числа Pi, т.е. фактически очередные 4 бита двоичного представления. И она не требует вычисления предыдущих цифр. Проблема только в том, что чтобы перевести бинарное число в десятичное, нужно много раз умножать на 10 всё число целиком. Т.е. от наличия дополнительных цифр в двоичном числе зависят цифры в десятичном представлении этого числа. А после перевода первых N цифр в десятичный вид уже нельзя добавить новые двоичные данные.
Получается, сначала нужно рассчитать все цифры 16-ичного (двоичного) числа, и только потом заняться переводом его в десятичное. Для 8-мибитного компьютера перевод двоичного числа в десятичный вид не менее трудоёмок (в плане времени вычисления), чем рассчёт каких либо других формул.
- - - Добавлено - - -
А вот это что:
x = 10*a[i-1] + q * i;
Имхо, это добавление переноса от умножения предыдущего разряда на 10 и деления на 2i-1.
a[i] это цифра в другом счислении. Понятно, что умножая это число на 10 нужно учитывать ещё и перенос из другого разряда. Очередной множитель цифры этой системы сисления как раз равен i/(2*i-1), а q, как ты правильно заметил - это перенос. Просто умножение на i в одной строке, а деление - в другой.
Забавно, получается что:
for(j=0;j<LEN;j++) a[j]=2;
просто задает число пи равное 2.222222...., а все остальное ниже - просто перевод в десятичную систему? А в какой системе исчисления пи равно 2.222...?
Тут надо читать про spigot-алгоритм вычисления числа pi:
http://zx-pk.ru/attachment.php?attachmentid=54828&d=1447061792
А, тогда не совсем позиционная система исчисления (что предполагает фиксированное основание), а все-таки обычный ряд. Просто тут его вычисление удачно совместили с переводом в десятичную систему. А в массиве находятся не цифры, а обновляемые члены ряда.
Update: кстати, добавление нового члена ряда прикольно сделано, с отложенным переносом. Если новая полученная цифра не девятка, то переноса в предыдущую цифру не предполагается (неочевидно, как по мне - требует доказательства, но ладно), значит предыдущую цифру можно вывести. А если девятка - то копим число девяток подряд, вдруг произойдет перенос и его распространение.
Очередная и, надеюсь, последняя версия spigota - 54829
100 знаков - 19897238 тактов - 11.19 сек (это с расчетом таблицы!)
535 знаков - 551337754 тактов - 5 мин 10 сек
Обращаю внимание, что запускать нужно G4200
Можно еще чуть-чуть ускорить, если размещать таблицу для умножения с 0000h, но я не стал заниматься крохоборством.
Ну, молодец, молодец, ускорил в 5 раз :)
Теперь напиши это на псевдоассемблере и ещё ассемблер, генерирующий прогу для любого из компов, что есть у меня в эмуляторе :)
[/sarcasm detection off]
А тебя не смущает, что по ссылке (http://www.z88dk.org/wiki/doku.php?id=libnew:examples:pi), которую приводил litwr, программа на си считает 800 знаков за 1,458,354,526 тактов? Если попробовать сравнить, то 535 знаков она посчитала бы примерно за 1,458,354,526/2,2=662888420 тактов. Т.е. сейчас программа на асме 8080 наконец-то стала считать быстрее программы на си для z80. Как то не очень круто, если учесть, что в той проге используются и 32 битные операции. Алгоритм, который используется в сишном варианте по ссылке очень похож на spigot, но, если я правильно понимаю, переводит не по одной цифре, а по 4.
[/sarcasm detection on]
который используется в сишном варианте по ссылке очень похож на spigot, но, если я правильно понимаю, переводит не по одной цифре, а по 4.
[/sarcasm detection on]
А это и есть тот же spigot только переводит в систему с основанием 10000. Ну и массив 32-битный, чтобы не переполнялись члены. Кстати, возможно, там ошибка - если будет 9999 и перенос из следующего разряда. Вероятность небольшая, но пи - число иррациональное и трансцендентное :), в нем все комбинации группы цифр рано или поздно встретятся.
Теперь напиши это на псевдоассемблере и ещё ассемблер, генерирующий прогу для любого из компов, что есть у меня в эмуляторе :)
LLVM с его IR (intermediate representation, по факту это псевдоассемблер), возможно "спасет отца русской демократии" :)
Кстати, возможно, там ошибка
Из интереса посчитал той программкой 1600 знаков - все ОК, т.е. по крайней мере в этом районе все нормально.
На i5 показывает время расчета в районе сотых долей секунды, насколько все же далеко вперед ушло развитие процессоров.
Из интереса посчитал той программкой 1600 знаков - все ОК
Если совсем грубо, то вероятность появления "цифры" означающей 9999 - порядка 1/10000, да еще и перенос должен быть из следующего разряда, то есть вероятность около 1/100К, поэтому ошибка от 100К знаков может вылезти. Это если она там есть (вдруг ряд сходится так быстро что перенос не возникает), пока это только мое подозрение.
http://bio.fizteh.ru/student/spravochnik/pi/pi-arpfelw5bsu.zip
999999, пятая седьмая строка
Если верить архиву с миллиардом знаков числа пи, который скачал на рутракере, та программа правильно считает максимум 16256 знаков (за 1.7 секунды). Для 8биток выше крыши
- - - Добавлено - - -
Если заменить long на int64_t, то правильно считает до 54932 знака включительно (за 25 секунд).
А тебя не смущает, что ... сейчас программа на асме 8080 наконец-то стала считать быстрее программы на си для z80.
Смущает. Там есть одна хитрость, которая позволит ускорить наш spigot ( уже наш :) ) ровно в два раза.
- - - Добавлено - - -
Может просто тупо тот алгоритм на асме переписать? Хотя, основная масса времени это всё равно умножение/деление, не думаю, что в сишном рантайме они какие-то неоптимальные.
- - - Добавлено - - -
Если только использовать не чисто 32-битные умножение/деление, а смешанные 32/16 битные. В том алгоритме явно указано, что нужно умножать uint32 на uint32, ну и делить также. А на самом деле нужно uint16*uint16 -> uint32, а затем uint32/uint16 -> uint16.
Может просто тупо тот алгоритм на асме переписать? Хотя, основная масса времени всё равно это умножение/деление
У тебя есть готовые арифметические процедуры для 32 разрядных? Если да, то я за "тупое переписывание". Пусть даже будет медленнее, чем pirk20, зато больше цифр можно считать.
У меня были процедурки для 32битных, но они, насколько помню, в архиве на другом компе, который сдох (но винт целый).
Ну и у нас ещё одно преимущество: вместо двух операций / и % мы делаем это за одну операцию. Фактически, тоже ускорение почти в два раза.
- - - Добавлено - - -
У тебя есть готовые арифметические процедуры для 32 разрядных?
16*16 -> 32 вроде где-то было (FAT?), а вот деления точно не было. Но что нам стоит дом построить? :)
Была старинная математическая библиотека для 8080, но не могу вспомнить как назывался архив или хотя бы кто автор.
Возможно у vinxru есть готовые процедуры для 32-разрядных для его си?
Конечно можно и заново написать.
- - - Добавлено - - -
В Гуртовцеве Гудыменко есть готовые процедуры для 16*16=32 и 32/16
Вот это можно как-то ускорить (не разворачивая цикл)?
MUL32: MOV B,H ; DEHL = DE*HL
MOV C,L
LXI H,0
MVI A,17
MUL321: DCR A
RZ
XCHG
DAD H
XCHG
JC MUL322
DAD H
JNC MUL321
INX D
JMP MUL321
MUL322: DAD H
JNC $+4
INX D
DAD B
JNC MUL321
INX D
JMP MUL321
Если верить архиву с миллиардом знаков числа пи, который скачал на рутракере, та программа правильно считает максимум 16256 знаков (за 1.7 секунды). Для 8биток выше крыши
Эх, для меня это все очень сложно, качать мегабайтные архивы, сверять :)
Есть путь попроще:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <windows.h>
#define NUMS 280000
int main()
{
static long r[NUMS + 1];
long i, k;
long b, d;
long c;
long x;
c = 0;
for (i = 0; i < NUMS; i++)
r[i] = 2000;
for (k = NUMS; k > 0; k -= 14)
{
d = 0;
i = k;
while (1)
{
d += r[i] * 10000;
b = i * 2 - 1;
r[i] = d % b;
d /= b;
i--;
if (i == 0) break;
d *= i;
}
x = c + d / 10000;
if (x >= 10000)
{
printf("\r\nERROR (%d, %d)", x, k);
break;
}
printf("%.4d", (int)(c + d / 10000));
c = d % 10000;
}
return 0;
}
Сначала оно прикольно упало, когда я NUMS поставил 280000 :), стек коротковат оказался, пришлось static вкрутить.
А потом оно секунд за 10 привело к ошибке:
ERROR (10000, 119266)
Ожидаем четыре цифры, а оказывается их пять, и пятая-то, вот досада, должна быть перенесена в уже выведенное, косяк-с, мда.
Итого - ошибка есть, возникает на 45-тысячной с копейками цифре, если кому надо меньше цифр (ограничен там восьмибитками или еще чего) - то и так сгодится
b2m, у меня по той процедуре идей нет. Обещаю не ударяться в паразитическую оптимизацию :), если что - ты сам потом оптимизируешь.
Vslav
Если заменить long на int64_t, то правильно считает до 54932 знака включительно (за 25 секунд).
У меня пока нет оснований не доверять тому архиву, т.ч. с 45000 я не согласен.
Вот из вышеупомянутой книги, как ни странно - работает :)
DIV32: MOV A,B ; DE = HLDE/BC, HL = HLDE%BC
CMA
MOV B,A
MOV A,C
CMA
MOV C,A
INX B
XRA A
DIV321: DAD H
RAR
XCHG
DAD H
XCHG
JNC $+4
INX H
PUSH H
DAD B
JNC DIV322
RAL
DIV323: INX D
INX SP
INX SP
ADI 10h
JNC DIV321
RET
DIV322: RAL
JC DIV323
POP H
ADI 10h
JNC DIV321
RET
INX SP INX SP
Подобные вещи и в pirk катят, но убрал, чтобы работало и при разрешенных прерываниях (там где они есть).
- - - Добавлено - - -
Это я к тому, что желательно этот фрагмент потом заменить
- - - Добавлено - - -
желательно этот фрагмент потом заменить
Пардон, здесь проблем не будет (у меня несколько другая ситуация была).
У меня пока нет оснований не доверять тому архиву, т.ч. с 45000 я не согласен.
Я тоже не согласен с 45000 :biggrin:
Взял Пи вот тут (http://pi.karmona.com/)
и сравнил с вычисленным по 4-цифровому шпигату (по ссылке что давал litwr и в моем листинге), оно навернулось на 16278 цифре - начиная с нее не совпадает с эталонными цифрами. То есть, найденная мной ошибка - там не единственная.
Update:
там банальное целочисленное переполнение происходит, то есть - не совсем ошибка, просто неприменимость в данных условиях. Поменял типы на 64-битные - доехало до 50К, потом опять ERROR
Update2:
Правильная последовательность с 54920-ой цифры:
61527146690058147000026330
Вычисленная по 4-цифровому шпигату (с int64):
61527146690058146000026330
То есть - перенос 10000 не отработал, ошибка в наличии.
Взял Пи вот тут
Скопировал оттуда, сравнил с ранее полученным результатом
правильно считает до 54932 знака включительно
- эти самые 54932 знака совпали
- эти самые 54932 знака совпали
Да, а потом встречается перенос за четыре десятичных разряда и он игнорится, на 57936-ой позиции имеем липовую цифру 6 вместо верной 7, я заслужил с полки пирожок :)
Нехватает однако 16*16=32 и 32/16=16. Наткнулся на итерацию, в которой после деления 17 бит получается, дальше можно не проверять. Нужны нормальные 32-битные процедуры, но тут регистров уже не хватит. Да и на первый взгляд, медленновато пока получается (пусть даже и неверный результат). Точно не засекал, но даже на глаз - медленнее. Так что первый шпигат - для восьмибиток пока лучше.
Я так понимаю, что нужна процедура переваривающая 32 битные: делимое, делитель и частное. Остаток м.б. 16 битным
Cделал код для 6502. На Коммодоре+4 800 знаков отсчитало за 6 мин 32 сек. Там по cсылке есть указания на алгоритм, по которому миллиарды знаков отсчитал некто Чудновский, с 32-разрядными базовыми константами. Но кода не искал, может где и есть в сети.
Для затравки процедура 32 битного деления для 8080 - 54857
Все 32битное - делитель, делимое, частное и остаток. Очень медленно. Единственный плюс - легко масштабировать хоть до 256 бит.
С делением я разобрался, доделал до 32-битного частного и 16-битного остатка. Сделал так: если надо, деление будет выполнено дважды (для старших двух байт и для младших двух байт). Умножение оставил как есть, но сделал цикл сложением для старшего байта 24-битных чисел. Вобщем, пока считает 100 знаков за 12,5 сек.
Ну и для 536 и 800 знаков результат очень хороший, особенно если учесть, как реализованы умножение и деление.
особенно если учесть, как реализованы умножение и деление.
Ты на что это, царская морда, намекаешь? :)
- - - Добавлено - - -
Хотя, с делением я согласен, для деления старших двух байт можно 16/16 алгоритм использовать.
Но но, папрашу без фамильярнасти!
Фактически у тебя получилось вручную откомпилировать для 8080 с несколько большей эффективностью, чем тот си для z80. И это еще без всяких развертываний циклов и таблиц. Интересно, будет ли эффективно дальнейшее увеличение основания? Хотя для 8080 вряд ли, с учетом роста сложности реализации умножения и деления.
Развернул циклы умножения и деления, теперь 100 знаков 10.644 сек.
будет ли эффективно дальнейшее увеличение основания?
Видимо нет. Если считать по 5 знаков за раз, то делить/умножать нужно будет уже на 100000, а оно в 16 бит не полезет. Эффективные процедуры для "честных" 32-битных умножения/деления я вряд-ли сделаю. Да и неизвестно, что там будет после умножения на 100000, может произведение и в 32 бита не влезет.
Тут похоже никого кроме как с РК86 и нет. Кроме бкашников, возможно никто и не знает. Но прикрепляю программку и снимок экрана.
800 знаков за 5м 41с
100 знаков за 5.8c
Использовалось умножение с 2К таблицей и деление с раскрученными циклами.
На БК должно хорошо деление получится, а с умножением будет плохо - медленно там с байтовыми таблицами.
54870
54869
Результат 100 знаков за 10 сек. на Радио-РК впечатляет. Это на 2 МГц? Популярнейший Коммодор 64 (как и АГАТ) с этой программкой не должен справиться быстрее чем за сек 14.
Проверил программку на типовом ПК c AMD 3.4 МГц и N=210000, никаких ошибок переполнения d не было, но расхождение на 32375-й цифре. Пи брал с программы Reduce (https://en.wikipedia.org/wiki/Reduce_(computer_algebra_system)).
Результат 100 знаков за 10 сек. на Радио-РК впечатляет. Это на 2 МГц?
1.78МГц!!!
Насчет программы с арктангенсами (http://algolist.manual.ru/maths/count_fast/pi.php). Она работает, но последние цифры выдает неправильно. Т.е. например, чтобы правильно посчитать 1000 цифр, нужно задать расчет 1004 цифр. И, похоже, с определенной цифры она начинает совсем неправильно считать. Но, повторюсь, 1000 цифр посчитать ею можно. Причем, если уменьшить константы
short B=10; /* Working base */
short LB=1; /* Log10(base) */
short MaxDiv=57; /* about sqrt(2^15/B) */
то все long можно заменить на short
- - - Добавлено - - -
C short считает правильно до 4138 цифр
- - - Добавлено - - -
В исходном виде (с long) считает заметно лучше spigotа с основанием 10000, который с 64-битной арифметикой считал правильно только до 54392 цифр. Арккотангенсная программа правильно посчитала и 110000, наверняка и больше правильно посчитает, но это уже долговато.
- - - Добавлено - - -
Ну и 200000 знаков правильно посчитала почти за 5 минут. Дальше не буду пробовать, это уже и для 16биток многовато
1.78МГц!!!
8080 совсем неплох для арифметики, z80 тут ничего почти не улучшает, только частота повыше.
Прогнал вашу программку (с минимальным подгоном под систему) на Amstrad CPC6128 c z80 на 4 мгц (реально 3.2).
5487454875
Результаты: 100 знаков - 6.14 с, 800 - 6м 4.91c, 1000 - 9м 26.82c
Интересно будет сравнить со Спектрумом...
Ha Commodore+4 1000 знаков за 9м 1.04c (программку чуть улучшил - 54876).
Получается, что на "тяжёлой" арифметике 6502 только раза в полтора побыстрее на одинаковой частоте.
Под z80 можно заметно оптимизировать, да и для 8080 предел не достигнут.
perestoronin
11.11.2015, 23:40
с определенной цифры она начинает совсем неправильно
Для каждой точности есть свой вариант уточненной формулы Мэчина.
Самая простая формула обладает невысокой точностью, но при этом является более быстрой.
https://en.wikipedia.org/wiki/Approximations_of_π
Думаю, что упущен момент с расчетом неких констант, выраженный в этой программе на бейсике:
; This BASIC program was used to calculate the equates for PIF.ASM.
; DEFDBL A-Z
; INPUT "Digits required"; A
; MPVSize = 32 * ((A / (LOG(2) / LOG(10)) + 255) \ 256)
; PRINT "NumDigits = "; A + 64
; PRINT "MPVSize = "; MPVSize
; k = A / .69897
; k = INT(15 + (k + k * .1)) 'floor 1
; PRINT "Last1 = "; k
; k = INT(15 + (A / 2.37)) 'floor 2
; PRINT "Last2 = "; k
;
numDigits=164
mpvSize=74
last1=172
last2=57
- - - Добавлено - - -
Насчет программы с арктангенсами.
Реализация на Си далека от идеала. Смотрите реализацию на асме 286 и возможно ли её перенести на 8080 без потери эффективности ?
https://sites.google.com/site/richgel99/index/286-assembler-machin-series-pi-calculator
возможно ли её перенести на 8080 ?
У меня был опыт переноса небольшой программки с 8086 на 8080 (15 лет назад :) ). Получилось довольно медленно и длинно, но зато работало. Это, конечно, не значит, что нельзя нормально конверснуть с писи, но имхо лучше реализовывать алгоритм для 8080.
b2m, чтобы ты был в тонусе - в категории до 535 байт дожал (с предварительным расчетом таблицы и еще кое-какими изменениями) pirk 100 знаков до 10.61 сек. Твой ход :). pi32 100% можно оптимизировать до 10 и менее секунд, может даже до 8-9.
Насчет переносов могу привести такой пример. Несколько лет назад с помощью рекомпилятора Tim0xи адаптнул распаковщик megalz с z80 на 8080. Потом оптимизировал его и все такое. А потом b2m по сишному распаковщику написал распаковщик для 8080, который (если не изменяет память) в разы быстрее. Да, там тоже можно пару байтов и пару тактов скинуть, но в разы его уже не улучшить. Это я к тому, что с си вполне можно написать нормальную программу для 8080, что уже не раз демонстрировал b2m, и, с другой стороны, с асма на асм можно довольно неудачно перенести.
b2m, чтобы ты был в тонусе - в категории до 535 байт дожал (с предварительным расчетом таблицы и еще кое-какими изменениями) pirk 100 знаков до 10.61 сек. Твой ход :).
Без таблиц 12.77 сек. Если добавишь свои таблицы, наверняка будет быстрее 10 сек.
pi32 100% можно оптимизировать до 10 и менее секунд, может даже до 8-9.
Ну не знаю, я уже и циклы деления/умножения развернул, а оно всё равно только 10.64 сек.
pi.rar - зачетно. Я собирался модифицировать первоначальный spigot подобным образом, а ты уже сделал.
Под z80 можно заметно оптимизировать, да и для 8080 предел не достигнут.
Извините, но что можно тут оптимизировать под z80? Хотя бы одно что-нибудь можете указать? А предел никогда не будет достигнут, если не зафиксировать алгоритм. Неужели тут нет никого со Спектрумом?!
что можно тут оптимизировать под z80? Хотя бы одно что-нибудь можете указать?
Первое, что приходит в голову - деление. Тут и команды вычитания регистровых пар пригодятся (для ускорения восстановления остатка) и дополнительные регистры.
b2m ленится оптимизировать "по-мелкому", а мне было интересно. Заменил в последнем pi.rar умножение и деление:
100 цифр - 12868015 тактов - 7.24 сек
536 цифр (из них 535 верно) - 351958021 тактов - 3 мин 18 сек
Просто охренеть. И там еще есть резервы, я их не трогал, тупо заменил процедуры. А так явно можно 100 знаков меньше чем за 7 секунд посчитать. Как бороться с b2mом?
- - - Добавлено - - -
Уточню - это без учета времени расчета таблицы умножения
balu_dark
13.11.2015, 15:21
b2m ленится оптимизировать "по-мелкому", а мне было интересно. Как бороться с b2mом?
Самый простой вариант - добавить ему пурген в чай.
А вообше - очень интересная тема - с удовольствием слежу. пока нет возможности проверить или поправить на 8ми битке.
Как бороться с b2mом?
Исключительно личным примером :)
- - - Добавлено - - -
добавить ему пурген в чай.
Э... проверено на личном опыте?
Во избежание недоразумений заменю формулировку своего риторического вопроса на более корректную - Как соревноваться с b2mом? Для себя у меня есть отмазка - я (практически) не программист.
Интересно было бы увидеть реализацию для 8080 более эффективного алгоритма.
balu_dark
13.11.2015, 18:02
Э... проверено на личном опыте?
Не :) Прочитано в книжках. Как ненасильственный метод борьбы :) Ибо согласно нашему уголовному кодексу - "публичные призывы к ...." малость наказуемы :)
А ivagor к тому моменту не уточнил - что он хочет побороть.
Первое, что приходит в голову - деление. Тут и команды вычитания регистровых пар пригодятся (для ускорения восстановления остатка) и дополнительные регистры.
Слышал от знатоков z80, что быстрые программы IX, IY не используют. 16-битная разность почти бесполезна из-за отсутствия беспереносного вычитания, а ставить перенос на z80 морочно - проще складывать дополнительные коды. Система команд z80 определенный лидер конкурса некрасоты. Разве только второй набор регистров... Но их лучше возможно к прерываниям прикрепить.
Вот, например, деление на z80 - http://cpcwiki.eu/index.php/Programming:Integer_Division#32bit_division - другого там раньше не было. Оно раз в 5-6 (!) медленнее DIV32 в программе для Радио-РК (pirk)! :) Кстати последний вариант pirk - это просто шедевр какой-то. :v2_dizzy_champagne:
Пора посмотреть на сверхскоростной 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/
Насчет выкладывания семисекундного+ варианта - я тут обещал больше не заниматься (по крайней мере в этой теме :) ) паразитической оптимизацией программ b2mа, так что выкладывать очередную версию было бы непоследовательно и нехорошо. Правильнее было бы даже и не писать про нее, но эмоции переполняли. При желании быструю версию можно собрать самостоятельно, нужно только заменить умножение и деление. Умножение можно взять из pirk20 (там еще можно таблицу расположить с 0000h и избавиться от лишнего inr). Деление проще взять из предыдущего pirk, в 20 уже немного иначе сделано. Если вдруг сам реализую какой-нибудь другой вариант расчета, то выложу, но это очень маловероятно.
- - - Добавлено - - -
Кстати, насчет реализации умножения и деления на z80 - не новая, но очень хорошая статья (http://ivr.webzone.ru/articles/dop_ar/). Думаю про нее большинство знает, но может кто не читал. И, конечно, то, что там написано, вполне можно адаптировать для других процессоров.
И где же он этот сверхскоростной на 7 сек?
Вот вариант без таблиц, но он 8.89 сек. 54896
Умножение 16*16=32 на 8080 заметно выгоднее реализовать через два умножения 16*8=24 и сложение. Это я про без таблиц, с ними, понятное дело, еще быстрее.
- - - Добавлено - - -
Это я про без таблиц, с ними, понятное дело, еще быстрее
Тут я был не совсем прав. Время четырех умножений 8*8 с использованием таблицы квадратов вполне сравнимо с одним умножением 16*16, реализованным через два умножения 16*8 (с развернутыми циклами). Т.е. маленькая таблица в данном случае не особо поможет.
Умножение 16*16=32 на 8080 заметно выгоднее реализовать через два умножения 16*8=24 и сложение.
Да, если при этом учесть, что когда старший байт равен нулю, то можно и одним умножением обойтись. DAD H/RAL немного быстрее, чем сдвиг пар DE/HL, тут можно выиграть пару тактов, лишь бы сложение их потом не съело.
- - - Добавлено - - -
По совету ivagor-а переделал умножение. Теперь этот модифицированный spigot, выдающий по 4 цифры за цикл, работает 8.14269 сек.
Мне именно pi32 представляется самым перспективным вариантом и по количеству рассчитываемых цифр и по возможности ускорения.
Мелкий момент - связки JNC $+4 \ INR A лучше заменить на ACI 0 (это не я придумал, прочитал в журнале МПСиС, номер не помню).
Да, чёт я тупанул, подумал об этом уже когда выключил комп (отлучиться надо было). Думал ты не успеешь заметить :)
Вот правильный вариант: 54904
З.Ы. в связи с новой реализацией умножения выкинул пару MOV там, где она используется, теперь 8.117 сек.
Умножение в pi32 вряд ли уже удастся заметно улучшить, теперь бы деление оптимизировать.
Кстати, насчет реализации умножения и деления на z80 - не новая, но очень хорошая статья (http://ivr.webzone.ru/articles/dop_ar/). Думаю про нее большинство знает, но может кто не читал. И, конечно, то, что там написано, вполне можно адаптировать для других процессоров.
Посредственная статья. Там нет алгоритма умножения с 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.
Нужны ли программки? Неужели кто-то их запускает? Тема интересная, плохо что не получилась популярной. :v2_dizzy_tired2:
sergio78
15.11.2015, 23:22
это получается что 6502 быстрее z80, архитектурно лучше сделан? несмотря на то что сделали 6502 раньше на несколько лет. слышал у 6502 ещё хитрый 10 значный режим имеется, случаем не его здесь испльзуют в подсчётах?
Посредственная статья
На мой взгляд хорошая обзорная статья, в которой рассмотрены основные алгоритмы и приведено много ссылок. Да, готовые процедуры там не на все случаи жизни, но для 8080 я оттуда готовыми и не пользовался, а вот некоторые алгоритмы впервые увидел там (это было, скажем так, не сегодня).
- - - Добавлено - - -
Интересно, что для 8085 можно оптимизировать pi32 на уровне z80 (может даже лучше). Там мало новых команд, но это именно те команды, что надо :)
perestoronin
16.11.2015, 18:59
Формулу числа Пи неожиданно обнаружили в атоме водорода (http://www.vesti.ru/doc.html?id=2687449):
Я даже подпрыгнула от неожиданности, когда мы получили формулу Валлиса из уравнений для атома водорода, – рассказывает Фридман. – То, что чисто математическая формула 17-го века характеризует физическую систему, которая была обнаружена 300 лет спустя, является удивительно красивой связью между физикой и математикой
Может и нам попробовать воспользоваться той самой формулой (http://scitation.aip.org/content/aip/journal/jmp/56/11/10.1063/1.4930800) и сравнить её с другими методами? Хотя думаю она будет очень медленной :)
Сделал пока программку для БК. Запускал в эмуляторе BK-TERAK, который вроде бы работает чуть быстрее чем положено. Проверил бы кто на реальном железе... Спектрум не догоняет. Писать на ассемблере БК одно удовольствие, но работает медленно.
На этом эмуляторе 100 цифр за 6 сек, 1000 - за 9м 21с.
Прикрепляю и файлы для "иностранцев" с исходниками и файлами для эмуляторов или для переноса на железо.
54933
54932
54931
54930
это получается что 6502 быстрее z80, архитектурно лучше сделан? несмотря на то что сделали 6502 раньше на несколько лет. слышал у 6502 ещё хитрый 10 значный режим имеется, случаем не его здесь испльзуют в подсчётах?
6502 - это как окно в мир, где просто делают хорошие вещи, без оглядки на маркетинг и политику. Его сделали по революционной технологии, по которой цена получалась раз в 5 меньше, а скорость в 2-3 большей. Возможно z80 это была глубоко эшелонированная защита связанной с политикой Intel от развития этой технологии, результаты который были достигнуты только с 80186. В итоге фирма MOSTEC была разгромлена еще в 1976 и 6502 штамповали почти без изменений до начала 90-х. Но 6502 успел вдохновить на разработку первых ARM.
Как слышал от знатоков, американских программистов, которые в 80-е писали под разные платформы (6502, z80, 6809, ...), соотношение по скорости 6502 к z80 принималось от 2.2 (меньшинством) до 2.4 (большинством). Хотя на командах пересылки данных ldir/lddr z80 только на 50% медленнее. С другой стороны, на переходах он уже медленнее в 4 раза. По мнению этих же знатоков коды для z80 получались процентов на 10-20 поменьше. Работать c BCD умели и 8080/z80 и все x86 до архитектуры x86-64, но в 6502 это сделано напрямую без дополнительных команд, существенно быстрее.
На мой взгляд хорошая обзорная статья, в которой рассмотрены основные алгоритмы и приведено много ссылок. Да, готовые процедуры там не на все случаи жизни, но для 8080 я оттуда готовыми и не пользовался, а вот некоторые алгоритмы впервые увидел там (это было, скажем так, не сегодня).
Возможно выразился излишне резко. Имел только в виду, что для того, кому нужно умножение или деления, статья малополезна. Прочитав её, можно с неделю сочинять сочинения на тему "хорошие алгоритмы" и только.
Интересно, что для 8085 можно оптимизировать pi32 на уровне z80 (может даже лучше). Там мало новых команд, но это именно те команды, что надо :)
Не перепрограммировались? Насколько знаю, в 8085 новых команд для арифметики нет.
100 цифр за 6 сек, 1000 - за 9м 21с
Интуиция настоятельно подсказывает мне, что 8080 с частотой 1.78 МГц может посчитать почти за то же самое время.
Насколько знаю, в 8085 новых команд для арифметики нет.
Это неплохо документированные "недокументированные" команды. Благодаря dkspb теперь известно, что и в 1821ВМ85 они тоже есть.
- - - Добавлено - - -
Здорово, что сделали расчет пи для БК!
Интуиция настоятельно подсказывает мне, что 8080 с частотой 1.78 МГц может посчитать почти за то же самое время.
Не надорвитесь. :) Сделал ещё вариант для БК0011М с интерфейсом и замером времени по 48.5 Гц прерыванию. В более точном эмуляторе 100 цифр за 4.5 секунды, 1000 - за 7м 31.3с. Это уже близко к Спектруму, а может и чуть быстрее. Для окончательного вердикта нужен прогон на железе.
Не удержался и сделал ещё программку для IBM PC (команды только для 8088). 3апустил в довольно аккуратном эмуляторе первых РС РСЕ (т.е. и примерно и наших ЕС-1840/1841, ...), результат 100 цифр за 1.06с, 1000 - за 1м 26.74с. Получается, что даже по максимуму используя преимущества 8088 (деление, умножение) на частоте 4.77 МГц, скорость его работы сравнима с 6502 на 2 Мгц (Apple III, Commodore CBM II, BBC Micro) или даже с z80 на 4 Мгц. Кстати, упомянутые коммодоры и бибисишки на американский рынок просто не пустили...
54948
5494954950
Это неплохо документированные "недокументированные" команды. Благодаря dkspb теперь известно, что и в 1821ВМ85 они тоже есть.
Благодарю, не знал. Там, действительно, мощные команды, лучшие чем у z80. Странно, что Интел их скрыла - политика... Но разве в Радио-86РК не 8080? В СССРе делать 8085 массово не умели (в вики про 8085 почти ничего)?
Viktor2312
20.11.2015, 10:49
Но разве в Радио-86РК не 8080?
Нет, там КР580ВМ80А.
litwr, респект за разнопроцессорную реализацию расчета пи.
результат 100 цифр за 1.06с, 1000 - за 1м 26.74с. Получается, что даже по максимуму используя преимущества 8088 (деление, умножение) на частоте 4.77 МГц, скорость его работы сравнима с 6502 на 2 Мгц (Apple III, Commodore CBM II, BBC Micro) или даже с z80 на 4 Мгц.
Не врубился - 100 цифр за 1.06с это на какой частоте? Если 4.77, то это довольно неплохо. Ну и программу для 8088 можно заметно ускорить (не стоит использовать команды умножения, таблицы - наше все).
По поводу использования клонов 8085 в советских компьютерах - как минимум были ПК-6128Ц (своеобразный клон вектора) и Русич (своеобразный клон специалиста). Плюс на zx-pk.ru есть темы о новодельных вариациях на 1821ВМ85 (или ИМ85?)
Еще исправлюсь - выше неправильно написал ник dk_spb
- - - Добавлено - - -
не стоит использовать команды умножения, таблицы - наше все
Признаю ошибку, в общем случае mul 16*16 быстрее. Но все же можно немного ускорить *10000
CodeMaster
20.11.2015, 14:14
Не врубился - 100 цифр за 1.06с это на какой частоте?
5 МГц, вряд ли он турбировал 1801ВМ1 до 6-ти.
litwr, респект за разнопроцессорную реализацию расчета пи.
Не врубился - 100 цифр за 1.06с это на какой частоте? Если 4.77, то это довольно неплохо. Ну и программу для 8088 можно заметно ускорить.
Писал же - эмулятор первого писи-5150 - http://www.hampa.ch/pce/pce-ibmpc.html. Конечно, 4.77. В досбоксе надо ставить cycles=fixed 200 примерно, но досбокс для точного времени очень плох.
Ускорьте. :)
вряд ли он турбировал 1801ВМ1 до 6-ти.
Если вы с железом, так дайте результаты. Интересно узнать данные с 6 МГц.
Писал же - эмулятор первого писи-5150 - http://www.hampa.ch/pce/pce-ibmpc.html. Конечно, 4.77.
Дело в том, что цифры не стыкуются.
8088 на 4.77
100 цифр за 1.06с, 1000 - за 1м 26.74с
6502 2.2Mhz 100 - 3.74c, 1000 - 5м 40.02с
т.е. не получается
даже по максимуму используя преимущества 8088 (деление, умножение) на частоте 4.77 МГц, скорость его работы сравнима с 6502 на 2 Мгц
Разве что для 6502 уже ускорили в 3.5 раза, но в треде про это информации я не видел
Для 8088 я бы поускорял, но не на чем проверить и я не в курсе, насколько точна (по таймингам) эмуляция 8088 на сегодняшний день.
Дело в том, что цифры не стыкуются.
В чем проблема? Так и есть в 3.5 раза, но на программе, где почти всё время нужно умножать и делить при частоте процессора в 2.15 более высокой. Если взять не столь заматематезированную проблему, то 6502 на 2 МГц может и обогнать 8088 на 4.77 МГц. :-)
Для 8088 я бы поускорял, но не на чем проверить и я не в курсе, насколько точна (по таймингам) эмуляция 8088 на сегодняшний день
Это отговорка. Дал вам ссылку на очень точный эмулятор. Пусть не на все сто... И потом для сравнения программ абсолютная скорость неважна. Программку можно ускорить, но только подчисткой кода, не меняя алгоритма, полагаю, что только на чуть-чуть.
perestoronin
21.11.2015, 01:21
для сравнения программ,
написанных под разные архитектуры, с разной разрядностью и работающих на разных частотах, и качества подбора алгоритма под архитектуру (использовать можно любые плюшки архитектуры процессора и системы в целом дающие преимущества, в том числе и команды любые умножения и деления, если таковые имеются) - полученные результаты по любому нужно нормировать по разрядности и частоте.
Чтобы получить еще большее ускорение алгоритм придется опробовать иной, отличный от рассматриваемого в предложенных программах.
PS. Умножение табличное 16 на 16 использовать не выгодно.
Думаю ускорение примерно в 1,5 раза (для 1000) потянет на заметное
Думаю ускорение примерно в 1,5 раза
Откуда XMS? Это значит у вас 80286, как минимум (досбокс? :)). На PCE-эмуляторе (первого писи с 8088) ускорение на 40% на 1000 цифрах и только на 25% на 100 цифрах. Хорошую провели оптимизацию, всё что можно загнали в регистры, но, главное, подогнали умножение к случаю. Последнее дало 25% из 40. А первое - с современными оптимизирующими компиляторами не посоревнуешься. Итак, оглашаю данные ваших рекордных программ на почти точном эмуляторе: 100 цифр - 0.82с, 1000 - 54.47с.
Точное время - большая проблема. Сделал для БК0010 вариант с интерфейсом и расчетом до 2000 цифр, а также с подсчетом времени по таймеру. 54980 Случился неприятный сюрприз, эмулятор gid неправильно работает с таймером - не поддерживает бит 1. :-( Все использованные эмуляторы (gid, на яве, бк-терак) берут частоту видеопрерывания 50 Гц вместо 48.5 и работают в режиме 11М на процентов 15 быстрее. Пришлось скорректировать результаты. По БК0010 на 100 цифр 7 сек, 1000 - 11м 35с; по БК0011 на 100 6.1с, на 1000 - 10м 3с. Как это соотносится с реальное техникой - большой вопрос. На эту тему меня пригласил кто-то из бк-ников, переслал сообщение с форума. Удивительно, что никто не возьмётся проверить на железе. Получается Спектрума не догнать даже на математике. Ну и что? БК работает по скорости процессора примерно как самый массовый фирменный компьютер Коммодор-64, т.е. БК11М примерно как z80 на 2.2 МГц без задержек. 3ато Радио-86РК точно БК никогда не догонит. :) Как не хватает в теме знатоков ДВК, УКНЦ, Корветов, Агатов, ...
полученные результаты по любому нужно нормировать по разрядности и частоте
Это почти невозможно, нужно будет учитывать тонкие архитектурные особенности. Вот, например, процессоры Intel 8080 или Zilog 80 в почти 4 раза медленнее, чем 6502 работают с памятью. Но это позволяло использовать более высокие частоты для процессора при работе с медленной памятью - эти процессоры выполняли микрокод между обращениями к памяти. 6502 требовал быстрой памяти - если он не обращался к памяти, то простаивал. Конечно, возможно волюнтаристкое нормирование...
Откуда XMS? Это значит у вас 80286, как минимум (досбокс? ).
Это pce. В конфиге менял всего две строки
model = "8088"
speed = 1
Использовал образ hd0.img, куда дописывал проверяемые программы.
по БК0011 на 100 6.1с, на 1000 - 10м 3с.
Радио-86РК точно БК никогда не догонит.
Насчет РК сложно сказать, но сферический 8080 в вакууме с частотой 1.78 МГц обгоняет.
Lethargeek
22.11.2015, 21:41
это получается что 6502 быстрее z80, архитектурно лучше сделан? несмотря на то что сделали 6502 раньше на несколько лет.
он не лучше, в среднем тактов меньше на операцию, но сами такты приходилось делать длиннее в тех же условиях
код обычно тоже занимал больше места, и вроде как стек его был неудобен для компиляторов
слышал у 6502 ещё хитрый 10 значный режим имеется, случаем не его здесь испльзуют в подсчётах?
BCD (десятичный, а не десятизначный) разве что для бухгалтерии был полезен
- - - Добавлено - - -
полученные результаты по любому нужно нормировать по разрядности и частоте.
правильней скорее по техпроцессу
Это pce. В конфиге менял всего две строки
Маленькая разница возникла наверное, потому что использовал модель 5150. Она, получается, чуть медленнее XT (5160). Он откуда XMS - не понятно, у меня такое не появилось с досом 3.30
вроде как стек его был неудобен для компиляторов
Скорее для многозадачных ОС типа SymbOS, которые появились только в 21 веке. Стек в 6502 ограничен 256 байтами, но в него можно класть и отдельные байты. Обычно 256 байт более чем достаточно и стандартные бейсики иногда использовали низ стековой памяти для временных вычислений.
Lethargeek
23.11.2015, 17:08
Стек в 6502 ограничен 256 байтами, но в него можно класть и отдельные байты. Обычно 256 байт более чем достаточно и стандартные бейсики
и при чём тут, спрашивается, те бейсики, когда я про компиляторы говорил
представь что-то си-подобное с этим стеком
Техпроцесс качественная характеристика, пока рано по ней нормировать
техпроцесс задаёт предел возможной производительности количественно
допустимые частота, разрядность, число конвейеров - производные, вторичные показатели
впрочем, начинайте с чего-нибудь)
Viktor2312
23.11.2015, 21:47
Ну да, при прочих равных железка будет потреблять энергии меньше
Главное, что он позволяет работать на частоте как минимум в два раза выше, а соответственно при равной архитектуре и других прибамбасах, скорость будет в два раза выше. Так что, тех процесс - это первое что необходимо указывать.
представь что-то си-подобное с этим стеком
Если вы не используете рекурсии и не передаёте структур по значению, вложенность вызовов до полусотни достаточна. А если вы используете, то у вас не 8-битный ретрокомпьютер с 64К ОЗУ. Повторю, на 6502 стек позволяет работать с байтами - более эконoмно чем с z80. Но операции со стеком 6502 медленнее чем должны быть при сравнении с другими на 1-2 такта - что-то там не доделали.
Viktor2312
24.11.2015, 12:41
Что в теории позволяет тех процесс, пусть интересует маркетологов и технологов, нас же по факту интересуют реальные ретро-железки, уже выпущенные и работающие, их то мы и сравниваем, а не теоретические возможности современных тех.процессов
А никто и не говорит, про современные тех. процессы, любая, хоть старая, железка выпущена по определённому тех. процессу. И это не теория, а практика, например КР580ВМ80А выпущен по одному тех. процессу и для него номинальная частота 2 МГц, он при этом выполняет простую команду за 2мкс (4 такта по 0,5мкс), д другой проц, старый, ретро, выполнен по более современному тех. процессу и допустим для него номинальная частота 4 МГц, вот тебе уже и ускорение в два раза выполнения одного и того же алгоритма, при всех равных остальных условиях, и пусть это будет старый ретро тех. процесс середины 70-х годов. Вот тебе и практика и никакой теории.
Если есть сторонники уже сейчас нормировать результаты по норме техпроцесса - как "первичного фактора" при сравнении, то справедливую достаточно точную формулу "в студию" , но думаю здесь для справедливости нужна эмпирическая сложная зависимость, для вывода такой формулы у нас пока недостаточно статистики для ретро-железок. Для современных же железок её вполне можно считать линейной, а для ретро - нет.
Зачем такие сложности, просто при описании, нужно его учитывать, если первым пунктом идёт микропроцессор, который применяется в системе, на которой проводится тест, то вторым пунктом должен быть указан тех. процесс по которому и в соответствии с которым он выполнен/произведён.
Версия pi32 для Вектора
5506355064
100 цифр - 4.34 сек
1000 цифр - 403.50 сек - 6 мин 43.50 сек
Процедурой деления DIV320 я можно сказать горжусь.
В целом этого спигота для 8080 уже вряд ли удастся сильно оптимизировать.
Если пересчитать на частоту 1.78МГц, то 7.32 сек. Немного быстрее моего варианта, но не на столько кардинально... Хотя, в процентном отношении - неплохая оптимизация.
Дело в том, что тормоза вектора сказываются очень сильно, а на 1.78 МГц без торможения 100 цифр посчитает за 5.62 сек. Еще сказывается более быстрый вывод символов на экран у РК. С другой стороны, на реальном рк все же тормоза есть. Лучше проверять на машинках у которых либо прозрачный доступ к памяти (корвет, орион, специалист) либо тормоза точно эмулируются (вектор).
Альтернативный вариант для вектора. Заменил только процедуру деления. На ней просто отдохнул душой - тут и самомодифицирующийся код и переходы внутрь команды и нецелевое использование sp, в общем экстрим. На компах без торможения она чуть медленнее предыдущего варианта, а на векторе быстрее:
5507255073
100 цифр - 4.16 сек
1000 цифр - 385.82 сек - 6 мин 25.82 сек
Этот вариант деления лучше подойдет не только для вектора, но и для ПК8000 и ПК8002.
Но все имеет свою цену. Данный вариант требует квазидиск, который нужен только для возможности не запрещать прерывания и сохранить подсчет времени. Можно откомпилировать с запрещенными прерываниями (соответствующий фрагмент в исходнике я прокомментировал) - тогда квазидиск не нужен, но время придется засекать секундомером.
у меня есть несколько разных процов z80, в том числе ВМ1 , могу протестить на реале но надо файл для дисковода. Тар я не знаю как загрузить ((((
Самый быстрый (на текущий момент) в данном треде вариант для восьмибитки (ПК-6128Ц)
5510355104
100 цифр - 3.46 сек
1000 цифр - 319.62 сек - 5 мин 19.62 сек
Сыграли два преимущества 8085 над 8080
1. Более быстрое исполнение востребованных команд, что особенно актуально при вектороподобном торможении.
2. Оптимизированная процедура деления. Под 8085 есть еще что оптимизировать, но я поработал только над делением.
sergio78
04.12.2015, 19:28
https://ru.wikipedia.org/wiki/Motorola_6809 - говорят лучшая 8 битка. значительно лучше чем 6502. в теме никто под неё не пробовал pi подсчитать.
100 цифр - 3.46 сек
1000 цифр - 319.62 сек - 5 мин 19.62 сек
Ну и ну! Надо загрузить эту программку в Амстрад и подозреваю, что Амстрад станет чемпионом опять. :) Что-то вы с делением сделали фантастическое, даже прежняя процедура DIV32 была лучшим такого рода алгоритмом во всей сети! Даже удивительно, просматривал все (?) архивы z80 - там лучшего нет.
никто под неё не пробовал pi подсчитать.
Хотелось бы, но железо с 6809 какое-то больно экзотическое и редкое: Драконы, цветные Тэнди...
Улучшил оформление программ для PDP-11 (БК, ДВК, ...), добавил поддержку аппаратных деления и умножения. На диске программы с буквой М с умножением - 11М может обгонит и Спектрум и Вектор. Уважаемый perestoronin, надеюсь что вы сможете найти способ их и/или подобные протестировать. Программа с буквой T для 11M считает время по таймеру, а не видеопрерыванию - может это будет полезно для авторов эмуляторов. В исходниках программа и для RT-11 (ДВК, БК0011М, ...) с опциональной поддержкой как умножения, так и деления - кто бы протестировал? Интересны ДВК-3, а эмулятора нет. :(
55119 (исправлен файл для RT-11)
Надо загрузить эту программку в Амстрад и подозреваю, что Амстрад станет чемпионом опять.
Эту в амстрад не получится, здесь используется команда rdel. Но несомненно амстрад обгонит вектор, против z80 с большей частотой не попрешь.
прежняя процедура DIV32 была лучшим такого рода алгоритмом во всей сети
Думаю просто никто особо не занимался оптимизацией 32 битных операций с целыми для 8080 и z80 ввиду неактуальности. Любая из двух вышеприведенных процедур для вектора будет быстрее исходного амстрадовского варианта. Но и под z80 можно оптимизировать. Возможно спектрумисты уже оптимизировали, просто надо найти их вариант.
CodeMaster
05.12.2015, 08:11
добавил поддержку аппаратных деления и умножения.
Это для ВМ1Г? vslav сейчас делает потактовый клон БК на FPGA с разными процами, надо будет с ним поговорить. Но, мне кааца, он говорил по итогам реверса кристаллов, что аппаратное умножение/деление в ВМ1Г весьма формальное и заметного выигрыша скорее всего не даёт. Там же можно проверить вычисление на ВМ1 на 100 Мгц ;-)
несомненно амстрад обгонит вектор
Не уверен, частота у Амстрада на треть выше, но дополнительные инструкции 8085 выглядят помощнее и оптимизаторы поэнергичнее. :) Удивительно сходство архитектур Вектора и Амстрада по части работы с процессором. А знаете ли сколько было выпущено ПК-6128Ц? Как к этой модели относится, как к серийному или опытному компьютеру? Неужели у вас настоящий?! А был ещё Вектор-Турбо+, лучший в мире Спектрум - Пентагон, ...
32 битных операций с целыми для 8080 и z80 ввиду неактуальности
Их до сих пор используют, но в современных значительно ускоренных выриантах. Вот неплохая библиотека для z80 http://z88dk.cvs.sourceforge.net/viewvc/z88dk/z88dk/libsrc/_DEVELOPMENT/math/integer/fast/l_fast_divu_32_32x16.asm?revision=1.2&view=markup
вывод результата надо исключить из подсчета времени расчета числа
Времени там менее 1%.
не отвечает
На него похоже.
Интересны ДВК-3
100 знаков- 0,7сек.
1000 знаков- 64,7сек.
4680 знаков- 1409,8сек.
дополнительные инструкции 8085 выглядят помощнее
По крайней мере rdel быстрее adc hl,hl, это да, важный момент. Но у z80 свои фишки
А знаете ли сколько было выпущено ПК-6128Ц?
Меня этот вопрос тоже очень интересует.
Неужели у вас настоящий?!
Нет, я все прогоняю в эмуляторах, но dk_spb проверял на реальном 6128 и тест быстродействия всех команд и тесты флагов, т.ч. эмуляция 8085, причем с правильными тормозами, в emu и VV точная. Правда b2m немного поломал ее с определенной версии, но уверен, что и с emu все будет хорошо (может даже уже).
Самый быстрый (не спектрумоподобный) реал с z80 у читателей/писателей форума сейчас пожалуй Орион-ПРО. Как минимум у двух человек он работает, возможно стоит и для него сделать версию. Ее точно нужно проверять на реале, т.к. точной эмуляции задержек для режима 10 МГц (пока?) нет.
Времени там менее 1%.
Вот кстати где как. На компах с аппаратным текстовым экраном все хорошо, а при выводе на графический может быть и больше. В векторовских CP/Mах очень медленный вывод на экран. Корвет опередит вектор в pi32, но 6128 все же быстрее корвета.
- - - Добавлено - - -
Ничего себе ДВК-3 скоростной
100 знаков- 0,7сек.
1000 знаков- 64,7сек.
4680 знаков- 1409,8сек.
Очень вам благодарен, лет 20 что-то такое хотел узнать. А ещё бы сравнить выгоду от аппаратных деления и умножения. :) Чтобы использовать только программные надо поставить HMUL=HDIV=0. На PDP-11 эти операции только знаковые и перевод, особенно деления, в беззнаковый формат непрост. Поэтому выгода от аппаратных операций наверное не слишком большая.
ВМ1Г весьма формальное
Что ждать уважаемого vslav'a - может в этой теме быстрее накопаем? :)
На компах с аппаратным текстовым экраном все хорошо, а при выводе на графический может быть и больше.
Почтим уверен, что у всех - менее процента - там печать один раз после большого цикла. А вот в долях процента может быть разница раз в 10, которая ни на что в итоге не влияет.
Корвет опередит вектор в pi32, но 6128 все же быстрее корвета.
Противоречие
Противоречие
При выполнении pi32 6128 быстрее корвета, корвет быстрее вектора. В чем противоречие?
- - - Добавлено - - -
Почтим уверен, что у всех - менее процента - там печать один раз после большого цикла
У самых медленных векторовских версий cp/m 100 символов будет печатать 0.3 секунды! Это значительно больше 1% для 100 цифр. Для тысячи цифр, конечно, это пустяк
HMUL=HDIV=0
100 знаков -1,8сек.
1000 знаков -183,4сек.
4680 знаков -4265,2сек.
Оффтоп
с emu все будет хорошо (может даже уже)
Оказывается b2m еще позавчера поправил. С версии 03.12.2015 у 6128 в emu снова правильные тайминги
Реальный 1801ВМ1Г, на модуле + плата DE0, частота 5МГц, быстрая память без ожидания, терминал асинхронный, время измеряется 50Гц таймером
При HMUL=0 (программное умножение)
1000 знаков - ~261,7 сек
100 знаков - ~2,6 сек
При HMUL=1 (аппаратное умножение, инструкция MUL)
1000 знаков - ~195,6 сек
100 знаков - ~2,1 сек
Итого - аппаратное умножение на ВМ1Г полезное, потому что программное - еще медленнее.
в цикле вычисления есть два умножения и два деления, так что вклад именно умножения в конечный результат немного размыт.
Update: на 100МГц реплике (ВМ1Г, HMUL включен) время вычисления 1000 знаков - 9.14 секунды, забавно производительность с частотой отмасштабировалась - в 20 раз подняли частоту, в 20 раз выросла скорость.
Корвет опередит вектор в pi32, но 6128 все же быстрее корвета.
При выполнении pi32 6128 быстрее корвета, корвет быстрее вектора. В чем противоречие?
В этих двух ваших фразах. Или вы противопоставляете разные Векторы? Если так, то понятно.
Аппаратное умножение должно дать существенный выигрыш, странно, что разница почти не заметна
Архитектура PDP-11 какая-то спартанская: мало памяти, ФС без сверхминималистская, но как-то душевно и качественно в мелочах, трогательно. В наших вычислениях главный тормоз - это деление, поэтому разгон умножения проявляется незначительно. Возможно, если ivagor возмется за оптимизацию деления на pdp-11, то это даст выигрыш больший, чем аппаратное умножение.
знаков без их вывода на экра
Извините, но это уже какое-то выхолащевание. Какой-то компьютерный аутизм... Скорость вывода на экран - это тоже характеристика архитектуры. По данным ivagor даже в самом крайнем случае это менее 10% (0.3 на вывод при более трех на весь счёт и с трудом верится в компьютер, печатающий 1000 знаков за три секунды), и это при том, что он сам скорее работал с другой системой. Есть же категория 100 символов, 1000 символов. В первой вывод на экран чуть влияет, но только в крайне редких случаях, которые можно и отметить как недостатки системы.
А теперь сюрприз, полученный благодаря уважаемому form: данные по PDP-11/83 (процессор на 18 мгц (?), 4 мб памяти, RT-11 v5.7).
100 знаков - 0.3/0.2/0.5
1000 знаков - 21.8/21/49
2000 знаков - 85.9/84/199.2 (больше посчитать не получилось, система выдала только 21 кб свободной памяти, а про VRUN не знал).
Первые числа - это время стандартного счета, вторые - время без вывода на экран, третьи с выводом, но без EIS.
Аппаратное деление более, чем вдвое ускорило работу. Любопытно, что на ДВК-3 - втрое. Может это какой-то особенный ДВК, с улучшенным процессором?
Привёл данные по выводу на экран только с целью показать их незначительное влияние на результат. Знаки пролетали пол-России прежде чем напечататься. Больше таких данных приводить не собираюсь. Гораздо больше погрешностей могут дать эмуляторы редких компьютеров, хороший эмулятор не один год пишут. А тут используют эмуляторы мелкосерийных компьютеров и даже может опытных образцов. БК сравнительно массовый компьютер, а эмулятора с точными таймингами и близко нет.
Запустил модуль на 1801ВМ2, на 10МГц (внутренняя эффективная ядра 5МГц), пока только с аппаратным умножением (программа та же что для 1801ВМ1Г):
1000 знаков - 83,7 сек
100 знаков - 0.92 сек
Кстати, если отнормировать первую цифру 83,7 на частоту 18/5, то получается 23.3 секунды, почти как у J11 в PDP-11/83 из предыдущего поста. А если добавить использование аппаратного деления, то J11 на эквивалентной частоте будет уверено обойден. Такие дела. Архитектурно ВМ2 конечно попроще J11, но и побыстрее удельно на такт, и это неудивительно - у него память микропрограмм внутри, а не в отдельной микросхеме как у J11.
Update:
- на 12.5МГц ВМ2 работать не захотел, хотя и стартанул. Так что пока продолжаем опыты на 10.0МГц
- с аппаратным делением и умножением 1000 знаков - 52.9 секунды, нормируем на 18/5, получаем 14,7 секунды. Этот результат лучше чем у J11. В-общем, если 1801ВМ2 хорошо кормить из быстрой памяти, то он очень даже неплох.
Реальный 1801ВМ1Г, на модуле + плата DE0, частота 5МГц, быстрая память без ожидания, терминал асинхронный, время измеряется 50Гц таймером
А система какая?
Запустил модуль на 1801ВМ2, на 10МГц (внутренняя эффективная ядра 5МГц)
Странно, что выигрыш от деления так мал - менее двух раз - получается на ВМ2 медленное деление - оптимизированным программным можно обогнать. На ВМ2 отделять деление от умножения смысла нет. Лучше дать данные с EIS и без (как с microPDP-11/83). А возможно, что J11 медленнее из-за задержек памяти?
После беглого знакомства с содержимым книги "Алгоритмические трюки для программистов"
Давно известно, что простого способа перевести знаковое деление в беззнаковое нет. Поэтому у Интел их два. И, конечно, энергичный оптимизатор всегда может пару процентов отжать. :)
Нас интересуют скорость вычисления числа Пи
Должен быть результат. Если его нет, то это не программа, а восточная медитация пусть и с высочайшим непостижимым смыслом. :v2_dizzy_vodka: Кого не устраивает скорость вывода пусть оптимизируют, отключают экран на время счета и т.п. Но π нужно показать - иначе будет история про то, не знаю что. ;)
Кроме того, точность эмуляторов редких компьютеров под большим вопросом. 10-40% тут разброса более чем вероятны. Также настораживает непроверяемость данных по 8085 - массовых компьютеров с таким процессором не было и соответственно результаты эмуляции тут очень условны. Кажется, что ответственные за результаты программисты в таких случаях должны хотя бы раз найти возможность сверить полученные данные с реальным железом.
Его требуется сменить
А кто против? Только получается как про двух или даже трёх непойманных зайцев: поиск лучшего алгоритма, исследование быстродействия компьютерных архитектур, поиск лучшего оптимизатора. :) Но и с лучшим алгоритмом в два раза более быстрое деление даст в два раза лучший результат.
у меня есть несколько разных процов z80, в том числе ВМ1 , могу протестить на реале но надо файл для дисковода. Тар я не знаю как загрузить ((((
Для z80 можно взять за основу код для Амстрада. Подставьте туда правильный вызов своей систем для печати знака и уберите (это самое простое) таймерные коды. Если сообщите адрес процедуры печать и ее параметр, а также адрес загрузки, то могу собрать бинарник, который можете поместить куда угодно. Для ВМ1 (БК) есть загрузочный диск, могу сделать bin-файл для загрузки с кассеты, но только для 0010 - для 0011 что-то не так системными вызовами. Даже подозреваю, что ПЗУ 11М по базовым вызовам неработоспособно. :(
А система какая?
Никакой, bare metall. Процессор на модуле, подключенный к отладочной FPGA-плате DE0.
Лучше дать данные с EIS и без (как с microPDP-11/83).
Реальный 1801ВМ2, 10МГц внешней частоты, измерение времени через 50Гц таймер, вывод на терминал асинхронный, по прерываниям (то есть вывод знаков почти не влияет на время)
EIS On (HMUL=1, HDIV=1):
1000 знаков 52,92 сек
100 знаков 0,58 сек
EIS Off (HMUL=0, HDIV=0):
1000 знаков 152,8 сек
100 знаков 1,50 сек
А возможно, что J11 медленнее из-за задержек памяти?
Может быть из-за памяти, можеть быть там частота не 18МГц, может быть и не "честных" 18МГц, а с растягиванием циклов как у F11. Смотреть на конкретную машину надо.
Проанализировал обмен по шине и сделал отдельный вариант моста Winshbone-МПИ для 1801ВМ2 - убрал синхронизацию RPLY по срезу, которая была добавлена для 1801ВМ1, также сделал коротким строб AR. Циклы шины сократились на 2 такта 10МГц, общая скорость теста возросла примерно на 10-15 процентов:
1801ВМ2 @ 10MHz
EIS On (HMUL=1, HDIV=1):
1000 знаков 47,42 сек (было 52,92)
100 знаков 0,50 сек (было 0,58)
EIS Off (HMUL=0, HDIV=0):
1000 знаков 123,91 сек (было 152,8)
100 знаков 1,20 сек (было 1.50)
6128 бьет рекорды:
5514155142
100 цифр - 2.94 сек
1000 цифр - 297.90 сек - 4 мин 57.90 сек
Запустил 1801ВМ3, на данный момент есть непонятки - с включенным таймером не работает устойчиво на 5МГц. Без таймера считает Пи верно и на 6.25МГц. Включаешь прерывания от таймера (тумблером) - зависает. Второй экземпляр процессора пока холодный - может пару раз Пи и с таймером посчитать, прогреется - виснет. На 4.5МГц оба процессора считают Пи с включенным таймером без зависаний. На диаграммах шины все красиво и большим запасом по времянке.
В вообще - 1801ВМ3 медленнее 1801ВМ2 при той же частоте ядра (5МГц):
EIS On, 1000 знаков - 52,5 секунды
Похоже недостаточно высокого уровня на входе CLK (3.3V) - трогаешь щупом - зависает. Припаял резистор 2k2 на +5V стало заметно надежнее - можно потрогать уже, даже тест на 5МГц проходит один раз из трех.
Удалось в векторовской версии получить все и сразу
1. Ускорил
2. Избавился от использования sp в процедуре деления (и при этом она стала быстрее!). Теперь расчет пи полнофункционален (с подсчетом времени) и на голом векторе, без квазидиска
5516055161
100 цифр - 3.48 сек
1000 цифр - 351.14 сек - 5 мин 51.14 сек
Посты с парой предыдущих версий удалил.
Нормально заработал 1801ВМ3А на 7,14МГц
EIS On, 1000 знаков - 41,52 сек
Если удастся заставить процессор тратить 4 такта на выборку, то возможно результат улучшится.
Update: удалось добиться 3 тактов на выборку, итоговый результат 1000 знаков на 7.14МГц - 37,52 секунды.
Версия для вектора с древовидной организацией процедуры деления:
5518755188
100 цифр - 3.36 сек
1000 цифр - 340.00 сек - 5 мин 40.00 сек
Решение несколько спорное, т.к. деление очень сильно разбухло, но зато удалось обогнать текущую версию 6502 не только при расчете 100 цифр, но и 1000.
Никакой, bare metall.
Ну и ну! :)
Быстрый - вызывать для полученной текстовой строки какую-либо функцию подсчета контрольной суммы
Тема и так скучноватая, а удаление вывода на экран сделает её совсем аутичной. И, потом, идя на поводу пожеланий отдельных энтузиастов отдельных систем впадаем в унылое крохоборство. :( Эта погоня за 3% процентами - жалкое зрелище...
удалось обогнать текущую версию 6502 не только при расчете 100 цифр, но и 1000.
Теперь можно смело писать в википедию, что Вектор самый быстрый суперкомпьютер. Там уже кто-то, не жалея длинных предложений, написал (подозреваю, что известно кто), что Корвет чемпион по заливке экрана краской, а графика Вектора лучшая в мире. Ещё бы з/п всем на 150 руб и будет полное "чисто советское" счастье. :) Сам имел дело с Корветами в начале 90-х - ужас!
Какие 6502?! Ну запустим программу на ускорителе для Агата с 5 МГц и что? Или на Atari Lynx. Интересно, конечно, поиспытывать 8085, но выходим на уровень эксперименатальных и почти неизвестных компьютеров... Модель Commodore 65 была выпущена в 1990 тиражом около 1000 штук, но разве можно её сравнивать с другими 8-битными коммодорами? Вектор 6128 модель 1991 года и очень редкая... Удивительно почему 8085 так не часто использовали - его гораздо проще подключать, меньше нужно всяких интерфейсных схем... За рубежом более-менее понятно - сложная политика, а в России? Кстати, упомятутый ускоритель получался простым наращиванием напряжения до 20 вольт, а можно так с 8080, ВМ1, ВМ2, ... ?
Уважаемый ivagor, стремление довести код до максимальной скорости делает его нечитабильным - не стал разбираться с тем, что вы сделали. Не советую разбираться и со своим. Такие коды делают их неотделимыми от авторов и затрудняют тестирование с другими системами. Как, например, теперь объективно сравнить результаты с БК? Сидеть кому-то несколько дней, изучать проблему быстрого деления?
Собрал данные по разным коммодорам.
Commodore 64 PAL - 5.87 c - 572.4 c (9m 32.4s) - 5138.9 c (85m 38.9s)
Commodore 128 - 3.17 c - 303.3 c (5m 3.3s) - 2720.4 c (45m 20.4s)
Commodore +4 PAL - 2.77 c - 266.5 (4m 26.5s) - 2390.4 (39m 50.4s)
Данные по 100, 1000 и 3000 цифр.
http://www.lemon64.com/forum/viewtopic.php?p=709114#709114
Очень просто - по секундомеру.
Не понял, как тут возник секундомер? Речь была о том, что сравниваться стали не алгоритмы или техника, а трудозатраты. Потратим 1000 человекочасов и получим более быструю программу, чем те, кто потратил 100. Но как это отобразить, нормировать? Не для всякой платформы найдутся желающие в этом чем-то не совсем нормальном участвовать.Поэтому вопрос, как сравнивать с БК, остаётся. Повторю, именно с БК, а не с конкретным кодером.
И пару слов не в тему. Отпимизирующий компилятор легко сделает любого программиста на ассемблере, если только тот не готов тратить раз в 100 больше времени на разрaботку кода, имея лишь шанс догнать компилятор. А смысл модных языков может в том и состоит, чтобы развивать способности человека, а не максимально утилизировать железо. :) Написать рекурсию в лябда-функции - это какой-то новый уровень развития серого вещества. :)
стремление довести код до максимальной скорости делает его нечитабильным
Да, но хотелось максимально ускорить. Обычный (по крайней мере для асма) размен понятности на скорость. Правда можно написать комментарии, только не хочется.
Возвращаясь к приземленным вопросам - версию для 8080 можно еще немного ускорить за счет оптимизации умножения. Через таблицу квадратов ускорить не получалось, но получилось (немного) быстрее с использованием таблицы процедур. Таблица генерируется перед началом работы. Занимает 16 Кб, но можно ужать до 8, но так будет медленнее. Хотелось бы выйти из 3 секунд для 100 и из 5 мин для 1000, но не уверен, что это получится.
UPD: Про ВМ85 убрал, т.к. пруфов по датам и ценам привести не могу, т.е. мог ошибиться
Отпимизирующий компилятор легко сделает любого программиста на ассемблере
Для 8080 (да и для z80 вряд ли) подобных высокоэффективных компиляторов C нет и никогда не будет (к сожалению).
Viktor2312
19.12.2015, 23:47
Скачать Левенталь Вар.1 (https://yadi.sk/d/y0VRFLFhmLqrb)
Скачать Левенталь Вар.2 (https://disk.yandex.net/disk/public/?hash=9d5g6WO3oeNa0p12nZIhpStH//Y1BPLVgqEnPcEsJwc%3D)
Скачать Левенталь Вар.3 (https://yadi.sk/d/NZXlY8FqmLr65)
Скачать Гудыменко Вар.1 (https://yadi.sk/d/QXDKJ4c5mLrML)
Viktor2312
20.12.2015, 01:20
Вероятно потребуется помощь коллег математиков для подбора подходящего алгоритма, позволяющего перешагнуть далеко за 3 сек для скромной целочисленной арифметики ретро-процессора КР580ВМ80А.
Наша скромная Арифметика, уже порвала пентиум-2
Вот простенькая программа на Паскале, считающая пи этим способом... Четыре первых знака требуют на моем PentiumII-300 около 5 минут...
Lethargeek
20.12.2015, 05:56
Для 8080 (да и для z80 вряд ли) подобных высокоэффективных компиляторов C нет и никогда не будет (к сожалению)
И не может быть, потому что свойственное опытному "восьмибитному" ассемблерщику трюкачество (от самомодифицируемого кода и жонглирования ограниченными регистрами до подбора удобных адресов и даже команд с удобными опкодами) даже сверхвысокоэффективный компилятор сможет в лучшем случае повторить, но не превзойти. Ну, разве что, появится сверхкомпьютер, способный за не очень долгое конечное время забрутфорсить код на несколько килобайт :)
Viktor2312
20.12.2015, 14:19
А мне ББП понравилась, буду ради интереса её использовать, изящная и красивая.
Формула Бэйли-Боруэйна-Плаффа (BBP-формула, Формула ББП) для вычисления n-го знака числа Пи в шестнадцатеричной системе счисления. Формула позволяет найти любую цифру числа Пи без необходимости вычисления предыдущих. Формула была впервые открыта в 1995 году Саймоном Плаффом и называется в честь авторов статьи, где формула была впервые опубликована, Дэвида Бэйли, Питера Боруэйна и Саймона Плаффа. До выхода статьи, она была опубликована Саймоном Плаффом на персональном сайте. Формула выглядит как:
https://img-fotki.yandex.ru/get/15481/139302065.6/0_14fe33_f0f1253_orig.png
компиляторы пишут
Сам пишу (и даже для БК что-то сделал :)) и знаком с программистом, который над gcc работает и который сделал лучшие в мире генераторы компиляторов по LR(k) и Эрли разбору. Для хорошей оптимизации надо просто очень много квалифицированнного труда - ничего сверхестественного. Программист против отпимизатора - это ремесленник против конвейера. Конечно, речь не о 8-битных системах.
что скажут поклонники Колибри
А это с какого боку? Сам поклонник Колибри - времени не хватает на активную поддержку. :( Удивлен, что вы не сообщали на первом сообщении о результатахпо ДВК, ВМ2, ...
версию для 8080
Дело в том, что любой код для 8080 или 8085 (с недокументированными инструкциями) можно механически переносить на 6502. Будет получаться код в худшем случае на 50% более быстрый для 6502 на той же частоте, т.е. 6502 на 2 МГц как 8080 на 3 МГц. А если не механически, то тут можно и на 100% и более пробовать. Коды вы сделали очень хорошие, но их привязка к такой поздней и почти неизвестной модели (скорее к сомнительной эмуляции) делает их "слегка" проблематичными.
Lethargeek
20.12.2015, 19:07
Программист против отпимизатора - это ремесленник против конвейера. Конечно, речь не о 8-битных системах.
Если речь о современных системах, то вроде как человеки пока лучше оптимизируют некоторые векторные расчёты. Да и в целом компиляторы до сих пор не свободны от недоработок, а то и элементарнейших ляпов (тот же gcc года полтора тому назад не умел в цикле с уменьшением до нуля делать переход к началу по флагу знака)))
Поработал немного с кодом для 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! :) Извините, если раньше, что не так написал...
litwr, спасибо за высокую оценку :)
Это не предел, пока еще есть надежда выйти на векторе из 3 сек для 100 и из 5 мин для 1000
- - - Добавлено - - -
5533255333
100 - 2.9768 сек
1000 - 298.9832 - 4 мин 58.9832 сек
UPD: Заменил на версию с более точным подсчетом времени (само вычисление пи не менял) - теперь учитывается, что кадровая частота вектора не 50 Гц, а 50.08 Гц.
CodeMaster
25.12.2015, 21:24
100 цифр - 2.98 сек
1000 цифр - 299.46 сек
Линейная функция - 0,03 сек на 1 цифру. Прошлые алгоритмы не были такими линейными.
Увеличил (http://zx-pk.ru/showthread.php?t=25783&p=848330&viewfull=1#post848330) точность подсчета времени
- - - Добавлено - - -
0,03 сек на 1 цифру
Это для 100 цифр, для 1000 в среднем 0,3 сек/цифру
CodeMaster
25.12.2015, 22:02
Это для 100 цифр, для 1000 в среднем 0,3 сек/цифру
А, блин точно ;-)
Заменил на версию с более точным подсчетом времени
Ваши коды мне напоминают записи прохождений мастеров по думу :) - уровень чемпионов. :) Ещё бы выкладывали версии и для других компьютеров Радио-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 везде бы дожали. :)
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
27.12.2015, 17:56
Дальнейшая оптимизация скорости расчета числа Пи для 100 знаков возможна только подбором алгоритма расчета под конкретные процессоры.
И действительно, сначала путем перевода "с Бейсика на ассемблер" получили ускорение в 10 раз. Затем шаманскими манипуляциями получили еще 10 кратное ускорение. Итого от перехода с Бейсика (Java, Си++) на ассемблер со сравнительно небольшими издержками в затратах в часах, можно получить ускорение во всех расчетных модулях как минимум в 100 раз!
А теперь представьте что Ваш любимый гаджет может перестать быть тормозным, а точнее мог бы и не быть никогда тормозным вовсе.
Как я ранее отмечал для 8080 достигнут абсолютный максимум по скорости для выбранного алгоритма. Хотим новых рекордов? Нужно искать новый алгоритм, более подходящий под 8080, чем ранее выбранный.
почти точно в 10 раз
Т.е. в 100 раз?
И вы уверены, что эмулятор даёт правильную частоту кадров? Все известные мне эмуляторы БК вместо положенных 48.5 Гц упрямо дают 50.
стараясь уменьшить применение самых торозных
Вы ещё и на этом оптимизируете?! Вам надо сайт какой-то сделать, сохранить коды для Истории. :) Был до ваших разъяснений уверен, что 8080 и z80 по тактам одинаковы, оказалось нет... INC на z80 быстрее, а ADD HL наоборот медленнее...
почти точно в 10 раз
Т.е. в 100 раз?
И вы уверены, что эмулятор даёт правильную частоту кадров? Все известные мне эмуляторы БК вместо положенных 48.5 Гц упрямо дают 50.
стараясь уменьшить применение самых торозных
Вы ещё и на этом оптимизируете?! Вам надо сайт какой-то сделать, сохранить коды для Истории. :) Был до ваших разъяснений уверен, что 8080 и z80 по тактам одинаковы, оказалось нет... INC на z80 быстрее, а ADD HL наоборот медленнее...
ассемблер со сравнительно небольшими издержками в затратах в часах, можно получить ускорение во всех расчетных модулях как минимум в 100 раз!
Скорее раз в 10 для 8-биток. Давал ссылку на компилятор си для Амстрада - тот при включении оптимизации даёт код, примерно раз в 8 медленнее лучшего из пока сделанных. И затрат в часах для такого небольшого кода нужно очень немало: уверен, что уважаемый ivagor при случае это подтвердит.
Т.е. в 100 раз?
Да, что-то меня переклинило (цифр в 10 раз больше, считает в 100 раз дольше).
ещё и на этом оптимизируете?!
Подкованные векторовские программисты это знали с самого начала, а после того как в информационном выпуске Вектор-USER была опубликована (в 94 или 95 году) информация по растактовкам это узнали все (в т.ч. и я). Сергей Ермолаев (SES) написал (правда уже после коммерческой смерти вектора, в конце 90х) статью с некоторыми приемами оптимизации под вектор.
уверены, что эмулятор даёт правильную частоту кадров? Все известные мне эмуляторы БК вместо положенных 48.5 Гц упрямо дают 50.
В emu и Virtual Vectore в кадре точно 59904 такта. Если так не сделать, то не будет правильно работать как минимум игрушка exolon (и наверняка некоторые демки, просто навскидку не назову).
Для вектора b2m выдал мне индульгенцию, а я еще распространил её действие и на клоны вектора.
Что-то я не помню, чтобы я где-либо что-либо тебе запрещал. Я мог высказать где-то какое-нибудь скептическое мнение, но запрещать - не было такого. Так что дерзай на здоровье. :)
perestoronin
28.12.2015, 01:48
Скорее раз в 10 для 8-биток. Давал ссылку на компилятор си для Амстрада - тот при включении оптимизации даёт код, примерно раз в 8 медленнее лучшего из пока сделанных. И затрат в часах для такого небольшого кода нужно очень немало:
Затраты в часах можно померить разницей во времени между сообщениями. Так что не правы.
А на счет 100 раз речь шла о переходе с Бейсика на ассемблер для не самого удачного одного и тоже алгоритма. Для Си же разница как между оптимизированной версией на асме и не оптимизированной. Что оптимизация на Си не стала лучше за последние 20 лет, это мне и так давно известно, что говорит в пользу использования ассемблера там, где есть такая необходимость или возможность.
надо сайт какой-то сделать, сохранить коды для Истории.
Есть вики здесь местная. Наполняйте на здоровье. Я прилеплю ссылку на Вашу статью в шапку этой темы.
http://zx-pk.ru/wiki
Что-то я не помню, чтобы я где-либо что-либо тебе запрещал.
Ты не запрещал, а вот я пообещал.
Ты не запрещал, а вот я пообещал.
Просим самую быструю версию под Z80)
первые версии pi32 для вектора показывали что-то в районе "2.25 МГц"
Проверил, поправлюсь - первая версия для вектора соответствовала "эффективной частоте" 2.3 МГц (4.48 сек с тормозами, 3.44 сек без тормозов)
Затраты в часах можно померить разницей во времени между сообщениями.
Время в сутках, а ускорение только в 10-х процентов к малюсенькому коду. И ошибся с числом, по сравнению с С (Z88DK/SDCC_FAST - http://www.z88dk.org/wiki/doku.php?id=temp:front#pi) все усилия по оптимизации дали только 3-х кратный прирост. Оптимизаторы сейчас работают лучше и продолжают улучшаться - откуда 20 лет - загадка. Кто 20 лет назад мог рассчитывать на стабильный 2-х и более кратный прирост скорости от стандартной оптимизации? Тогда ещё память была дорогой - 16 МБ были нормой. В ретропрограммировании без ассемблера почти никак... А вот статья с фактами и про современный ассемблер - http://habrahabr.ru/post/254121/ :)
Просим самую быструю версию под Z80)
Выкладываю версию superbest уважаемого ivagor - остальные пока не перевёл. Перевод на z80 процесс быстрый, минут на 15. Может на днях сделаю и остальные. В коде нужно только заменить функцию печати знака из регистра А (после метки PRC) и вставить при желании учёт времени. На Амстраде время считать поручаю бейсику, который вызывает машинный код как подпрограмму. Адреса загруки нужно ещё соответствующие системе выбрать...
55357
Выкладываю версию superbest уважаемого ivagor - остальные пока не перевёл. Перевод на z80 процесс быстрый, минут на 15. Может на днях сделаю и остальные.
Имеется в виду версия специально оптимизированная под Z80.
litwr, как переводите мнемоники 8080->z80? Раньше я иногда использовал IDA: ассемблируем 8080, IDA->z80. Или вручную, если мало кода.
- - - Добавлено - - -
статья с фактами и про современный ассемблер
Что-то совсем асм загнобили.
perestoronin
28.12.2015, 19:28
Что-то совсем асм загнобили.
И на асме можно таким образом написать программу, что при том же алгоритме она будет медленнее аналогичной программы на Бейсике.
Смею предположить что есть коллеги сильно любящие "Бейсики" и "Жаб" и готовые на любые грязные манипуляции.
Асм, и не только ретро-асм, требует трудолюбия свободного художника, а не фарцовщика - промышленного кодера в финансовых кандалах из юго-восточной Азии с американским тайм-менеджером-надсмоторщиком за проектом, но при этом последние мало что смыслят в творческом подходе к программированию и без давления со стороны клиента-заказчика, и то если правильно составлен договор, и не помышляют о повышении скорости работы своих монстров :)
В результате получаем тормозящие браузеры на java и python, тормозные смартфоны и планшеты и снова на java. А про бизнес-приложения и говорить не приходится, если раньше обходились для этих целей сервером на 486-процессоре, то сейчас схожие задачи уже требуют для "современного" ПО мощностей датацентров, оправдание - якобы аналитики стало больше :)
Интересно, если бы сейчас впервые потребовалось разработать ядерный реактор, предположим что открытие цепной реакции сделали бы именно сейчас, то какой мощности для расчетов машину бы запросили ученые ? Думаю 16Кбайт и 4тыс операций в секунду им было точно мало! А офисные мыши бы не пасьянс раскладывали, а не отходили бы от стоек машины пылающей жаром Ада, а офисные босы бегали бы с коробками ламп и бухгалтерскими счетами под мышкой вместо смартфонов и калькуляторов в кармане каждые 15 минут и не спрашивали бы у мышей чем они сегодня занимались вместо того чтобы трудиться.
blackmirror
28.12.2015, 23:04
В википедии есть очень симпатичный алгоритм (https://en.wikipedia.org/wiki/Gauss%E2%80%93Legendre_algorithm), N=100 цифр можно вычислить за S=6 шагов, а N=1000 за S=9. Из сложных операций на каждом шаге требуется одно умножение и корень. Еще одно умножение и деление нужно чтобы получить Пи, и один корень для инициализации. То есть требуется одно деление, S+1 умножение и S+1 корень. Что касается деления, то его можно заменить умножением на обратную величину вычисляемую по итеративной формуле типа x=x*(2-x*y) за log(N) шагов. Начинать можно с некоторого приближения x0, на каждой итерации количество верных цифр будет удваиваться, полное умножение NxN потребуется только на последнем шаге, а все предыдущие итерации по времени выполнения примерно равны еще одному умножению. То есть финальное деление примерно эквивалентно 4 умножениям. Что касается корней, то 1/корень можно вычислить используя итеративную формулу x=x*(3-x*x*y). Здесь три умножения, добавив еще 1.5 на предыдущие итерации, и 1 чтобы получить корень, получим что корень эквивалентен 5.5 умножениям, в итоге получается что для 100 цифр требуется примерно 50 умножений, а для 1000 примерно 70. Возможно что для деления и корня есть и более простые варианты. Хорошо бы конечно делать умножения методом Карацубы, но 100 и 1000 десятичных цифр занимают не очень круглое количество байт и не факт, что дробление блоков и лишние проверки не дадут фору какому-либо более примитивному алгоритму.
avivanov76
29.12.2015, 15:34
А про бизнес-приложения и говорить не приходится
Помню, как-то сгоряча переписал пару функций из бизнес-логики на асме, благо на Дельфи это легко делалось. Потом проследил всю цепочку вызовов и понял, что сэкономил пару микросекунд, в то время как дальше (не в моем коде) шел SQL запрос, выполнявшийся минимум 50 миллисекунд :)
perestoronin
29.12.2015, 20:35
Никто и не спорит, что сочетая априори две тормозные технологии, к примеру рекурсию и временные таблицы в хранимой процедуре, художник может получить блестяший результат, недостижимый в запросах, которые используют одну из двух обозначенных техник.
Аналогично, могу предположить, и на Бейсиках можно найти такие задачи, которые асму будут не по зубам.
Но у нас то, самая что ни на есть задачка для ассемблеров - расчет числа Пи :)
Для решения этой задачи нам нужно три специалиста: оптимизаторы кода (есть как минимум трое), кодировщики (способные изложить алгоритм в коде, такой пока замечен только один) и математики (способные удачно подбирать, а если повезет то и открывать новые, алгоритмы под конкретные железки).
Ждем помощи математиков.
В википедии есть очень симпатичный алгоритм (https://en.wikipedia.org/wiki/Gauss%E2%80%93Legendre_algorithm), N=100 цифр можно вычислить за S=6 шагов, а N=1000 за S=9.
Ну да, а шаги эти включают работу с числами с плавающей точкой, для 100 знаков минимум 45 байт мантиссы, для 1000 - 450. И при этом, вычисление квадратного корня нужно будет в такой длинный ряд разложить (чтобы была нужная точность), что считаться он будет на 8-ми битках вечность. Реализованные в этой теме алгоритмы использовали лишь 16/32 битные числа.
Потер два предыдущих поста насчет оптимизации деления для z80 и 8085.
В итоге лучший вариант такой: в финальной версии для вектора не трогаем de, а меняем знак самого bc. Фрагменты "jnc DIV0_1\ dad h\ inr l" меняем на adc hl,hl или xchg\ rdel\ xchg. dad d меняем на dad b, а dad b меняем на sbc hl,bc или dsub. Лишнее убираем - древовидность становится не нужна и размер резко сокращается. Также отпадает необходимость в самомодифицирующемся коде (в процедуре деления). Такие версии показывают практически одинаковое быстродействие.
Так а где сам исходник самого быстрого в мире Пи и деления для Z80?)
blackmirror
30.12.2015, 10:35
b2m
Для 1000 цифр хватает мантиссы в 420 байт, если длина мантиссы M, а целая часть в нулевом байте, то при перемножении чисел A и B, можно не перемножать байты A[i] и B[j] если i+j>M, в этом случае из-за неучтённых переносов мы теряем только 3-4 младших байта.
Что касается вычисления X=1/Y, то имея приближение X=1/Y+R, где |R|<2^-n, и сделав итерацию x=x(2-xy), получаем X=(1/Y+R)(2-(1/Y+R)*Y)=(1/Y+R)(1-R*Y)=1/Y-R*R*Y, и если Y<1, то ошибка станет менее 2^-2n, иными словами количество верных цифр удваивается. Если Y>1, то можно на предыдущем шаге обрабатывать не половину цифр, а чуть больше. К примеру использовать умножения 45x45, 23x23, 12x12, 7x7 и так далее. С обратным корнем ситуация аналогичная, только умножений там чуть больше.
Деление 32/16=(16;16) для z80 55380
Легко адаптируется для 8085 - меняем adc hl,hl на xchg\ rdel\ xchg, sbc hl,bc на dsub.
Или для 580ВМ1 - меняем adc hl,hl на cs\ dad h, sbc hl,bc на dsub b.
- - - Добавлено - - -
При необходимости можно еще добавить в начале изменение знака bc.
UPD: заменил архив - добавил "выпавший" adc a,a. У меня эта процедура в программе в мнемониках 8080 (коды z80 в виде .db), команда выпала при переводе мнемоник 8080->z80.
UPD2: ёпрст, вроде НГ не начался, а пришлось еще раз исправлять
- - - Добавлено - - -
Еще вариант для 8085 - 55381
Эту процедуру просто скопировал из программы, ничего не менял, поэтому ошибок сразу нет.
Деление 32/16=(16;16) для z80 55380
А чего там в какой-то предыдущей версии стек использовался, а тут нет?
Если речь про использование dad sp (add hl,sp), то оказалось, что без этого можно обойтись и без sp будет даже быстрее (при данной разрядности).
Для z80 можно с использованием sp апгрейдить эту процедуру до получения 32битного остатка. Младшие байты делимого при этом придется тасовать самомодифицирующимся кодом, как в версии для 8080. Зато можно увеличить и разрядность делимого и довести процедуру, например, до 64/32=(32;32)
С другой стороны для расчета пи в пределах первых тысяч знаков это не особо нужно. Если использовать формулу Гаусса, то хватит даже 16 битных процедур (но вроде знаковых, надо уточнить) для расчета 4000 с чем-то знаков (в этой теме про это упоминал).
- - - Добавлено - - -
но вроде знаковых, надо уточнить
Уточнил - достаточно беззнакового деления и умножения.
Удалось постигнуть некоторые рецепты оптимизации от уважаемого ivagor и всё заработало побыстрее. Конечно, вычесть быстрее, чем умножить. :) Собрал такие данные для 100, 1000 и 3000 цифр.
Commodore 64/PAL - 4.03 - 393.5 - 3527
Commodore 128/PAL - 2.2 - 208.6 - 1868
Commodore +4/PAL - 1.92 - 183.3 - 1641
Amstrad CPC6128 - 2.65 - 218.4 - 1934
Всё выложил на сайте - http://litwr2.atspace.eu/retropc.html
Версий для БК не правил - никто не тестирует. Версия для первых IBM PC совместимых вроде бы в руках уважаемого ivagor?
Попробовал версию treediv на Амстраде: 2.89 и 264.9 на 100 и 1000. Опять поражает разница по 100 и 1000. В первом случае Амстрад быстрее всего на 9%, а во втором на 21. По частоте Амстрад быстрее (если считать частоту Вектора 2.33) на 37% и ещё нужно надбавить процентов 5-10 за большую скорость LD и INC. Есть ещё неизученные рецепты. :)
Версия final_precise, если правильно понял, требует более 40 КБ непрерывной памяти - на Амстраде в бейсике такое без головной боли не сделаешь - надо в CP/M.
Заметил разницу в скорости, если печатать не с первой строки, т.е. со скроллингом. На Амстраде (нет текстового режима) до 3%, на Коммодоре - менее одного.
специально оптимизированная под Z80
Непонятно. Выложил один из лучших кодов для z80 и нужно ещё что-то? Оптимизацию - это к уважаемуму ivagor-y. Версию treediv для z80, как понял, выкладывать не надо. Где же данные по Спектруму?
как переводите мнемоники 8080->z80
Нашел в сети awk-сценарий (http://www.hytherion.com/beattidp/comput/z80cpm.htm) - он всё и делает. Только там беда с плюсами. Поэтому их сначала нужно заменить, например, на @, а потом обратно. Ещё почему-то sbb не воспринимает.
Деление 32/16=(16;16) для z80
На Амстраде JR быстрее JP. Но код очень впечатляет, собираюсь выложить его на профильной википедии. Эту версию DIV320 гораздо труднее приспособить для работы с любым BC. В прежней достаточно было поставить JR C, а теперь простого способа совсем не видно. Нужно указывать, что работает только если BC < $8000.
И на асме можно таким образом написать программу, что при том же алгоритме она будет медленнее аналогичной программы на Бейсике.
Ну это будет что-то почти невероятное. :)
Удалось постигнуть некоторые рецепты оптимизации от уважаемого ivagor и всё заработало побыстрее.
...
Версий для БК не правил - никто не тестирует.
Я бы на живых процессорах потестировал, скоро и до собственно БК надеюсь добраться.
Нашел в сети awk-сценарий
Круто, спасибо, работает!
вычесть быстрее, чем умножить.
?
На Амстраде JR быстрее JP
Без тормозов в среднем условный jr скорее всего тоже будет быстрее jp, это я не додумал.
Ещё почему-то sbb не воспринимает
Насколько вижу он просто забыл про sbb и не преобразует его.
Commodore +4/PAL - 1.92
Ага, теперь быстрее 2 сек
Amstrad CPC6128 - 2.65
Вектор с z80 и 6128 с вышеприведенной процедурой считают быстрее 2.5 сек, т.ч. определенно есть простор для оптимизации
perestoronin
30.12.2015, 21:37
что-то почти невероятное.
Невероятно виртуальным может может указание города под Москвой и использование как домашнего сайта, сайта в доменной зоне ЕС, а остальное в очумелых руках вполне себе более "невероятное" (вполне себе в реальности).
PS .Почему бы учебник по верстке и рекомендациям по эргономике сайтов не поковырять в перерывах между генерацией аналитики по ретро-железу?
Пытался найти на сайте программки имеющие отношение к числу Пи, оказалось это не простой задачей с такой эргономикой и версткой. Может попроще можно сделать сайт и подобрать картинку для фона ?
blackmirror
31.12.2015, 02:14
Код вполне можно адаптировать и для других архитектур, требуются только ADD/ADC и условные переходы в зависимости от знака, переходы можно сделать и по флагу переноса, чуть сместив команды и метки. На входе BC - делитель меньше чем 0x8000, в регистрах HLA - делимое, которое должно быть меньше 256*BC, на выходе в HL будет остаток, а в A будет очередной байт частного, его можно сохранить и загрузить следующий чтобы продолжить деление. Делитель можно сделать и до 0xFFFF, но тогда полученный байт нужно конвертировать по таблице из 256 элементов.
#define ADD(a,b) do{a+=(M&b); C=(a>>8)&1; S=(a>>7)&1; a&=M;}while(0)
#define ADC(a,b) do{a+=(M&b)+C; C=(a>>8)&1; S=(a>>7)&1; a&=M;}while(0)
void div_8(int &hl, int &a, int &bc){
const int M=255;//такая маска чтобы не плодить макросов, hl и a могут быть разной разрядности
int de=-bc&M;//для замены тормозного вычитания сложением
int C=0,S=0;//флаги переноса и знака
ADC(a,a); ADC(hl,hl); ADD(hl,de); if(S) goto A1;
S1: ADC(a,a); ADC(hl,hl); ADD(hl,de); if(S) goto A2;
S2: ADC(a,a); ADC(hl,hl); ADD(hl,de); if(S) goto A3;
S3: ADC(a,a); ADC(hl,hl); ADD(hl,de); if(S) goto A4;
S4: ADC(a,a); ADC(hl,hl); ADD(hl,de); if(S) goto A5;
S5: ADC(a,a); ADC(hl,hl); ADD(hl,de); if(S) goto A6;
S6: ADC(a,a); ADC(hl,hl); ADD(hl,de); if(S) goto A7;
S7: ADC(a,a); ADC(hl,hl); ADD(hl,de); if(S) goto A8;
S8: ADC(a,a);
return;
A1: ADC(a,a); ADC(hl,hl); ADD(hl,bc); if(!S) goto S2;
A2: ADC(a,a); ADC(hl,hl); ADD(hl,bc); if(!S) goto S3;
A3: ADC(a,a); ADC(hl,hl); ADD(hl,bc); if(!S) goto S4;
A4: ADC(a,a); ADC(hl,hl); ADD(hl,bc); if(!S) goto S5;
A5: ADC(a,a); ADC(hl,hl); ADD(hl,bc); if(!S) goto S6;
A6: ADC(a,a); ADC(hl,hl); ADD(hl,bc); if(!S) goto S7;
A7: ADC(a,a); ADC(hl,hl); ADD(hl,bc); if(!S) goto S8;
A8: ADC(a,a); ADD(hl,bc);
return;
}
blackmirror, круто!
переходы можно сделать и по флагу переноса, чуть сместив команды и метки
Даже не нужно ничего смещать
- - - Добавлено - - -
для замены тормозного вычитания сложением
У 8085 и 580ВМ1 вычитание не тормозное и с учетом того, что отпадает необходимость менять знак bc и становится не нужен самомодифицирующийся код для тасовки младших байт делимого получается быстрее, несмотря на то, что в ветках S перед adc a пришлось добавить stc. Сейчас в pi32 8085 догнал z80 (для 100 цифр, на 1000 все же z80 быстрее на 1 сек), по крайней мере с учетом векторовского торможения для обоих.
Пока нормальные люди отдыхают, некоторые занимаются всякими странными делами
5539555396
100 - 2.8168 сек
1000 - 286.8624 сек - 4 мин 46.8624 сек
Часть меток в процедуре деления можно было убрать и заменить в командах переходов, но я поленился, т.к. на скорость это не влияет.
perestoronin
01.01.2016, 11:31
100 - 2.8168 секСразу не заметил, рекорд ставится с использованием такого инструмента как:
tasm -b -85 pi32.asmХотел бы уточнить, а где этот инструмент можно скачать ?
На странице http://www.z80.info/z80sdt.htm есть расшифровка аббревиатуры tasm как:
TASM table driven assembler Can assemble Z80 and a lot of other CPUs Ссылка на сборку под PC на той странице уже давно не актуальная :(
Хотел спросить, может и исходники этого tasm где-то выложены?
Также по тегу tasm нашел такой инструмент как http://metasm.cr0.org/
https://code.google.com/p/metasm/source/browse/
Кто-то уже пробовал его использовать? Как я понял его можно уставить и на сайт и использовать в онлайн для компиляции программ, он интегрируется с хипстерским ruby (https://www.ruby-lang.org/ru/), что немаловажно, чтобы заинтересовать "свежую кровь" ретрожелезками. Попробую у себя где-нибудь развернуть.
Когда у меня недавно были проблемы с архивным десктопом, тоже искал tasm32 (https://yadi.sk/d/2YShg5pGmcvDm) - и не нашел. Про исходники не знаю.
perestoronin
01.01.2016, 11:47
тоже искал tasm32 - и не нашел
Благодарю, действительно table driven, сюда по компонентам.
Правильное наименование TASM - the Telemark Assembler
и по такому ключу находится у калькуляторщиков http://www.ticalc.org/archives/files/fileinfo/250/25051.html
А также
http://old-dos.ru/files/file_1385.html
А здесь есть страничка с документацией онлайн
http://www.cpcalive.com/docs/TASMMAN.HTM
Также нашел полную версию документации в pdf (http://www.s100computers.com/Software%20Folder/6502%20Monitor/The%20Telemark%20Assembler%20Manual.pdf).
Эта pdf спрятана на сайте проекта sl100 (http://www.s100computers.com/Software%20Index%20Page.htm). На заметку, в состав борды SL100 входят модули и на Z80 и на 8080.
Сказано что кроме DOS версии, есть еще и Linux сборка, а возможно и даже и исходники. Никому не попадались ?
А здесь сказано, что был далее использован в новых разработках:
http://tistory.wikidot.com/tasm
In the early days of the TI community, TASM was the most popular assembler that was used by Z80 assembly programmers.
Later it was superceded by IDE's such as Assembly Studio 8x and SPASM, however in some cases it is still used to this day.
Assembly Studio 8x:
описание
http://tistory.wikidot.com/assembly-studio-8x
Assembly Studio 8x v4.0
A full featured Win32 assembler and IDE for z80 calculator
а скачать дистрибутив можно по другой ссылке
http://www.ticalc.org/archives/files/fileinfo/158/15892.html
Есть контакты автора Jeremy Goetsch (
[email protected])
Проект судя по всему заброшен, вместе с доменом acz.org, может кто уже сталкивался с этим проектом и выпрашивал исходники у автора?
SPASM:
SPASM-ng is a z80 assembler with extra features to support development for TI calculators.
https://github.com/alberthdev/spasm-ng
Попутно откопал такое ретро-чудо, но уже для IBM360:
http://www.jaymoseley.com/hercules/compilers/spasm.htm
Пусть этот оффтопик побудет некоторое время в этой теме, позже его уберу в копилку знаний http://zx-pk.ru/wiki, кто-то же должен её пополнять :).
А здесь еще масса ретро-инструментов для ретро-процессоров упоминается, жаль что отчасти с битыми ссылками:
http://wiki.nesdev.com/w/index.php/Tools
ass (шутники) по картинке понравился, но увы есть отличия в синтаксисе от tasm и справка в 7ке не смотрится.
А здесь есть страничка с документацией онлайн
Этот файл есть в архиве
perestoronin
01.01.2016, 13:49
Этот файл есть в архиве
Благодарю, все еще в поиске исходника tasm или хотя бы linux версии, на данный момент нашел вот такой архив, в нем есть документация в pdf по программированию для процессора 6502, думаю может быть полезна для тех, кто разрабатывает версию программы расчета числа Пи под процессор 6502 (NES, Агаты, Анюша, Apple 1).
Левенталь 6502 Подпрограммы на ассемблере (книга на английском). (http://www.s100computers.com/Software%20Folder/6502%20Monitor/6502%20Assembler.zip)
в том же архиве находится и сам tasm 3.2, но с таблицей только для 6502.
Подумалось, что наверное не так сложно будет мне расковырять tasm с целью получить fork в исходниках, а сами таблички-то просто текстовые файлы, их можно использовать будет без изменений в авторской редакции.
tasm мега компилятор с ассемблера, и сразу под массу процессоров, среди которых есть почти все нужные нам ретро-процессоры.
Не представляется сложным написать самим таблички под какие-то другие более экзотичные процессоры :), для этого и программирование даже знать и не нужно :)
Не особенно тщательно искал но на той же страничке проекта много чего выложено (http://www.s100computers.com/Software%20Folder/Assembler%20Collection/Assembler%20Collection.htm), может еще что-то найдется в тех архивах уникальное, как к примеру выше упомянутая версия книги Левенталя для 6502, дайте знать и мне.
Ждем теперь оптимизированную версию расчета чиста Пи по неоптимальному алгоритму и для процессора 6502 ;)
blackmirror
01.01.2016, 14:19
Пока нормальные люди отдыхают, некоторые занимаются всякими странными делами
100 - 2.8168 сек
1000 - 286.8624 сек - 4 мин 46.8624 сек
Как вижу, деление работает с любым делителем до 2^16, это действительно необходимо? Уменьшение диапазона в два раза позволит выкинуть половину кода, а из оставшейся половину условных переходов. Вроде бы алгоритму "краника" деления на числа до 2^15 хватает для вычисления 4930 десятичных знаков.
Ждем теперь оптимизированную версию расчета чиста Пи по неоптимальному алгоритму и для процессора 6502
Судя по времени работы текущая версия litwr весьма оптимизирована:
Собрал такие данные для 100, 1000 и 3000 цифр.
Commodore 64/PAL - 4.03 - 393.5 - 3527
Commodore 128/PAL - 2.2 - 208.6 - 1868
Commodore +4/PAL - 1.92 - 183.3 - 1641
Не представляется сложным написать самим таблички под какие-то другие более экзотичные процессоры
Это большой плюс tasma, который перевешивает (для меня) его недостатки.
- - - Добавлено - - -
Как вижу, деление работает с любым делителем до 2^16, это действительно необходимо?
Да, старший бит делителя бывает единичным. Диапазоны чисел я проверял, в умножении учет диапазона хорошо помог, а в делении, к сожалению, нет.
Уменьшение диапазона в два раза позволит выкинуть половину кода, а из оставшейся половину условных переходов.
? Не могу сообразить, за счет чего можно выкинуть половину кода при уменьшении диапазона в два раза. На каждый бит делимого приходится 8 строк.
- - - Добавлено - - -
Вроде бы алгоритму "краника" деления на числа до 2^15 хватает для вычисления 4930 десятичных знаков.
Это Вы наверно про исходный, а здесь то "4х циферный"
perestoronin
01.01.2016, 15:14
весьма оптимизирована
весьма вероятно что это так, но цифры уж очень близки к версии для 8080, поэтому думаю что это именно весьма неоптимизированная версия, при равной частоте с 8080, должна получаться версия быстрее для 6502.
а здесь то "4х циферный"
память можно рассматривать и как массив байт и как массив бит, другое дело что обращение к памяти как к массиву бит потребует накладных расходов, тут нужно внимательно смотреть сколько выигрываем и сколько проиграем в производительности и объеме памяти.
В дополнение старый список инструментов для компиляции программ под ретропроцессоры
http://www.z80.info/z80sdt.htm
все еще в поиске исходника tasm
увы ни исходника tasm, ни версию для linux, я не нашел, но зато нашел другой ассемблер и тоже управляемый таблицами и причем с исходными кодами самого ассемблера:
http://www.penguin.cz/~niki/tdasm/
думаю будет полезен и для Z80, тем более что таблица (хотя и неполная) для z80 прилагается, а полные таблицы и отсутствующие таблички можно попробовать портировать для tdasm из архива tasm, но форматы таблиц различны.
PS. В целом мне кажется tdasm не дотягивает до уровня tasm, поэтому ищу исходники или версию tasm под linux дальше.
еще наткнулся на vasm, тоже достоен внимания http://sun.hasenbraten.de/vasm/index.php?view=relsrc
blackmirror
01.01.2016, 15:35
? Не могу сообразить, за счет чего можно выкинуть половину кода при уменьшении диапазона в два раза. На каждый бит делителя приходится 4 строки.
Мой код (http://zx-pk.ru/showthread.php?t=25783&page=20&p=849059&viewfull=1#post849059) начинает работать с R<B, и на каждом шаге остаток удваивается с добавлением очередного бита делимого, после чего к нему либо прибавляется либо вычитается B, чтобы |R| оставался меньше B, а далее можно обрабатывать следующий бит. Если B<2^15, то |R|<2^15 на каждом шаге, и после удвоения переполнения произойти не может, а условный переход требуется только чтобы отследить момент, когда сложение с B нужно заменить вычитанием. А вот если |R|>=2^15, то здесь требуется дополнительное ветвление, чтобы правильно отследить знак после добавления/вычитания B.
В версии для 8080 "удвоенное" количество кода вызвано отсутствием команды HL=HL+RP+флаг переноса. В вариантах для 8085 и z80 код почти как у Вас, только с переходами по переносу, а не знаку.
- - - Добавлено - - -
На каждый бит делителя приходится 8 строк.
Поправлюсь - на каждый бит делимого
- - - Добавлено - - -
Да, старший бит делителя бывает единичным.
Уф, это я опять про делимое, а не про делитель. Максимальный делитель для 1000 - 6999, для 100 - 699. Не думаю, что это можно использовать для сокращения процедуры при расчете 1000 или 100 цифр. Вот если бы делимое, которое я как раз имел в виду, тогда другое дело.
Хотел бы уточнить, а где этот инструмент можно скачать ?
Я скачивал с официальной странички, сейчас уже не открывается, но есть в веб-архиве (http://web.archive.org/web/20150906070146/http://home.comcast.net/~tasm/).
perestoronin
01.01.2016, 16:28
сейчас уже не открывается
а другие на ретро-железках еще и деньги зарабатывают, с каждой копии своей программы по 100 сантиков:
http://www.cdadapter.com/cross32.htm
Вот нам и Licensing Best Practices (http://eu.wiley.com/WileyCDA/WileyTitle/productCd-0471740675.html) в действии.
blackmirror
01.01.2016, 23:46
В версии для 8080 "удвоенное" количество кода вызвано отсутствием команды HL=HL+RP+флаг переноса.
8080 гадость конечно редкостная, но даже для него с делением не всё так плохо:
#define ADC8(a,b) do{a=(a&255)+(b&255)+C; C=a>>8; a&=255;}while(0)
#define ADD16(a,b) do{a=(a&65535)+(b&65535); C=a>>16; a&=65535;}while(0)
//BC - делитель, должен быть в диапазоне от 256 до 32768
//DE = -BC
//HL < BC - старшие два байта делимого
//SP - младший байт делимого расширенный нулём
//A - частное
//деление производится по формуле A=HL*256/BC; HL=HL*256%BC; HL+=SP; if(HL>=BC) {HL-=BC; ++A;}
void div_8080(int &hl, int &a, int &bc){
int sp=a;
int de=-bc;
int C=0;
ADD16(hl,hl); ADD16(hl,de); if(!C) goto A1;
S1: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A2;
S2: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A3;
S3: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A4;
S4: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A5;
S5: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A6;
S6: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A7;
S7: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A8;
S8: ADC8(a,a); ADD16(hl,sp); ADD16(hl,de); if(!C) goto A9;
S9: ADC8(a,0);
return;
A1: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S2;
A2: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S3;
A3: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S4;
A4: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S5;
A5: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S6;
A6: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S7;
A7: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S8;
A8: ADC8(a,a); ADD16(hl,sp); if(C) goto S9;
A9: ADD16(hl,bc);
return;
}
Народ на лимонном форуме протестировали версию для Коммодора 64 с разными 8085 и 580ВМ1 :) или, точнее, с Хамелеоном и Суперпроцесором (SuperCPU довольно массовая приставка для означенного Коммодора, эмулируется в Vice). Результаты от 16 до 22 раз быстрее Коммодора 64. Это даже Вектору с Турбо+ многовато. Там ещё обозначилась тема не вполне точной эмуляции ускоряющих приставок.
Кстати, для интересующихся z80 самый быстрый относительно массовый компьютер на его основе - это SAM Coupé с z80 на 6 MHz, выпускавшийся с 1989 (!). Хотя сэр Синклер вроде собирался новый Спектрум сделать на 8 МГц, но "переспешил" на "квантовом скачке" с QL и сдал хозяйство консервативному Амстраду. Амстрад в 1992 сделал что-то на z80 c 16 Мгц, но в единичных экземплярах.
blackmirror, интересный вариант, но 100 цифр с ним считается медленнее, а 1000 с той же скоростью, как здесь (http://zx-pk.ru/showthread.php?t=25783&p=849193&viewfull=1#post849193). Это без sp, с ним еще медленнее, плюс сложность с подсчетом времени. Возможно моя реализация была недостаточно эффективна и кто-нибудь сильнее раскроет потенциал этого варианта.
Результаты от 16 до 22 раз быстрее Коммодора 64. Это даже Вектору с Турбо+ многовато.
Тогда я бы сравнил реализации на ПЛИС, думаю 6502 будет быстрее максимум раза в 2.
- - - Добавлено - - -
Кстати, для интересующихся z80 самый быстрый относительно массовый компьютер на его основе - это SAM Coupé с z80 на 6 MHz
Если уж сравнивать с 65816, то и на стороне z80 пусть играет r800 в MSX Turbo R.
- - - Добавлено - - -
100 цифр с ним считается медленнее, а 1000 с той же скоростью
Маленько оптимизировал, теперь 100 считаются с той же скоростью, а 1000 цифр на 5 секунд быстрее - неплохо.
- - - Добавлено - - -
Добавил ветку для делителя<128 - 100 цифр стало быстрее на 0.06 сек, 1000 цифр - еще на 0.6 секунды (т.е. в сумме по сравнению с выложенной версией почти на 6 сек).
blackmirror
02.01.2016, 13:07
ivagor, вообще можно не тащить младший байт в процедуру деления, а добавить его уже после выхода, грузить можно самомодифицируемыми командами LXI, потому что после умножения наверно не сильно принципиально, куда сохранять два младших байта, ну а чтобы проще было проверить, не нужно ли после сложения править частное/остаток, процедуру деления можно чуть изменить, чтобы она работала с отрицательными остатками.
#define ADC8(a,b) do{a=(a&255)+(b&255)+C; C=a>>8; a&=255;}while(0)
#define ADD16(a,b) do{a=(a&65535)+(b&65535); C=a>>16; a&=65535;}while(0)
//вход:
//BC - делитель, должен быть в диапазоне от 256 до 32768
//DE = -BC
//HL - два байта делимого минус BC, |HL+BC|<BC
//выход:
//A - HL*256/BC
//HL - HL*256%BC-BC
void div_8080(int &a,int &bc, int &de,int &hl){
int C=0;
ADD16(hl,hl); ADD16(hl,bc); if(C) goto S1;
A1: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S2;
A2: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S3;
A3: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S4;
A4: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S5;
A5: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S6;
A6: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S7;
A7: ADC8(a,a); ADD16(hl,hl); ADD16(hl,bc); if(C) goto S8;
A8: ADC8(a,a);
return;
S1: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A2;
S2: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A3;
S3: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A4;
S4: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A5;
S5: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A6;
S6: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A7;
S7: ADC8(a,a); ADD16(hl,hl); ADD16(hl,de); if(!C) goto A8;
S8: ADC8(a,a); ADD16(hl,de);
return;
}
//bb делитель от 256 до 32768
//aa - делимое, aa<65536*bb
void div_32_16(int aa, int bb){
int a,bc,de,hl,C;
hl=aa>>16;//старшие два байта делимого
bc=bb;//делитель
de=-bb&0xFFFF;//-делитель
ADD16(hl,de);//корректируем старшие два байта, потому что деление работает с отрицательным остатком
div_8080(a,bc,de,hl);//делим 256*HL на BC
//PUSH BC
bc=(aa>>8)&255; //перед делением модифицируем данную команду LXI, чтобы загрузить предпоследний байт делимого
ADD16(hl,bc); //суммируем предпоследний байт делимого с остатком
bc=bb;//POP BC
if(C){//если остаток стал положительным, то корректируем остаток и старший байт частного
ADD16(hl,de);
++a;
}
printf("%3X",a);//старший байт частного
div_8080(a,bc,de,hl);//делим дальше
de=aa&255;//перед делением модифицируем данную команду LXI, чтобы загрузить младший байт делимого
ADD16(hl,de);//суммируем младший байт делимого с остатком
if(C)//если стал положительным, то корректируем младший байт частного, иначе корректируем остаток
++a;
else
ADD16(hl,bc);
printf("%02X",a);
printf("%4X",hl);
}
грузить можно самомодифицируемыми командами LXI
Я так и сделал. Но я сейчас складываю внутри, на "после" может потом переделаю. Сейчас тяжеловесно выглядит ветка для 127<делителя<256, может для нее что-нибудь придумаю.
blackmirror
02.01.2016, 14:24
Сейчас тяжеловесно выглядит ветка для 127<делителя<256, может для нее что-нибудь придумаю.
Там похоже без удвоения разрядности никак, то есть в BC придётся грузить делитель*128, начинать не с удвоения HL, а с вычитания, ну а в конец добавить удвоение HL, чтобы весь остаток оказался в H, в A мы получим байт частного, а в L нужно загрузить следующий байт делимого.
на стороне z80 пусть играет r800 в MSX Turbo R.
Вы и это в Вектор вставите? :):):)
Кстати, Хамелеон это именно ПЛИС и возможно лучший из существующих эмулятор такого рода - рекомендую посмотреть, позавидовать. :)
Перенёс final_precise на СР/М на Амстраде (55411) и результаты получились странные: 100 цифр за 2.81 (2.98 - ваши данные), 1000 цифр за 253.9 (299) - это на 100 цифрах получается Амстрад быстрее на тех же кодах только на 6%, что делает эффективную частоту Bектора чуть-чуть большей 3 МГц... Хотя возможно нашёл объяснение: торможение BDOS - вы вместо него используете что-то побыстрее. Без печати Амстрад делает 100 цифр за 2.49, а 1000 за 250. С такими таймингами Амстрад стабильно на 19% быстрее по 100 и 1000 цифрам, что тактирует Вектор в 2.68 МГц!
Получается, что на 100 цифрах на 15% сравнивается скорость печати символов на экран. С ростом скорости основного алгоритма эта доля будет расти... Уже писал об этом - кажется, что такая оптимизация не есть что-то правильное... Интересно бы данные по Корвету получить, Микроше и т.п.
Раньше время измерялось из бейсика и поэтому в данных по Амстраду учитывалось и время построения таблиц, но это примерно полсекунды в final_precise, влияет только на результаты по 100 цифрам. И повторю вопрос. Почему не класть таблицы готовыми? При загрузке система сразу определит хватает ли ей памяти... И тестировать проще и вам меньше кода носить.
A коды интересные: штучки вроде check - это даже слов не нахожу - прямо пимания какая-то. :)
Перенёс final_precise на СР/М на Амстраде (final-precise-z80.zip) и результаты получились странные
Вполне возможно, что тормозит вывод на экран. В векторовских cp/mах эта проблема есть, поэтому я и сделал стэндэлон.
Почему не класть таблицы готовыми?
Просто лень.
В векторовских cp/mах эта проблема есть, поэтому я и сделал стэндэлон.
Как видите проблема есть не только у Вектора. Без такого, что вы сделали с кодом, мы могли бы сравнивать разные системы. Например, Корвет мог бы быть быстрее на 100 цифрах, но медленнее на 1000. Это бы реально отражало архитектурные особенности компьютеров, а не трудовое усердие энтузиастов.
Уважаемый perestoronin, на лимонном форуме (http://www.lemon64.com/forum/viewtopic.php?t=58674&postdays=0&postorder=asc&start=24) выложены данные по железному самому быстрому Коммодору в сравнении с программой на си.
perestoronin
03.01.2016, 05:59
мог бы быть быстрее на 100 цифрах, но медленнее на 1000.
Предлагаю ограничиться, пока не пройдем барьер 1сек, для КР580ВМ80А на его штатных частотах, 100 цифрами, а 1000 приводим справочно, по желанию, и лишь для тех архитектур и алгоритмов, которые уже преодолели 1 с. Для остальных случаев остановимся на глубокой оптимизации для лишь для 100 цифр.
То, что прислушались к совету вынести вывод результата в отдельный код, отдельно от кода расчета, благодарствую и приветствую, так значительно легче сравнивать и искать причину деградации скорости расчета в сравнении с предыдущими предложенными вариантами.
в сравнении с программой на си.
Это не интересно, Си заведомо в невыгодной позиции, думаю это должно быть уже давно очевидно быть. На Си быстрее кодить в продакшн, когда работа должна быть завершена еще вчера, но создавать шедевры, доступные лишь свободному художнику, на Си сложнее, чем на ассемблере, если вообще возможен шедевр на Си. Я знаю лишь один пример шедевра на Си - веб-сервер nginx (http://nginx.org/ru/), остальное всё - изделия для "продакшн", пускай даже и с лейблой СПО.
на лимонном форуме
Кто бы потрудился из знатоков Коммодоров и еже с ними Хамелеонов, смог проинтерпретировать те расчеты? А также привести подробности того самого расхваливаемого Хамелеона, разрядность этого сопроцессорного блока на ПЛИС (если я правильно понял) и его тактовую частоту.
Можно краткую выжимку сюда запостить, как ранее делали, 100 знаков (на такой то машине столько-то 0,00хх сек, с ускорителем Хамелеон столько то ..., Хамелеон разрядность хх бит, частота хх МГц, команды умножения такие-то, столько-то тактов) ?
Конечно любопытно знать, что кроме 1801ВМ1 и 580ВМ80 что-то еще существует, но нам бы в первую очередь доступное железо прогнуть нужно ;)
Хотя думаю в Евросоюзах наверное Коммодоры достаются за "500р", а то и вовсе за 10 рублей как в России в Митино процессоры КР580ВМ80А ? Впрочем можно и к ретро-машине соорудить приставочку на ПЛИС и на мощном ARM-процессоре и похвалиться какие мы молодцы, только зачем ? Пока в этом не вижу необходимости, есть запас и без сопроцессоров для достижения новых рекордов, до 1 сек "еще далеко".
Также не понятно зачем в той теме прикрывают расчёт чисел числа Пи заголовком "демо", вместо нормального названия. Чего стесняются ?
Мое мнение насчет разделения расчета и вывода на экран - это нормально только для расчета 100 цифр. Несколько секунд можно и подождать, когда казалось бы ничего не происходит. А для 1000 цифр это уже не здорово. Насколько помню, litwr писал нечто похожее, т.е. я фактически присоединяюсь к его мнению по этому вопросу.
Можно сделать версию для cp/m, но не знаю универсального способа подсчета времени, разве что поручить это "оператору" с секундомером.
Насчет быстродействия реализаций на ПЛИС - v06cc svofski в максимальном разгоне, который мне удался на DE1, работал примерно в 12 раз быстрее стандартного вектора. Для DE1-SoC и DE2-115 можно сделать и побыстрее, да и для DE1 предел не достигнут, но оказалось, что на векторе практически нет программ, которым нужно такое быстродействие.
оптимизации для лишь для 100 цифр
Мелко как-то, даже Командор 64 с текущим алгоритмом почти 5000 знаков может считать. Это машина класса Вектора.
Что-то вы странное про си написали. На нём библиотеки пишут для всяких питонов и сами питоны. На ассемблере тольку управление памятью и ввод-вывод с железом.
Данные для SuperCPU - довольно массовой (10-и тысяч) приставки из 90-х. А Хамелеон это продолжение разработки уже почти легендарной компьютерной девушки Джерри - это уже 21 век, разработка продолжается. Можно воткнуть в C64, а можно в него воткнуть usb-клавиатуру.- https://icomp.de/shop-icomp/en/produkt-details/product/Turbo_Chameleon_64.html
Мое мнение насчет разделения расчета и вывода на экран - это нормально только для расчета 100 цифр.
Таким мнением вы внесли в тему политику, поиск преференций для выбранной платформы. :(
Можно сделать версию для cp/m
Уже выложил такую для final-precise. А универсального способа работы с таймером в ср/м нет, нужно подстраиваться под каждый случай. В выложенной версии используются обращения к фирменным ROM-вызовам.
Таким мнением вы внесли в тему политику
Непротрезвел что-ли? Какая тут политика? Совсем обалдели...
perestoronin
03.01.2016, 14:59
Непротрезвел
До 10го мало кто из коллег будет трезвым (я не в счет, т.к. "его" не пью), не пьют лишь только убежденные трезвенники и язвенники. Но среди непьющих % в последние годы выше тех, кто не пьёт по убеждению и это не может не радовать меня.
А на счет преференций, так оно так все и делается, нужно продвигать отечественную продукцию, а её в Митино очень много :) и не дороже чем по 30 руб за микросхему КР580ВМ80А.
Зачем нам Коммодоры и Эпплы 1, когда у нас и КР580ВМ80А не до конца прокачан :) ? Не у всех есть лишние ресурсы по времени чтобы заниматься сразу несколькими архитектурами, да и не всем оно по большому счету нужно. Но это не значит что нам не интересно что творится в плане войны с числом Пи у них там, интересны сводки с фронта Коммодора и Эппла, но желательно не отсыл на сайты с ихними кракозябрами, которые даже гуглопереводчик не может правильно и понятно перевести, а выжимки сюда в тему с циферками на русском языке, для простоты можно присылать краткое описание новизны алгоритмов и достигнутые улучшения подкрепленные полученными сек за 100 знаков.
100 знаков нам пока за глаза достаточно для начала опытов и поиска решения позволяющего перешагнуть за 1 сек для 100 знаков числа Пи на КР580ВМ80А при его штатных частотах (без разгона).
5541955420
100 - 2.7568 сек
1000 - 280.9320 сек - 4 мин 40.9320 сек
perestoronin
03.01.2016, 22:10
почти 5000 знаков может считать
А Phenom то может посчитать сколько циферок! Главное чтобы места на жестком диске в 4Тбайта для результата было :)
А теперь вернемся к нашим баранам, т.е. к 100 циферкам и удобному, для поиска слабых мест в примитивных алгоритмах, процессору КР580ВМ80А, коих полно у каждого, не то, что экзотичные в наших краях иностранцы, интересно коим боком их заносит под Москву ? Ну не каждому дано владеть разными машинками Тюринга и Поста.
Технарям попроще ставить эксперименты именно на простых процессорах - типа проверенных временем и к тому же по прежнему доступных КР580ВМ80А и КР1858ВМ*.
Но за циферки все равно спасибо, впрочем и за Си с Бейсиками тоже. Вот еще бы кто на Форте поупражнялся в скорости расчета числа Пи ;)
blackmirror
04.01.2016, 12:53
Если spigot'а перевернуть, то есть внутренним циклом проходить по переносам(от старших к младшим), а внешним по множителям/делителям(в убывающем направлении), то понадобится только массив переносов. При вычислении по 4 цифры переносы будут меньше 10000*2, и хранить потребуется 1000/4*2=500 байт. На каждой итерации внешнего цикла можно сгенерировать оптимальный код для внутреннего, поскольку там требуется только умножение/деление на константу. Вычислений здесь меньше конечно не станет, но не понадобится делать CALL/RET, насиловать стек, да и искать процедуру по таблице. После завершения внешнего цикла, нужно еще раз пройтись по переносам, приводя их к диапазону до 10000, и увеличивая соседний если нужно. Никаких "недействительных" цифр здесь не будет, если двигаться от младших к старшим. Если сделать процедуры умножения/деления 16x24->40, 40/24->16_24, то можно будет вычислять хоть 100К цифр, сейчас это конечно смысла не имеет, но 20 лет назад вычислить 100К цифр при 64К памяти было бы неплохо, пусть даже и за несколько месяцев.
55424
Сумма вычисляется по формуле s=s*10000+p[i]*a, затем это делится на b. Поскольку a и b во внутреннем цикле можно считать константами, то возможно получится одновременно умножать на 10000 и делить на b, не вылезая за пределы 16 бит. По крайнем мере в той ветви алгоритма где делитель прибавляется, можно сначала добавить множитель, и если результат станет положительным, значит на данном шаге делитель нужно вычитать. Оптимизация здесь возможна за счёт того, что сдвиг суммы станет общим для умножения и деления, и вроде как не потребуется подгружать младшие байты для следующих итераций. А вот про p[i] можно сразу сказать, что частное будет равно 0, поскольку a<b, и вычислять нужно только остаток. Но эти идеи еще нуждаются в проверке.
Интересный подход. Если честно - я не осмыслил, как это работает, но попробовал. Выложенный вариант начиная с 4934 цифры считает неправильно (последние правильные цифры - 3096, потом д.б. 3408).
blackmirror
04.01.2016, 15:15
ivagor, это я неправильно константы объявил, должно быть:
// const unsigned D=4,N=4936u,M=2*N*3322u/1000u;
const unsigned D=4, M=32767u, N=M/2*1001u/3322u;
сначала M было максимальным множителем, потом решил что для делителя нагляднее какой точности нужны процедуры умножения/деление, а константы переделать забыл. Вообще количество итераций внешнего цикла примерно равно требуемой длине в битах, если её умножить на lg(2), то как раз получается количество цифр. Остатки которые нужно хранить в массиве не превышают 2*10^n, где n - количество цифр в блоке. Ну а сумма перед делением может в M раз быть больше чем остаток. То есть 2*M*10^n должно влезать в сумму без переполнения. Если сумма 32 разряда, то считая по 4 цифры можно вычислить 32K+ цифр, но делением 32/16 тут уже не обойтись, а если считать по 3 цифры, то можно вычислить в 10 раз больше. Ну а для современных компов можно сделать сумму 64 разряда, умножение 32x32->64 у них есть, в массиве хранить по 9 цифр, и считать вообще до скончания вечности.
А работает алгоритм просто, оригинальный использует два линейных массива: сумма и перенос, если мы к ним добавим еще одну размерность, и результаты каждой итерации будем складывать в свою строку, то окажется, что элемент ячейки зависит только от суммы выше и переноса справа, то есть можно поменять циклы местами, вычислить сначала последний столбец, затем предпоследний и так далее. Сумму между столбцами нам передавать вообще не нужно, поэтому остаётся только столбец с переносами, а от второго массива одна ячейка для хранения суммы во внутреннем цикле.
Наверно стоит еще уменьшить N, чтобы выдавал только верные цифры, например до N=4935u или N=M/2*1000u/3322u
- - - Добавлено - - -
Нетребовательность алгоритма к памяти впечатляет.
CodeMaster
04.01.2016, 17:25
100 знаков нам пока за глаза достаточно для начала опытов и поиска решения позволяющего перешагнуть за 1 сек для 100 знаков числа Пи на КР580ВМ80А при его штатных частотах (без разгона).
Что-то мне подсказывает (глядя на алгоритм blackmirror, что получившееся решение ни на что, кроме вычисления Пи (хоть и очень быстро)) будет неспособно. А мне как-то казалось (по ходу темы), что появилась идея найти некие универсальные вычислительные алгоритмы для 8-битных процов. Или я упустил нить повествования и цель просто узнать во сколь раз можно оптимизировать конкретный расчёт между "в лоб" и "через ж..."?
? Насколько могу судить, реализованные алгоритмы умножения и, особенно, деления (blackmirror) для 8080 самые быстрые. А деление так и для z80 самое быстрое, или есть быстрее? Для универсальности нужно кое-что добавить, но это не принципиально.
- - - Добавлено - - -
Пару слов о широте охвата процессоров. Я лично за максимальный охват, массовые и экзотические, простые и сложные - чем больше тем лучше. Могу только повторить респект litwrу за многопроцессорность.
SoftFelix
04.01.2016, 21:40
Парни, так для Спектрума (Z80) есть готовый исполняемый супер-пупер-оптимизированный бинарник с запросом "сколько цифр считать" и подсчётом времени выполнения?
perestoronin
04.01.2016, 23:14
некие универсальные вычислительные алгоритмы для 8-битных процов
за максимальный охват
Универсальные не требуются, т.к. скорости от них, как после написания программы на Си и её первичной оптимизации руками после перевода на ассемблер.
Что делать с примерами "чрезмерно" оптимизированными к примеру на КР580ВМ80А, это уже решать тем, кому этот пример достанется.
Самое лучшее что можно рекомендовать, это сопроводить грамотными краткими комментариями свои шедевры.
А универсальные в нашем случае не дадут максимальной скорости.
Все что сейчас требуется, используя найденные самые быстрые реализации умножения и деления для КР580ВМ80А (впрочем и КР1858ВМ* /Z80) в частности), подобрать самые быстрые алгоритмы собственно расчета 100 цифр числа Пи.
Аналогичное после можно будет проделать и для остальных процессоров, к примеру для 6502 и КР1801ВМ*.
После чего можно будет констатировать "действительные" скорости и вычислительные возможности этих доступных сейчас в России и Китае ретропроцессоров.
Эти же подходы и алгоритмы позволят оптимизировать и другие, ранее не самые быстрые программки.
Расчет числа Пи самое простое что можно было предложить, и суть расчета чего понятна и гуру и новичку, и результат достигается достаточно быстро и наглядно :) А главное какой прогресс - с минуты до нескольких секунд! И главное, уверен, 3 секунды это еще не предел, при выборе другого алгоритма, при удачном выборе, возможно получить более лучший результат.
с нескольких минут
Все же первый вариант на ассемблере считал быстрее минуты
perestoronin
05.01.2016, 09:28
для Спектрума (Z80) есть готовый исполняемый супер-пупер-оптимизированный бинарник
Не припомню. В шапке темы нет ? Сюда бы Alone, он бы выдал нагора суперПи для Z80 ;)
Но вроде бы его сейчас волнуют больше земные ценности, а не спектрумовские, чуть позже возможно присоединится и тогда будет желаемое здесь.
Особенно интересен результат на 20МГц на Профи (http://zx-pk.ru/showthread.php?t=21644), впрочем и на 14МГц для ZX-Evo (http://nedopc.com/zxevo/zxevo.php) тоже будет интересен.
14МГц (мега турбо режим с WAIT)
Все же первый вариант на ассемблере считал быстрее минуты
Верное замечание, поправил.
Дошло, тут тема 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
06.01.2016, 00:10
БК по-прежнему никто не тестирует.
Все БКшники находятся на отдыхе до 10 января :)
Для коммодора
результаты обновил в шапке
Дошло, тут тема 8080
Тут тема для всех процессоров, которые доступны, а остальные уже как получится, если есть кому проверить, написать, то и на том благодарствуем владельцам иномарок, только вот не понимаю почему молчат те, кто нажил иномарки в России непосильным трудом :)
Амстрад 6128 - 2.48 - 186.5 - 1646.8
Какой сильный перекос для 100 и 1000 цифр. То ли умножение на 10000 сказывается, то ли вывод на экран, но ПК-6128Ц и вектор с z80 считают 100 цифр быстрее, а 1000 медленнее.
почти 8000 цифр
Посчитать можно, а как их контролировать? На экран вектора в 512x256 одновременно можно вывести 5376 символов 4x6 (надо еще написать процедуру вывода). Выводить с прокруткой, сохранять на диск?
понадобится всего-то 172*100² с
С учетом увеличения разрядности умножения и деления скорее всего будет дольше
perestoronin
06.01.2016, 09:17
Посчитать можно, а как их контролировать?
Много цифр пока рано считать. А контроль можно наладить уже сейчас, например по какой-нибудь быстрой короткой хэш-функции, коих море и которые на выходе выдают для длинного входного массива двоичных данных контрольное относительно короткое число - как результат хэш-функции. Его же заранее обсчитать для 100 цифр результата и сравнивать с результатом аналогичной функции. Кстати в рамках задачи по расчету числа Пи очень полезное упражнение, причем не сложнее чем собственно алгоритмы расчета числа Пи. Эти функции тоже желательно заоптимизировать. Рекомендую начать с устаревшей md5sum (http://hash.online-convert.com/ru/md5-generator) и затем продолжить с более надежной sha256sum (http://hash.online-convert.com/ru/sha256-generator). Кстати они, как и подпрограммы быстрого деления и умножения длинных чисел (десятки и сотни цифр в числе), будут очень полезны не только как наглядное пособие для изучающих программирование на ретропроцессорах.
Заниматься же оптимизацией вывода результата на экран тоже нужно, но эту задачку, относительно простую, лучше отложить, сделав предположение что вывод уже давно заоптимизирован дальше не куда :) Тем более мы договорились время вывода из памяти результат расчета на экран исключить из рейтинга алгоритмов расчета.
Отправными точками можно считать следующие реализации на ассемблере алгоритмов упомянутых хэш-функций для оффтопика :)
http://www.nayuki.io/res/fast-sha2-hashes-in-x86-assembly/sha256.S
http://www.nayuki.io/page/fast-sha2-hashes-in-x86-assembly
http://www.nayuki.io/res/fast-md5-hash-implementation-in-x86-assembly/md5-fast.S
http://www.nayuki.io/page/fast-md5-hash-implementation-in-x86-assembly
md5, sha256 - не крутовато ли для данного применения? ИМХО вполне хватит crc-16 или, если очень хочется, crc-32. Хотя мне вариант с контрольной суммой не особо нравится.
perestoronin
06.01.2016, 10:50
crc-16 или, если очень хочется, crc-32
Нет не крутовато, если хочется надежности, то даже md5sum слабо, то чего уж говорить про более примитивные.
Кстати а чего крутого в этих простых функциях ? Что испугало ?
чего крутого в этих простых функциях ?
Про крутость я не писал, я писал про достаточность.
perestoronin
06.01.2016, 11:14
про достаточность
Даже md5sum не достаточно надежная, от неё все прогрессивное человечество не так давно (что такое 5 лет в нашу эпоху) отказалось в пользу как минимум sha256sum. (https://www.linux.org.ru/news/bsd/5501470)
В файлах distinfo, использующихся в системе портов FreeBSD для контроля целостности исходных текстов, произошел полный переход на использование алгоритма вычисления контрольных сумм SHA-256. Это означает, что в файлах distinfo от новых пакетов MD5-суммы указываться не будут, а существующие строки с указанием MD5-сумм игнорируются.
Такое решение принято, поскольку алгоритм SHA-256 является более стойким к криптоанализу, чем MD5, а проверка сразу двух видов контрольных сумм не увеличивала бы безопасность.
Хотя мне вариант с контрольной суммой не особо нравится.
Не нравится контрольной суммой, можно по старинке, хранить в листинге 100 верных чисел числа Пи и сравнивать в коде их с тем, что посчитал алгоритм. Тоже вариант :)
А можно еще, just for fun, вывести двоичное представление числа Пи в прямоугольную область в правом верхнем углу экрана, и рядом ниже выводить посчитанное по тестируемому алгоритму, глаз обычно у всех алмаз, сразу увидит где пиксели различаются.
Не смог психологически использовать для умножения на 10000 32 килобайта в таблицах как делают некоторые. Использовал таблицу на 768 байт
Временно вернул умножение на 10000 по маленькой таблице, чтобы проверить сколько это дает - всего 2% с копейками.
- - - Добавлено - - -
Чтобы закрыть тему влияния больших таблиц убрал еще и таблицу процедур для умножения младшего байта. Суммарный проигрыш (без большой таблицы *10000 и без таблицы процедур для умножения младшего байта) - примерно четыре с половиной процента, т.е. вклад каждой большой таблицы примерно 2 с небольшим процента.
blackmirror
07.01.2016, 22:57
Решил проверить насколько хороша формула с арктангенсами:
Pi/4=44*atan(1/57)+7*atan(1/239)-12*atan(1/682)+24*atan(1/12943)
Если считать в лоб по разложению арктангенса в ряд, то для вычислений требуются только операции деления 24/16 и два буфера - для Pi и очередного слагаемого, можно вычислить 115К десятичных цифр, или в два раза меньше, если деление правильно работает только до 2^15. В элементах ряда присутствуют нечётные числа в качестве делителей, на них делить приходится параллельно со сложением или вычитанием. Перенос в соседний байт возникает в 20% случаев, а в следующий уже только в 0.1% случаев. Общее количество операций деления 24/16 примерено 0.4*N^2 (N - число десятичных цифр), но вычисления в алгоритме двоичные. Для gpigot'а требуется 0.83*N^2 операций деления 32/16 и в два раза больше операций умножения 16x16. В общем в данном виде вычисление Pi наверно будет раз в 10 быстрее, если всё не запороть алгоритмом перевода в десятичный вид. Как оказалось, формула 4*atan(1/5)-atan(1/239) требует немного меньше операций, но без расширения разрядности правильно считать будет только 45К цифр.
55490
perestoronin
07.01.2016, 23:09
Ура, нашему полку прибыло, в теме теперь есть и математики.
В общем в данном виде вычисление Pi наверно будет раз в 10 быстрее
Неужели получим вычисление первых 100 цифр числа Пи меньше чем за доли секунды на КР580ВМ80А ?
правильно считать будет только 45К цифр.
А нам то надо всего 0.1К цифр.
blackmirror
08.01.2016, 00:49
Неужели получим вычисление первых 100 цифр числа Пи меньше чем за доли секунды на КР580ВМ80А ?
Боюсь, что это будет львиная доля, а то и не одна. Поскольку с вычитанием у него не очень, то для деления придётся занимать все регистры, значит будет развёрнутая процедура, которая загрузит байт, вызовет функцию деления 24/16, сохранит результат. Скорее всего адресацию придётся использовать абсолютную. Еще нужны будут похожие процедуры, которые результат не сохраняют, а вычитают или добавляют к числу Pi, и в некоторых случаях корректируют несколько байт для распространения переноса. Для вывода проще всего 50 раз домножить на 100 при помощи маленькой таблички. Только по мере домножения нужно будет укорачивать обрабатываемую часть, чтобы не обрабатывать мусор в младших разрядах. А при делении наоборот, отбрасывать старшие нули, делить их конечно можно, но зачем?
Вот этот (http://zx-pk.ru/showthread.php?t=25783&p=840902&viewfull=1#post840902) вариант при замене типов на short правильно считает 4138 цифр. Причем большинство шортов можно заменить на беззнаковые, в т.ч. умножение и деление. Т.е. для расчета 100 и 1000 цифр там достаточно 16*16 и 16/16.
Перенес суперделение на 6502. Трудно догадаться убрать верчение лишнего байта - благодарности уважаемому ivagor'у. Вот код для истории
div16 ;dividend+2 < divisor, CY = 0, AC = dividend+3
.repeat 8
rol dividend+1
rol dividend+2
rol
cmp divisor+1
bcc l1
bne l2
ldx dividend+2
cpx divisor
bcc l1
l2 tax
lda dividend+2
sbc divisor
sta dividend+2
txa
sbc divisor+1
l1
.endr
rol dividend+1
.repeat 8
rol dividend
rol dividend+2
rol
cmp divisor+1
bcc l1
bne l2
ldx dividend+2
cpx divisor
bcc l1
l2 tax
lda dividend+2
sbc divisor
sta dividend+2
txa
sbc divisor+1
l1
.endr
rol dividend
sta remainder+1
lda dividend+2
sta remainder
lda #0
sta dividend+2
sta dividend+3
rts
Примерно 460 тактов, для z80 - 840. Итог по скорости 6502 быстрее только менее 90%. В некоторых случаях z80 показывает очень хорошую эффективность. Но на z80 легко писать очень плохие коды, а очень хорошие очень тяжело. С 6502 гораздо легче и коды легко масштабировать, типа сделать 64/32-деление.
Последние данные по программам - дал им версию 1. :)
Коммодор +4 1.62 - 152.3 - 1362
Амстрад 6128 2.41 - 179.3 - 1582
Как обычно для 100, 1000 и 3000 цифр. Версия для Коммодора считает до 7680 цифр, а для Амстрада до 5536 в бейсике. Кроме того есть сырая версия для Амстрада в СР/М, которая досчитала до 8500 цифр, но может и немного побольше.
Чтобы совсем не пишнуться решил покинуть эту приятную тему. Может через месяц посмотрю, что тут случилось. Может появятся и результаты по БК, Спектрумам или даже лучшему домашнему ПК СССР Поиску? Успехов всем в пи-строительстве! :)
Какой сильный перекос для 100 и 1000 цифр. То ли умножение на 10000 сказывается, то ли вывод на экран, но ПК-6128Ц и вектор с z80 считают 100 цифр быстрее, а 1000 медленнее.
Конечно, вывод на экран. Под СР/М он ещё раз в 10 (!) медленнее. Зато там можно перенаправить вывод в файл как в ДОСе или Юниксе.
Если хотите сами проверить, то скачайте эмулятор, подсоедините диск и командой RUN"PI проверяйте. Выход в СР/М командой |CPM, но нужен системный диск.
Для Коммодора нужны две команды DLOAD"PI* и RUN
Посчитать можно, а как их контролировать? На экран вектора в 512x256 одновременно можно вывести 5376 символов 4x6 (надо еще написать процедуру вывода). Выводить с прокруткой, сохранять на диск?
По последним цифрам. Алгоритм таков, что сбой накапливается. Для больших чисел можно и на диск сбрасывать. Дело автора.
А можно еще, just for fun, вывести двоичное представление числа Пи в прямоугольную область в правом верхнем углу экрана, и рядом ниже выводить посчитанное по тестируемому алгоритму, глаз обычно у всех алмаз, сразу увидит где пиксели различаются.
Круто! :) Но в некоторых системах есть текстовые режимы...
perestoronin
08.01.2016, 11:31
Но в некоторых системах есть текстовые режимы
Для таких случаев вполне сгодится сравнение sha256sum с эталоном.
- - - Добавлено - - -
Вот код для истории
Листинг бы продублировать и в виде вложения. Для удобства.
Powered by vBulletin® Version 4.2.5 Copyright © 2024 vBulletin Solutions, Inc. All rights reserved. Перевод: zCarot