Просмотр полной версии : Квадратный корень
В эл.журнале 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]
;а вычислять - наверное умножая числа :)
а вот это непонятно - зачем прибавлять? почему просто не взять?
Вот и я о том-же думаю.
Видимо эта часть таблицы так хитро сформирована, что корень получается для большего диапазона чисел чем 256, т.е. значения для целого ряда, но для получения конкретного результата нужно прибавить старшую часть...
Как это сформировать - ума не приложу %(
Экперементирую...
он же пишет что есть погрешность :)
он же пишет что есть погрешность
+-1 = ерунда.
К тому-же грит что если хорошо интерполировать то всё будет гут :)
а таблицы кстати есть в комплекте?
а таблицы кстати есть в комплекте?
В том то и вопрос как их сформировать, готовых я лично не нашел...
В самом образе журнала нашлись два файла, оба являются архивами Hrust. Но распаковыватся не хотят.
что пишут?
"Неизвестный формат или ошибка в архиве".
P.S. Зайди в асю что-ли, а то опять флейм какой-то получается...
да тут наверное можно и самому рассчитать :)
перемножить да посмотреть :)
да тут наверное можно и самому рассчитать
перемножить да посмотреть
Пробовал.
Получается плохо.
Погрешность +-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 бит (ну я так предпологаю :) )
В самом образе журнала нашлись два файла, оба являются архивами 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 году.
Barmaley_m
23.03.2012, 12:19
В программе явно глюки. Я обнаружил то же самое, что 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 ----------
опс сорри, только щас топик до конца дочитал:
Размер таблицы составит таким образом 4096+256 байт.
точность точно такая же как в топик старте +\-1 в диапазоне 4096-65535.
---------- Post added at 16:06 ---------- Previous post was at 16:01 ----------
в диапазоне 4096-65535.
поправочка 4096-10240.
Остальное точно на 100%(только округляется до целого)
ну значит автор метода тоже гдето ошибся
но я думаю что он то какраз хотел сделать определение с большей точностью
для точности достаточно ~1кбайт таблиц, но как сказал Бармалей_М, нужно несколько делений на 2.
а вот и автор
Цитата:
Мой E-Mail: devils@ellink.ru
Отписался, посмотрим ответит или нет.
(хотя вряд-ли мыло до сих пор актуально)
По поводу корней: Вообще начиная с больших чисел (16640) значения корней начинают повторятся более чем 256 раз. Т.е. получается что можно просто извлекать корень из старшей части, пренебрегая младшей. Видимо это и пытается делать табличками, но начиная с 4096. (с коррекцией). В общем надо-таки разобратся до конца, ибо скорость - дело самое необходимое для спека.
---------- Post added at 16:42 ---------- Previous post was at 16:35 ----------
Вполне себе распаковываются, но там внутри только данные газеты.
Как удалось? У меня не хотел (pc-шный дехруст).
Еще можно вычислять квадратный корень по таблице квадратов целых чисел. Методом двоичного поиска ищется местоположение x в этой таблице - это местоположение и будет искомым sqrt(x). Для двоичного поиска по такой таблице длиной в 256 двухбайтных чисел требуется не более 8 итераций.
А можно прогу? (необязательно готовую к компиляции, просто пример, кусок асма)
Как удалось? У меня не хотел (pc-шный дехруст).
http://zx.pk.ru/showthread.php?t=18236
(хотя вряд-ли мыло до сих пор актуально)
Так и есть, мыло убито :(
Еще можно вычислять квадратный корень по таблице квадратов целых чисел. Методом двоичного поиска ищется местоположение x в этой таблице - это местоположение и будет искомым sqrt(x). Для двоичного поиска по такой таблице длиной в 256 двухбайтных чисел требуется не более 8 итераций.
Проще посчитать честно: http://www.zxpress.ru/article.php?id=8752
Проще посчитать честно: http://www.zxpress.ru/article.php?id=8752
Да, но это OVER дольше... :(
(если бы один раз за фрейм - это ещё туда-сюда. Но если 20 - уже тормоза...)
Проще посчитать честно: 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
генератор конечно аховый, можно сократить и ускорить
но для иллюстрации вполне подходит
и да - я ничего не тестировал :)
Вот посмотрел методом ряда вычисление, точное вычисление т.е.
Медленное, конечно, но может кому понадобится.
Виноват, невнимательно первую ссылку смотрел.
Там такое было, только гораздо более умно сделано.
---------- 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. для упрощения понимания алгоритма я не заменял вычитание сложением, что, однако, возможно, и несколько ускорит вычисление.
Powered by vBulletin® Version 4.2.5 Copyright © 2026 vBulletin Solutions, Inc. All rights reserved. Перевод: zCarot