Вычислить квадратный корень без FPU

@R71MT · Регистрация: 29.07.2014

Студворк — интернет-сервис помощи студентам

Всем привет!
Допустим, имеется N-байтный/двумерный массив, и нужно вычислить сумму элементов главной диагонали. Когда длина массива известна (к примеру 100 байт), то здесь ясно, что разрядность матрицы 10х10. Но если длина массива не известна, то нужно вычислить кв.корень из N. Как это сделать без сопроцессора?
P.S.\\ команды FPU они ещё не проходили

@Mikl___ · 20.04.2016, 08:42

R71MT,
Казалось бы, что может быть проще fsqrt, но мы пойдем другим путем

Самый известный целочисленный алгоритм для вычисления квадратного корня из числа поражает своей простотой

C
1
2
3
4
5
6
    unsigned sqrt_cpu_int(usigned X)
    {    unsigned div = 1, result = 0; 
        while (X > 0)
        {    X -= div;  div += 2; result += X < 0 ? 0 : 1;     }
        return result; 
    }

Недостаток данного алгоритма - количество итераций будет увеличиваться с ростом Х

вычисление квадратного корня по разложению в ряд Тейлора.
Пусть $https://www.cyberforum.ru/cgi-bin/latex.cgi?X$ - любое число; $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(X)$ - некоторая функция, зависящая от $https://www.cyberforum.ru/cgi-bin/latex.cgi?X$ ; $https://www.cyberforum.ru/cgi-bin/latex.cgi?a$ - известное число, близкое к $https://www.cyberforum.ru/cgi-bin/latex.cgi?X$ ; $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(a)$ - известное значение функции.
Разложим $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(X)$ в ряд Тейлора:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?f(X)=f(a)+(X-a)f'(a)+\frac{(X-a)^{2}f''(a)}{2!} + ... + \frac{(X-a)^{n}f^{n} (a)}{n!}$
Пусть $https://www.cyberforum.ru/cgi-bin/latex.cgi?X$ - число, из которого нужно извлечь корень. Тогда $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(X)=\sqrt{X}$ ; $https://www.cyberforum.ru/cgi-bin/latex.cgi?a$ - известное число близкое к $https://www.cyberforum.ru/cgi-bin/latex.cgi?X$ ; $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(a)=\sqrt{a}$ - известное число близкое к $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{X}$ , и $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(X)=\sqrt{a} +\frac{X-a}{2\sqrt{a}}+...=\frac{2a+X-a}{2\sqrt{a}}=\frac{a+X}{2\sqrt{a}}$
Величина $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{X}$ может быть найдена, если задаться величиной $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{a}$ и затем вычислить $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(X)$ . $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(X)^{2}$ можно сравнить с исходным числом $https://www.cyberforum.ru/cgi-bin/latex.cgi?X$ . Если точность окажется недостаточной, тогда число $https://www.cyberforum.ru/cgi-bin/latex.cgi?a$ заменяется на $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(X)^{2}$ , $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{a}$ на $https://www.cyberforum.ru/cgi-bin/latex.cgi?f(X)$ и вычисление повторяется
поиск целочисленного квадратного корня методом Ньютона начинается с некоторого значения g₀, которое является начальной оценкой $https://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{X}$ . Затем выполняется серия уточнений значения квадратного корня по формуле $https://www.cyberforum.ru/cgi-bin/latex.cgi?g_{n+1}=\frac{g_{n}+\frac{X}{g_{n}}}{2}$ . Для уменьшения количество итераций можно на первом этапе более точно подобрать начальное значения для переменной g₀
{ usigned x1;
int a, g₀, g₁;
if ( x <= 1 ) return x;
a = 1;
x1 = x - 1;
if (x1 > 65535) {a = a + 8; x1 = x1 >> 16;}
if (x1 > 255) {a = a + 4; x1 = x1 >> 8;}
if (x1 > 15) {a = a + 2; x1 = x1 >> 4;}
if (x1 > 3) {a = a + 1;}
g₀ = 1 << a; // g₀ = 2ª
g₁ = (g₀ + (x >> a)) >> 1;
while (g₁ < g₀) // повторяем, пока приближения строго уменьшаются
{ g₀ = g₁; g₁ = (g₀ + (x/g₀)) >> 1}
}

Так как деление достаточно медленная операция, можно от нее отказаться. Для вычисления квадратного корня используем умножение. 32-разрядное число Х будет иметь 16-разрядный квадратный корень. На каждом шаге происходит уточнение 1 бита значения корня. Для ускорения сделано "безбранчевое" вычисление прибавить или отнять значение в соответствующем разряде

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    mov ebx,4000h
    mov ecx,8000h
    mov eax,40000000h
@@: cmp eax,X
    je @f; преждевременный выход из цикла
    sbb edx,edx; если CF=1 тогда edx=0FFFFFFFFh иначе edx=0
    sub ecx,ebx
    and edx,ebx; если CF=1 тогда edx=ebx иначе edx=0
    lea ecx,[ecx+edx*2]; если CF=1 тогда ecx=ecx+ebx иначе ecx=ecx-ebx
    shr ebx,1; переходим к следующему разряду
    mov eax,ecx
    mul eax; получаем "eax в квадрате"
    test ebx,ebx
    jnz @b
@@: mov eax,ecx; eax:=sqrt(X)

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\sum\limits_{n=1}^{k}(2n-1)=k^2$

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
unsigned sqrt(unsigned Y){
  unsigned N = get_last_bit_pos(Y);
  unsigned X = 1 << (N >> 1);
  unsigned bit;
  
  if(N == 0) return Y;
 
  for(bit = X >> 1; bit > 0; bit >>= 1){
    X |= bit;
    if(X * X > Y) X &= ~bit;
// тут можно еще на равенство проверять
// if(X * X == Y) return X;
  }
 
  return X;
}

алгоритм был описан аж в 1945 в Von Neumann J. "First Draft of a Reaport on the EDVAC"

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    mov ebp,X
        inc ebp
    bsr ecx,ebp
    and ecx,-2
    mov ebx,1
    shl ebx,cl;для уменьшения количества итераций 
        xor eax,eax
@@: lea ecx,[eax+ebx]
    shr eax,1
    cmp ecx,ebp
    sbb edx,edx
    mov edi,edx
    and edx,ecx
    sub ebp,edx
    and edi,ebx
    or eax,edi
    shr ebx,2
    jnz @b

И еще много интересного можно найти в Уоррен "Алгоритмические трюки для программистов" -- М. :Издательский дом "Вильямс" 2003

@R71MT · 20.04.2016, 10:38 **[ТС]**

Mikl___, большое спасибо за разъяснения!
Смысл сказанного уловил, и заточив под-себя написал что-то подобное:

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
X   dw  9097
 
start:
   mov   ax,[X]
   call  SQRT
   ....
   
;нннннннннннннннннннннннннннннннннннннннннннннннннннннннннннннннннннннннннннннн
SQRT:
  mov   bx,1
@@:
  push  ax            ; входное значение
  xor   dx,dx         ;
  div   bx            ;
  cmp   ax,bx         ;
  jb    correct       ;
  jz    @f            ;
  inc   bx            ;
  pop   ax            ;
  jmp   @b            ;
correct:              ;
  dec   bx            ;
@@:                   ;
  pop   ax            ;
  xchg  ax,bx         ; AX = результат
RET

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@R71MT Эксперт Hardware 6211 / 2445 / 403 Регистрация: 29.07.2014 Сообщений: 3,175 Записей в блоге: 4

	Вычислить квадратный корень без FPU 19.04.2016, 23:57. Показов 3903. Ответов 2 Метки нет (Все метки) Всем привет! Допустим, имеется N-байтный/двумерный массив, и нужно вычислить сумму элементов главной диагонали. Когда длина массива известна (к примеру 100 байт), то здесь ясно, что разрядность матрицы 10х10. Но если длина массива не известна, то нужно вычислить кв.корень из N. Как это сделать без сопроцессора? P.S.\\ команды FPU они ещё не проходили 1

Вычислить квадратный корень без FPU

Решение