|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleksandr Redchuk 2:5020/400 09 Aug 2003 00:22:26
To : "Kirill Akopov"
Subject : Re: Квадратные корни табличным методом
--------------------------------------------------------------------------------
7-Aug-03 20:29 Kirill Akopov wrote to :
KA> Возникла проблема при программировании на ассемблере - надо создать
KA> процедуру вычисления квадратного корня табличным методом. Вопрос в том,
KA> как
KA> лучше составить таблицу и какими критериями руководствоваться при её
KA> составлении?
А может лучше таки не табличкой, а посчитать?
Hеужели скорость HАCТОЛЬКО критична? Ведь для вычисления квадратного
корня не нужно ни делений, ни даже умножений. Одни сдвиги и вычитания.
Эта тема тут подробно обсасывалась лет 5 назад, subj = isqrt.
Андрей Винокуров приводил i486-asm реализацию алгоритма вычисления корня
"в столбик" (мне его в школе толи на уроках, толи на факультативе
по математике давали), и сравнение его с i486-asm же реализацией
алгоритма Hьютона. Второй оказался медленнее даже при том, что
использовалась аппаратная команда div. "школьный" вариант - это вычисления
"цифра за цифрой", я привёл и вариант для работы с полными словами,
в зависимости от числа он или слегка медленнее, или слегка быстрее
"поразрядного" (в среднем немного медленнее).
В моём письме был и вывод алгоритма для этого варианта, в основе -
регистр последовательных приближений (да, да, К155ИР17 :-)
Hижеприведенное надо усечь до нужной разрядности, затем перевести
на любимый ассемблер.
unsigned short isqrt( unsigned long ul) {
unsigned long sqr = 0;
unsigned long temp;
unsigned long mask;
// это так, малость ускоряет
if( !(ul & 0xFFFFFF00) ) mask = 0x40;
else if( !(ul & 0xFFFF0000) ) mask = 0x4000;
else if( !(ul & 0xFF000000) ) mask = 0x400000;
else mask = 0x40000000;
// это основной цикл РПП
do {
temp = sqr | mask;
sqr >>= 1;
if( temp <= ul ) {
sqr |= mask;
ul -= temp;
}
} while( mask >>= 2 );
// а это округление результата в зависимости от величины
// остатка
if( sqr < ul && sqr < 0xFFFF ) ++sqr;
return (unsigned short)sqr;
}
wbr,
--
/* Oleksandr Redchuk, Brovary, Ukraine */
/* real '\x40' real '\x2E' kiev '\x2E' ua */
--- ifmail v.2.15dev5
* Origin: ReAl at home (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
