|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alex Volkov 2:400/520.55 10 Aug 2003 01:29:05
To : Vladimir Vassilevsky
Subject : Квадратные корни табличным методом
--------------------------------------------------------------------------------
AV>> Hичего что мотороллеровский асм?
AV>> Ты извини, я амижник.. Могу накрйняк для спектрумя.
VV>
VV> Во, для ADSP-218x :)))
Если уж пошла такая пьянка... ;)
1. Для Pentium-III можно быстренько считать аппроксимацию через
RSQRTSS или RSQRTPS. Они дают точность 12 бит. Можно увеличить точность до 23
бит используя соотношение Hьютона-Рафсона:
x0 = RSQRTSS(a)
x1 = 0.5 * x0 * (3 - (a * x0)) * x0)
2. быстрый корень есть и у AMD.
3. А вот и код для 486, который считает 32bit sqrt быстрее чем встроеный FPU
сопроцессор.
mov EBX, 40000000h; EBX = (2^(n/2-1)) << (n/2-1) 1
mov ECX, 20000000h; ECX = (2^(n/2-1)) << (n/2-2) 1
mov EDX, 40000000h; EDX = 2^(n-2) 1
loop1:
cmp EAX, EDX; 1
jb bellow; 3/1
;
add EDX, EBX; 1
add EBX, ECX; 1
shr EBX, 1; 2
shr ECX, 2; 2
lea EDX, [EDX+2*ECX]; 1
jnz loop1; 3/1
jmp done; 3/1
bellow:
sub EDX, EBX; 1
sub EBX, ECX; 1
shr EBX, 1; 2
shr ECX, 2; 2
lea EDX, [EDX+2*ECX]; 1
jnz loop1; 3/1
done:
add EDX, 2; 1 for loop, 1 to work w/ carry 1
sub EDX, EBX; EDX = lower bound of EBX^2 1
lea ECX, [EDX+2*EBX]; ECX = upper bound of EBX^2, +1 1
cmp EAX, EDX; 1
sbb EBX, 0; 1
cmp EAX, ECX; 1
sbb EBX, -1; 1
лучший случай: 3+12(n/2-1)-2+3+7 = 6n-1
хучший случай: 3+14(n/2-2)+12-2+3+7 = 7n-5
До свидания.
---
* Origin: #F3 #76 (2:400/520.55)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
