ну значит автор метода тоже гдето ошибся
но я думаю что он то какраз хотел сделать определение с большей точностью
ну значит автор метода тоже гдето ошибся
но я думаю что он то какраз хотел сделать определение с большей точностью
С уважением,
Jerri / Red Triangle.
для точности достаточно ~1кбайт таблиц, но как сказал Бармалей_М, нужно несколько делений на 2.
Отписался, посмотрим ответит или нет.
(хотя вряд-ли мыло до сих пор актуально)
По поводу корней: Вообще начиная с больших чисел (16640) значения корней начинают повторятся более чем 256 раз. Т.е. получается что можно просто извлекать корень из старшей части, пренебрегая младшей. Видимо это и пытается делать табличками, но начиная с 4096. (с коррекцией). В общем надо-таки разобратся до конца, ибо скорость - дело самое необходимое для спека.
---------- Post added at 16:42 ---------- Previous post was at 16:35 ----------
Как удалось? У меня не хотел (pc-шный дехруст).
А можно прогу? (необязательно готовую к компиляции, просто пример, кусок асма)
Проще посчитать честно: 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
но для иллюстрации вполне подходит
и да - я ничего не тестировал
С уважением,
Jerri / Red Triangle.
Виноват, невнимательно первую ссылку смотрел.
Там такое было, только гораздо более умно сделано.
---------- 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. для упрощения понимания алгоритма я не заменял вычитание сложением, что, однако, возможно, и несколько ускорит вычисление.
Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)