Реализовать двойной sqrt (двойной x) в С++

Посмотрите здесь. В этой статье CodeProject сравниваются 14 различных методов вычисления квадратного корня.

Два очевидных ответа: деление пополам (полумедленное) и итерация Ньютона-Рафсона/Лейбница (обычно быстрее). Чтобы никому не портить удовольствие, я проведу реинтерпретацию по этому вопросу - вот реализация целочисленного квадратного корня на языке ассемблера 8086 с использованием техники Ньютона-Рафсона:

isqrt proc uses di, number:word
;
; uses bx, cx, dx
;
    mov di,number
    mov ax,255
start_loop:
    mov bx,ax
    xor dx,dx
    mov ax,di
    div bx
    add ax,bx
    shr ax,1
    mov cx,ax
    sub cx,bx
    cmp cx,2
    ja  start_loop
    ret
isqrt endp

Это открыто для некоторых улучшений - он использует x/2 в качестве исходного предположения о sqrt(x). С более чем 386 инструкциями вы можете использовать bsr, чтобы найти старший бит, установленный для получения грубого приближения log₂x, и разделить его на 2, чтобы получить начальное приближение.

OTOH, это действительно имело смысл только на древних процессорах. Для всего, начиная с 486 (или около того), которое имеет встроенное оборудование с плавающей запятой, почти наверняка инструкция FSQRT превзойдет это (или почти все, что вы можете написать).

Вот одна из самых гениальных реализаций sqrt, которую можно найти в википедии. Он не самый точный, но чрезвычайно быстрый.

float fast_sqrt(float number) {
   long i;
   float x2, y;
   const float threehalfs = 1.5F;

   x2 = number * 0.5F;
   y  = number;
   i  = * ( long * ) &y;                     // floating point bit level hacking [sic]
   i  = 0x5f3759df - ( i >> 1 );             // Newton's approximation
   y  = * ( float * ) &i;
   y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
   y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration
   y  = y * ( threehalfs - ( x2 * y * y ) ); // 3rd iteration

   return 1/y;
}

Если мне разрешено использовать log (ln) и exp, то, конечно, exp(log(x)/2) даст мне квадратный корень.

Предполагая, что нет:

Если наше значение, которое мы находим, sqrt равно x, а начальное значение равно y, тогда мы повторяем y->(y+x/y)/2

Завершающим условием будет либо близость y к его предыдущему значению, либо y*y к x.

С 385 в качестве значения x я получаю эти значения в своих итерациях (Excel)

1
193
97.49740933
50.7231161
29.15667189
21.1805984
19.67880541
19.62150055
19.62141687
19.62141687

Вы можете использовать «приблизительное» 2 ^ (логарифмическое основание 2 (x) / 2) в качестве начальной точки вместо 1. 385 имеет логарифм где-то между 8 и 9, поэтому, если мы скажем 8,5 и, следовательно, начнем с 2 ^ 4,25. Если мы сделаем это линейно между 16 и 32, то мы начнем с 20.

Начиная с 20 я добираюсь туда всего за 4 шага:

20
19.625
19.6214172
19.62141687

но для вычисления приблизительного логарифма и экспоненты требовались предыдущие «итерации».