Implement double sqrt(double x) in C++ [closed]

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussi开发者_如何学Con. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. Closed 10 years ago.

Implement double sqrt(double x) in C++ without using std library.

This is a facebook interview question I saw here. http://www.glassdoor.com/Interview/Implement-double-sqrt-double-x-in-C-QTN_87210.htm Any other good idea about this?...

!!!Edited.!!!(without using std library.)

---

Look here. This CodeProject article compares 14 different methods for computing the square root.

---

The two obvious answers are bisection (semi-slow) and Newton-Raphson/Leibniz iteration (usually faster). To keep from spoiling anybody's fun, I'll do a reinterpret_cast on the question -- here's an implementation of an integer square root in 8086 assembly language using the Newton-Raphson technique:

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

This is open to some improvement -- it uses x/2 as its initial guess at the sqrt(x). With 386+ instructions, you can use bsr to find the most significant bit that's set to get a rough approximation of log₂x, and divide that by 2 to get your initial approximation.

OTOH, this really only made sense on ancient processors. For anything since the 486 (or so) that has built-in floating point hardware, it's nearly certain that the FSQRT instruction will beat this (or pretty much anything else you can write).

---

Here is one of the most genius sqrt implementations which can be found on wikipedia. It is not the most accurate, but extremely fast.

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;
}

---

If I am allowed to use log (ln) and exp then of course exp(log(x)/2) will give me the square root.

Assuming not:

If our value we find the sqrt of is x and the start value is y then we iterate y->(y+x/y)/2

Terminating condition would either be a proximity of y to its previous value or of y*y to x.

With 385 as my x value I get these values in my iterations (Excel)

1
193
97.49740933
50.7231161
29.15667189
21.1805984
19.67880541
19.62150055
19.62141687
19.62141687

You can use an "approximate" 2^(log base 2(x)/2) as a start point instead of 1. 385 has a log somewhere between 8 and 9, so if we say 8.5 and therefore start with 2^4.25. If we do this linear between 16 and 32 then we would start with 20.

Starting with 20 I get there in just 4 steps:

20
19.625
19.6214172
19.62141687

but it required previous "iterations" to calculate the approximate log and exponential.