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

В эл.журнале Bugs #01 наткнулся на сабжевую статью: http://www.zxpress.ru/article.php?id=1819&skip=1

Вот одна из процедур которая меня заинтересовала:

Цитата:

4. Неявное табличное вычисление. ( Осторожно - взрыв мозгов ! )

LD A,H ; 4 : 1
CP 16 ; 7 : 2
JR NC,M1 ; 12/7: 2
OR 128 ; 7 : 2
LD H,A ; 4 : 1
LD A,(HL) ; 7 : 1
RET ; 10 : 1
M1: LD L,H ; 4 : 1
LD H,127 ; 7 : 2
LD H,(HL) ; 7 : 1
LD L,A ; 4 : 1
ADD A,(HL); 7 : 1
RET ; 10 : 1
----------------------
17 байт.

Пpи HL = от 0 до 4095, Вpемя = 46 тактов.
Пpи HL = от 4096 до 65535, Вpемя = 62 такта.

Pазмеp таблицы 5120 . ( адрес в памяти 32768 )
Таблица состоит:
0000-4095 - ответы для HL от 0-4095
4096-4351 - интерполирование диапазона 4096-19199
4352-4607 - интерполирование диапазона 19200-33791
4608-4863 - интерполирование диапазона 33792-34815
4864-5119 - интерполирование диапазона 34816-65535

Почему именно так - можете и не спрашивать.
Дополнительная 256-байтная таблица с адреса 32512.
Состав:
DS 75 ,144
DS 57 ,145
DS 4 ,146
DS 120,147

===== НУ, ЧТО - БАШНЮ ОТОРВАЛО ??? =====

Сейчас отпустит, когда расскажу о точности вычисления:

Абсолютно точно = 50046 чисел. 77%
Ошибка на -1 = 10321 число. 15%
Ошибка на +1 = 5199 чисел. 8%

Ну, что сказать в свое оправдание - надо лучше интерполировать !
( Но так впадлу ... да и времени нет совсем ... )

Вопрос: Кто-нибудь подскажет как сформировать таблицу?
(первые 4096 байт понятно, а вот остальное?)

у меня вторая половина сомнения вызывает

Цитата:

; ld a,h
M1: LD L,H ; 4 : 1
LD H,127 ; 7 : 2
LD H,(HL) ; 7 : 1
;здесь понятно - берем адрес таблицы для диапазона
LD L,A ; 4 : 1
; и здесь понятно - отбрасываем младший байт

ADD A,(HL); 7 : 1
; а вот это непонятно - зачем прибавлять? почему просто не взять?

RET ; 10 : 1

для примера - число #1000
ld a,#10

M1: LD L,#10 ; 4 : 1
LD H,127 ; 7 : 2
LD H,(HL) ; 7 : 1
LD l,#10 ; 4 : 1
ADD #10,(HL); 7 : 1
;по идее в таблице должно быть число #30
;что по факту - хз
RET ; 10 : 1[/QUOTE]
;а вычислять - наверное умножая числа :)

Цитата:

Сообщение от jerri

а вот это непонятно - зачем прибавлять? почему просто не взять?

Вот и я о том-же думаю.
Видимо эта часть таблицы так хитро сформирована, что корень получается для большего диапазона чисел чем 256, т.е. значения для целого ряда, но для получения конкретного результата нужно прибавить старшую часть...
Как это сформировать - ума не приложу %(
Экперементирую...

он же пишет что есть погрешность :)

Цитата:

Сообщение от jerri

он же пишет что есть погрешность

+-1 = ерунда.
К тому-же грит что если хорошо интерполировать то всё будет гут :)

а таблицы кстати есть в комплекте?

Цитата:

Сообщение от jerri

а таблицы кстати есть в комплекте?

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

В самом образе журнала нашлись два файла, оба являются архивами Hrust. Но распаковыватся не хотят.

что пишут?

Цитата:

Сообщение от jerri

что пишут?

"Неизвестный формат или ошибка в архиве".

P.S. Зайди в асю что-ли, а то опять флейм какой-то получается...

да тут наверное можно и самому рассчитать :)
перемножить да посмотреть :)

Цитата:

Сообщение от jerri

да тут наверное можно и самому рассчитать
перемножить да посмотреть

Пробовал.
Получается плохо.
Погрешность +-5.
Да и неудивительно! Я ведь вообще не представляю как полагается считать эту интерполяцию, поэтому считал наугад...

По-ходу в программе глюк.
M1: LD L,H
LD H,127
LD H,(HL)
LD L,A
ADD A,(HL)
RET
К момену прихода на метку М1, в аккумуляторе находится значение H.
Ага. Он-же отгружается в L. Потом H дважды меняется и в L кладется A. КОТОРОЕ = БЫВШЕМУ H, И КОТОРОЕ УЖЕ ТАМ!
К тому-же непонятно зачем заводить четыре таблицы по 256, если в каждую попадаем только при определённом значении H, и следовательно только в один диапазон. Т.е. можно было-бы обойтись одной (это если принимать процедуру как правильную).
Так что по-ходу что-то тут недописано...

есть вероятность пропущенной команды

Цитата:

M1:
ld a,l
LD L,H
LD H,127
LD H,(HL)
LD L,A
ld a,(hl)
; ADD A,(HL)
RET

но я хз :)

одной обойтись нельзя

как должна выглядеть таблица извлечения корней от 0 до 255

0 1 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

и тут уже надо смотреть как ты будешь округлять :)

кстати для этого у него и ADD A,(HL) чтобы хоть както скомпенсировать преобразование 16 бит в 8 бит (ну я так предпологаю :) )

Цитата:

Сообщение от Destr

В самом образе журнала нашлись два файла, оба являются архивами Hrust. Но распаковыватся не хотят.

Вполне себе распаковываются, но там внутри только данные газеты.

а вот и автор :)

Цитата:

Мой E-Mail: devils@ellink.ru

---------- Post added at 11:55 ---------- Previous post was at 11:53 ----------

на основе вот этого можно анализировать

Цитата:

1. Тоpмоз которого никто не видел !

LD DE,1 ; 10 : 3
XOR A ; 4 : 1
M1: SBC HL,DE ; 15 : 2
RET C ; 11/5 : 1
INC DE ; 6 : 1
INC DE ; 6 : 1
INC A ; 4 : 1
JR M1 ; 12 : 2
---------------------
12 байт.

Мин. вpемя = 14 + 26 = 40 тактов
Макс.вpемя = 14 + 255 * 48 = 12254 такта.

Hу, скажем так, - это pаботает основываясь на том, что количес-
тво ответов с каждым следующим целым ответом возpастает на 2.
Hаписана мною впеpвые была в 1994 году.

В программе явно глюки. Я обнаружил то же самое, что Destr. К тому же, неверны данные об адресе начала таблицы. При значениях аргумента >4096 регистр H Загружается число 7F, а потом идет считывание из HL. То есть идет считывание по адресам меньшим, чем 32768.

Еще можно заметить, что если значение аргумента >4096 - То его младший байт вообще не используется. Используется только старший байт. Я распечатал квадраты всех чисел от 0 до FF. В распечатке видно, что при значениях квадрата x>4096, одному и тому же значению старшего байта x соответствует не более двух различных значений sqrt(x). Поэтому и без всякой интерполяции, если брать значение sqrt(x) из таблицы только по старшему байту для x>4096 - то найденное таким образом приближение будет отличаться от истинного sqrt(x) не более чем на единицу. Размер таблицы составит таким образом 4096+256 байт.

Еще можно вычислять квадратный корень по таблице квадратов целых чисел. Методом двоичного поиска ищется местоположение x в этой таблице - это местоположение и будет искомым sqrt(x). Для двоичного поиска по такой таблице длиной в 256 двухбайтных чисел требуется не более 8 итераций.

Barmaley_m, он явно пишет что по адресу #7f00 находится таблица интерполяций где есть адреса 4 таблиц под 4 диапазона
а расчеты сюда покажешь?

---------- Post added at 12:33 ---------- Previous post was at 12:32 ----------

скорость вычисления какая?

Код:

M1: LD L,H ; 4 : 1 LD H,127 ; 7 : 2 LD H,(HL) ; 7 : 1 LD L,A ; 4 : 1 ADD A,(HL); 7 : 1 RET ; 10 : 1

Если младший байт не учитывается, а он не учитывается судя по коду и по:

Код:

Ошибка на -1 = 10321 число. 15% Ошибка на +1 = 5199 чисел. 8%

то зачем пять таблиц по 256байт?! Достаточно одной на 256 байт.

---------- Post added at 13:32 ---------- Previous post was at 13:11 ----------

Код:

M1 ld l,h ld h,high tabl2 ld a,(hl) ret генерация второй таблицы: n=0......255 (n+tabl2)=целое(корень(n*256))

причём первые 16 значений таблицы не используются

Но, ради взрыва мозга, можно и штаны через голову одеть.

---------- Post added at 13:59 ---------- Previous post was at 13:32 ----------

опс сорри, только щас топик до конца дочитал:

Цитата:

Сообщение от Barmaley_m

Размер таблицы составит таким образом 4096+256 байт.

точность наверное

точность точно такая же как в топик старте +\-1 в диапазоне 4096-65535.

---------- Post added at 16:06 ---------- Previous post was at 16:01 ----------

Цитата:

Сообщение от DimkaM

в диапазоне 4096-65535.

поправочка 4096-10240.

Остальное точно на 100%(только округляется до целого)

ну значит автор метода тоже гдето ошибся
но я думаю что он то какраз хотел сделать определение с большей точностью

для точности достаточно ~1кбайт таблиц, но как сказал Бармалей_М, нужно несколько делений на 2.

Цитата:

Сообщение от jerri

а вот и автор
Цитата:
Мой E-Mail: devils@ellink.ru

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

По поводу корней: Вообще начиная с больших чисел (16640) значения корней начинают повторятся более чем 256 раз. Т.е. получается что можно просто извлекать корень из старшей части, пренебрегая младшей. Видимо это и пытается делать табличками, но начиная с 4096. (с коррекцией). В общем надо-таки разобратся до конца, ибо скорость - дело самое необходимое для спека.

---------- Post added at 16:42 ---------- Previous post was at 16:35 ----------

Цитата:

Сообщение от Vitamin

Вполне себе распаковываются, но там внутри только данные газеты.

Как удалось? У меня не хотел (pc-шный дехруст).

Цитата:

Сообщение от Barmaley_m

Еще можно вычислять квадратный корень по таблице квадратов целых чисел. Методом двоичного поиска ищется местоположение x в этой таблице - это местоположение и будет искомым sqrt(x). Для двоичного поиска по такой таблице длиной в 256 двухбайтных чисел требуется не более 8 итераций.

А можно прогу? (необязательно готовую к компиляции, просто пример, кусок асма)

Цитата:

Сообщение от Destr

Как удалось? У меня не хотел (pc-шный дехруст).

http://zx.pk.ru/showthread.php?t=18236

Цитата:

Сообщение от Destr

(хотя вряд-ли мыло до сих пор актуально)

Так и есть, мыло убито :(

Цитата:

Сообщение от Barmaley_m

Еще можно вычислять квадратный корень по таблице квадратов целых чисел. Методом двоичного поиска ищется местоположение x в этой таблице - это местоположение и будет искомым sqrt(x). Для двоичного поиска по такой таблице длиной в 256 двухбайтных чисел требуется не более 8 итераций.

Проще посчитать честно: http://www.zxpress.ru/article.php?id=8752

Цитата:

Сообщение от alone

Проще посчитать честно: http://www.zxpress.ru/article.php?id=8752

Да, но это OVER дольше... :(
(если бы один раз за фрейм - это ещё туда-сюда. Но если 20 - уже тормоза...)

Цитата:

Сообщение от alone

Проще посчитать честно: http://www.zxpress.ru/article.php?id=8752

У меня в формулах в нижней части статьи абраказябрики прут. Так должно быть?

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

Код:

; hl = число из которого берётся корень ; бонус метода в замене вычитание сложением ; для этого инвертируется начальное число и $ производится банальное добавление ld a,h cpm ld h,a ld a,l cpm ld l,a inc hl ld de,#0000 ; полученное число, результат «корнения» ld bc,#0001 ; первое значение для вычитания sqrt add hl,bc inc bc inc bc inc de jp nc,sqrt ; готово ; de содержит число, соотвествующее корню ; среднее время на цикл вычисления = 11+3*6+10 = 39 тактов на цикл, ; максимум 39*256 = 9984 такта на циклы, минимум 39, ; ПЗО будут ещё 24 + 10 = 34 такта. ret

мой вариант на основе самого первого алгоритма

Код:

;извлечение корней - табличный вариант ;с округлением вниз до ближайшего целого ;размер таблиц страница sqrt_low equ #c000 ;нижние 16128 знaчений sqrt_hig equ #ff00 ;грубые 49408 значений sqrt ld a,h ;4 cp #3f ;7 jr nc,sqrt_0 ;7 ;для значений 0-16127 add a,sqrt_low/256 ;7 ld h,a ;4 ld a,(hl) ;7 ret ;10 ; 46 ;для значений 16128-65535 sqrt_0 ;+5 ld l,a ;4 ld h,sqrt_hig/256 ;7 ld a,(hl) ;7 ret ;10 ; 51 sqrt_gen ;наглядный генератор таблиц ;исходные значения hl - число для извлечения корня ; de - адрес в таблице xor a ld (sqrt_value),a ld hl,#0001 ld (sqrt_ctr),hl dec hl ld de,#c000 sqrt_g3 ld bc,1 sqrt_ctr equ $-2 sqrt_g0 ;проверяем на выпадение из точного диапазона ld a,h cp #3f jr c,sqrt_g2 ;да выпали и теперь корректируем de ld e,a ld d,sqrt_hig/256 sqrt_g2 ex de,hl ld (hl),0 sqrt_value equ $-1 inc hl ex de,hl inc l jr nz,sqrt_g1 inc h ret z ;таблица готова sqrt_g1 dec bc ld a,b or c jr nz,sqrt_g0 ld bc,(sqrt_ctr) inc bc inc bc ld (sqrt_ctr),bc ld a,(sqrt_value) inc a ld (sqrt_value),a jr sqrt_g3

генератор конечно аховый, можно сократить и ускорить
но для иллюстрации вполне подходит
и да - я ничего не тестировал :)

Цитата:

Сообщение от GriV

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

Виноват, невнимательно первую ссылку смотрел.
Там такое было, только гораздо более умно сделано.

---------- Post added at 10:10 ---------- Previous post was at 09:29 ----------

Подумав, сделал такой компромисс между скоростью и размером таблиц.
Всего таблица будет 768 байт.

Суть следующая.
Процедура вычисления корня медленна потому, что происходит небыстрое итеративное приближение к заданному значению.
Можно это приближение заменить табличным значением.
Т.е. используя значение старшего регистра hl (т.е. регистр h) можно определить наименьшее приближённое значение для начала итеративного поиска и затем уже доводить финальную часть "поиска" путем классического вычитания нечётного числа.

Конкретный пример.
Есть число 1761.
В этом случае старший байт будет 6. для этого значения выбирается базовое значение 1681 и значение вычисленное - 41. Тогда можно занести в вычитаемое 41*2+1=83 (путём банального add hl,hl, inc hl) и получить начальное нечётное число.
После этого вычитаем из 1761 значение 1681 получаем 80.
Пытаемя вычесть из остатка равному 80 полученное вычитаемое нечётное число 83 - не получается, т.о. счёт закончен, вычисленное целое значение корня - 41.
Т.е. счёт произошёл в 1 итерацию.

По этому примеру видно главная проблема методики: для числа в диапазоне 0-255 будет производится (для конкретно числа 255) аж 16 итераций.
Что технически можно решить заведением отдельной таблицы под эти 256 значений.

Для значений 256-511 остаётся всего 7 итераций, что для меня является терпимым. Чем выше значение корня, тем быстрее он будет вычисляться.

Код:

; hl — число для корня ex de,hl ; нужно получить данные из таблицы ld h,tab/256 ; загружаем адрес таблицы ld l,d ; устанавливаем по старшему байту ld c,(hl) ; загружаем базовое значение inc h ld b,(hl) inc h ld a,(hl) ; и значение корня для него ld l,a ld h,0 ; создаём нечётное вычитаемое число add hl,hl inc hl ex de,hl sbc hl,bc ; т.е. до этого делали add hl,hl то флаг переноса ; сброшен, вычитаем базовое число sqr sbc hl,de ; собственно делаем счёт inc de inc de inc a jp nc,sqr dec a ; возвращаем истиное значение корня ret ; в А - полученное значение корня

---------- Post added at 10:14 ---------- Previous post was at 10:10 ----------

P.S. для упрощения понимания алгоритма я не заменял вычитание сложением, что, однако, возможно, и несколько ускорит вычисление.