Квадратный корень на i8080

[shoorick]

Hacker's Delight (по-нашему: Алгоритмические трюки для программистов)

[Advertiser]

[ivagor]

Стоит ли выкладывать очень быстрый, но приближенный вариант или здесь только 100% точные (с усечением)? Сделал по этому алгоритму. Приближенность связана с тем, что используются только 8 бит мантиссы исходного числа. Но погрешность результата там максимум 1.
Самый быстрый вариант требует аж 7424 байта таблиц, зато (без call и ret) выполняется за 74 такта. На z80 за 69 тактов (!!!), т.е. быстрее, чем авторский вариант. Кроме того, пока разбирался, сделал несколько вариантов, в т.ч. с таблицами всего на 768 байт - все равно быстрее sqrttab2.
Можно попытаться приделать корректор, дожимающий точность до 100%

[shoorick]

ну конечно же сто́ит! это же форум для всех - кому-нибудь пригодится, например, звук генерировать или для фильтра цифрового, или графика - там скорость важнее точности, тем более, что отбрасывание дробной части уже не есть точность

[ivagor]

Приделал к "приблизительной" процедуре корректор - теперь дает на 100% точные результаты. В худшем случае 204 такта (это вместе с call и ret) и пришлось добавить таблицу на 512 байт из sqrttab. Для сравнения sqrttab2 в лучшем случае выполняется за 527 тактов. В среднем sqrtfast7 еще быстрее (в sqrtab2 медленнее), разница почти в 4 раза.
Для подавляющего большинства применений можно поставить ret после ldax b и пользоваться приближенным результатом (только обратите внимание, что результат в таком варианте будет в A, не в L), тогда параметры будут как я написал выше.
Само вычисление корня по этому алгоритму вряд ли получится ускорить, а вот корректор скорее всего можно оптимизировать.

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

Пара слов насчет точности.
В приложенном Etalon.zip две таблицы результатов, рассчитанные в матлабе
sqrtmatlab.fix - с округлением к нулю, как считают практически все точные целочисленные извлекалки (для примера проверил sqrttab2 - совпадает).
sqrtmatlab.round - с округлением к ближайшему значению.

Что дает sqrtfast7
Выложенный ранее вариант с корректором - совпадает с sqrtmatlab.fix
Если из sqrtfast7 убрать корректор - получится sqrtfast7.round (из sqrtfast7results.zip)
Приложенный к данному посту sqrtfast7fix.zip - выдает sqrtfast7.fix (тоже из sqrtfast7results.zip)
Чтобы оценить точность приближенных вариантов можно сравнить sqrtfast7.round с sqrtmatlab.round, а sqrtfast7.fix с sqrtmatlab.fix.
Кстати, корректор от предыдущего варианта к sqrtfast7fix не совсем подходит, прицеплять его туда смысла нет.

[ivagor]

На базе варианта b2mа и вот этого варианта для z80 сделал оптимизированную версию без таблиц.
sqrtnotab - в 3 раза больше варианта b2mа (121 байт) и в 3.0-3.2 раза быстрее
sqrtnotabCompact - в 2 раза больше варианта b2mа (83 байта) и в 2.6-2.8 раза быстрее

sqrtnotab догнал sqrttab2, который с его таблицей 512 байт теперь точно не нужен. sqrtfast7 конечно все равно быстрее раза в 3-3.5 (это если считать точно, а если приближенно то в 6 раз), но и памяти жрет немерено.
Возможно вычисление двух старших бит еще можно оптимизировать.

[shoorick]

вариантов уже больше чем сфер применения
не успеваю тестировать 8)
кстати, встречал вариант на Z80 с округлением ответа (не обрезанием),
завтра с работы ссылку покажу.

[shoorick]

вот оно: http://z80-heaven.wikidot.com/math#toc27
но, к сожалению, аргумент 8-битный

а это: http://z80-heaven.wikidot.com/math#toc30
вариант с волшебным 400Н, сдвигающимся вправо

[ivagor]

Удалил свой первый вариант

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

вот оно: http://z80-heaven.wikidot.com/math#toc27
но, к сожалению, аргумент 8-битный

Это ерунда, а не округление. Достаточно одного неверного результата, чтобы нельзя было сказать, что процедура округляет к ближайшему целому, вот для примера парочка (там еще есть):
sqrt(2)=1,41~1; RoundSqrtE(2)=2
sqrt(6)=2,45~2; RoundSqrtE(6)=3

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

Однако RoundSqrtE можно допилить напильником даже не увеличив размер - меняем в конце
jr c,$+3
на два условных retа
ret c
ret z
и результат совпадет с первыми 256 байтами таблицы sqrtmatlab.round из Etalon.zip

"Сделал как у них, только правильно". Добавил округление к sqrtnotab (первые варианты с округлением по таблице удалил - у них нет преимуществ).
В качестве примера два варианта:
sqrtNoTabRoundSatur2.zip - округление с насыщением (чтобы результат поместился в байт). Результат совпадает с таблицей sqrtmatlab.round, которую я выкладывал ранее в Etalon.zip
sqrtNoTabRound2.zip - "полное" округление без насыщения. Пришлось выделить под результат регистровую пару, хотя из старшего регистра нужен только один бит (да и то редко).

[shoorick]

да, всё надо проверять, даже очевидное...
но, честно говоря, приветствуя скорость, меня смущает разрядность... причем 32-битный и даже 64-битный (33...34...40-битный) аргумент вполне реален и мне не кажется роскошью: например, если в Специалисте провести диагональ на экране, то ее длина будет как раз sqrt(256^2+384^2)=sqrt(212992)=sqrt(34000h)~461.5= 461
хотя в таких случаях можно аргумент "делить" сдвигом на 4 или 16, а затем "умножать" на 2 или 4 соответственно: sqrt(128^2+192^2)=sqrt(53248)=sqrt(D000h)~230.7=23 0*2=460

[ivagor]

По тому же алгоритму можно и больше бит сделать. Для примера сделал 24 "обычный" (с округлением вниз) и с округлением к ближайшему целому. Просто чем дальше, тем медленнее будут даваться каждые следующие биты.

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

32 битный вариант. В 4,5 раза больше ньютона, но раз в 10 быстрее (и еще точно можно оптимизировать). Отмечу, что используется самомодифицирующийся код (этот фрагмент хорошо бы переписать).