在 C++ 中实现 double sqrt(double x)
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5000109/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Implement double sqrt(double x) in C++
提问by Josh Morrison
Implement double sqrt(double x)in C++ without using std library.
double sqrt(double x)在不使用 std 库的情况下用 C++实现。
This is a facebook interview question I saw here. http://www.glassdoor.com/Interview/Implement-double-sqrt-double-x-in-C-QTN_87210.htmAny other good idea about this?...
这是我在这里看到的 Facebook 面试问题。http://www.glassdoor.com/Interview/Implement-double-sqrt-double-x-in-C-QTN_87210.htm关于这个还有其他好主意吗？...
!!!Edited.!!!(without using std library.)
!!!编辑。！！！（不使用标准库。）
回答by Lior Kogan
回答by regality
Here is one of the most genius sqrt implementations which can be found on wikipedia. It is not the most accurate, but extremely fast.
这是最天才的 sqrt 实现之一，可以在wikipedia上找到。它不是最准确的，但非常快。
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;
}
回答by Jerry Coffin
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:
两个明显的答案是二分法（半慢）和 Newton-Raphson/Leibniz 迭代（通常更快）。为了避免破坏任何人的乐趣，我将对这个问题进行 reinterpret_cast - 这是使用 Newton-Raphson 技术在 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
This is open to some improvement -- it uses x/2 as its initial guess at the sqrt(x). With 386+ instructions, you can use bsrto find the most significant bit that's set to get a rough approximation of log2x, and divide that by 2 to get your initial approximation.
这有待改进——它使用 x/2 作为对 sqrt(x) 的初始猜测。使用 386+ 条指令，您可以使用bsr找到设置为获得 log 2x粗略近似值的最高有效位，然后将其除以 2 以获得初始近似值。
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 FSQRTinstruction will beat this (or pretty much anything else you can write).
OTOH，这真的只在古代处理器上才有意义。对于自 486（左右）具有内置浮点硬件的FSQRT任何东西，几乎可以肯定指令会击败它（或几乎任何你可以编写的东西）。
回答by CashCow
If I am allowed to use log (ln) and exp then of course exp(log(x)/2) will give me the square root.
如果我被允许使用 log (ln) 和 exp 那么当然 exp(log(x)/2) 会给我平方根。
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
如果我们发现我们的值是 x 的 sqrt 并且起始值是 y 那么我们迭代 y->(y+x/y)/2
Terminating condition would either be a proximity of y to its previous value or of y*y to x.
终止条件要么是 y 与其先前值的接近度，要么是 y*y 与 x 的接近度。
With 385 as my x value I get these values in my iterations (Excel)
使用 385 作为我的 x 值，我在迭代中得到这些值（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.
您可以使用“近似”2^(log base 2(x)/2) 作为起点而不是 1。385 的对数介于 8 和 9 之间，因此如果我们说 8.5，因此从 2^4.25 开始。如果我们在 16 到 32 之间做这个线性，那么我们将从 20 开始。
Starting with 20 I get there in just 4 steps:
从 20 开始，我只需 4 个步骤即可到达那里：
20
19.625
19.6214172
19.62141687
but it required previous "iterations" to calculate the approximate log and exponential.
但它需要先前的“迭代”来计算近似对数和指数。
