o**a
发帖数: 76 | 1 the roots of cos(sqrt(z)) is (n*pi+pi/2)^2
and \sum 1/(n*pi+pi/2)^2 converges
so I set
cos(sqrt(z)) = g(z) * \prod (1-z/(n*pi+pi/2)^2)
and take logrithmic derivative on both side to solve for g(z)
but I finally got g(z) = 1/cos(sqrt(z))
What's the problem here? What's the genus of cos(sqrt(z)) indeed? |
|
w******o
发帖数: 442 | 2 the roots of cos(sqrt(z)) is (n*pi+pi/2)^2
so cos(sqrt(z)) = prod (1-z/(n*pi+pi/2)^2)
and cos(sqrt(z))^m = prod (1-z/(n*pi+pi/2)^2) m is positive integer.
so g(z) = cos(sqrt(z))^(1-m) |
|
Q****a
发帖数: 296 | 3 我用牛顿迭代法和二分法都试过， precision 最小能设成 1e－15 (或者9e－16），再
小（比如1e-16) 就死循环了 ＝ ＝
可是我用precision = 1e-15做，返回结果比java里面Math.sqrt() 精度少一位 (比如
sqrt（2.0) 我return 1.414213562373095， 而java math return 1.
4142135623730951）。
请问大牛Math。sqrt怎么能精度多一位的？ |
|
s****d
发帖数: 56 | 4 Sqrt(a)可以用牛顿法公式迭代得到：
x=(x+a/x)/2.0 （1）
我用Java实现时，用了另一个“等价”公式：
x=(x*x+a)/(2.0*x) （2）
x我用的时double，leetcode测试表明公式(1)总是能收敛到一个固定的value，而公式(
2)却有时会出现最后在两个value跳跃的情况。
比如sqrt(3)，用公式(1)的收敛序列是：
3.0 2.0
2.0 1.75
1.75 1.7321428571428572
1.7321428571428572 1.7320508100147274
1.7320508100147274 1.7320508075688772
1.7320508075688772 1.7320508075688772
sqrt(3)，用公式(2)最后在两个值之间跳跃：
3.0 2.0
2.0 1.75
1.75 1.7321428571428572
1.7321428571428572 1.7320508100147274
1.7320508100147274 1.7320508075688772
1.732050807... 阅读全帖 |
|
w******o
发帖数: 442 | 5 first the roots of cos(sqrt(z)) is (n*pi+pi/2)^2 not (n*pi+pi/2)
second the roots of cos(sqrt(z))^m is (n*pi+pi/2)^2 too.
so prod(1-z/(n*pi+pi/2)^2) is the root expandation of cos(sqrt(z))^m |
|
o**a
发帖数: 76 | 6 我知道了，我的无穷乘积是从-\infty到\infty
实际上
cos(\sqrt(z))=\prod_{1}^{\infty} (1-z/(n*pi-pi/2)^2)
所以我得到了含根号的式子：
cos(\sqrt(z))=\sqrt[\prod_{-\infty}^{\infty} (1-z/(n*pi-pi/2)^2)] |
|
S******w
发帖数: 195 | 7 Z[sqrt(3)] is the ring of algebraic integers in the algebraic number field Q[sqrt(3)]. Such a ring is PID if and
only if it is UFD, if and only if its class group is trivial. And Z[sqrt(3)] satisfies this condition. You can find the
proof in any fundamental book on algebraic number theory. |
|
h**6
发帖数: 4160 | 8 看到版上有些面友被问到写sqrt函数的问题，现请教一下：
sqrt(x)
当x>=0的时候可以用牛顿公式逼近，当x<0的时候除了设定错误参数EDOM，返回值应该
是多少呢？ |
|
g*********s
发帖数: 1782 | 9 【 以下文字转载自 Programming 讨论区 】
发信人: gandjmitbbs (Nothing), 信区: Programming
标 题: sqrt的数值解法
发信站: BBS 未名空间站 (Wed Jan 26 18:44:22 2011, 美东)
如果用Newton's method，是否sqrt函数性质（单增且二阶连续可导）能保证任意初值
都可收敛？ |
|
c******w
发帖数: 102 | 10 if (mid * mid > i) {
high = mid;
} else {
low = mid;
}
这个地方可能出现溢出。 因为 double low = 1, high = i; 如果i的值本身比较大，
那么 mid*mide 的值很可能会比i的值大。 举个例子来说， 如果这个函数是求一个int
i的sqrt.假定 i= 2147483647， 那么你的mid值就会是 mid = low + (high - low) /
2 = 1073741823， 显然 1073741823* 1073741823的值比最大的int数要大多了。 类
似的问题也会发生到double类型上来。
比较好的办法是不是应该在初始化high的时候选择个适当大小的数字。 比如说 high =
1 << 32 如果是求double类型数字的sqrt。 |
|
c******w
发帖数: 102 | 11 if (mid * mid > i) {
high = mid;
} else {
low = mid;
}
这个地方可能出现溢出。 因为 double low = 1, high = i; 如果i的值本身比较大，
那么 mid*mide 的值很可能会比i的值大。 举个例子来说， 如果这个函数是求一个int
i的sqrt.假定 i= 2147483647， 那么你的mid值就会是 mid = low + (high - low) /
2 = 1073741823， 显然 1073741823* 1073741823的值比最大的int数要大多了。 类
似的问题也会发生到double类型上来。
比较好的办法是不是应该在初始化high的时候选择个适当大小的数字。 比如说 high =
1 << 32 如果是求double类型数字的sqrt。 |
|
o***d
发帖数: 313 | 12 难道不是float/double么?
而且test case: sqrt(3)=1 ???
sqrt(3)=1.732 ===> 2 |
|
y****n
发帖数: 743 | 13 牛顿迭代的算法要远好于Binary Search的O(lgn)。
贴个Sqrt(double)的算法。
static double Sqrt(double num)
{
double root = 1;
double diff = num - root * root;
double oldDiff = double.MaxValue;
int loop = 0;
while ((loop < 2) || (Math.Abs(diff) < Math.Abs(oldDiff)))
{
root = root + diff / root / 2;
oldDiff = diff;
diff = num - root * root;
loop++;
}
return root;
} |
|
Q****a
发帖数: 296 | 14 说是implement sqrt like math.sqrt, 我就好奇问问，找不到答案就算了～～
are |
|
k****r
发帖数: 807 | 15 function double sqrt(double d, int p). p is precision option. My code is as
follows. Please let me know if you see any error. Thanks,
public static double sqrt(double d, int p) {
if (d < 0) {
return Double.NaN;
}
double prec = Math.pow(10, - p);
double start = 0;
double end = d;
while (start < end) {
double mid = start + (end - start) / 2;
if (mid == 0) {
return mid;
}
if (... 阅读全帖 |
|
p****o
发帖数: 46 | 16 求sqrt， 有人说用binary search tree. 不知道具体是怎么做的。
有没有人说一说大致的思路。谢谢 |
|
K******g
发帖数: 1870 | 17 比如说sqrt(8)
4^2 > 8
2^2 <8
3^2 >8
2.5^2 < 8
2.75^2 < 8
2.875^2 >8
2.8125^2 < 8
...
util error < a certain value |
|
l***i
发帖数: 1309 | 18 Search between [x,n/x] if you are to compute sqrt(n) |
|
q**r
发帖数: 611 | 19 Sqrt(x) = ?
Find a, b, s.t., a^2 < x < b^2.
Then Bisection between a & b. |
|
P***P
发帖数: 1387 | 20 google quake III inverse sqrt |
|
P***P
发帖数: 1387 | 21 google quake III inverse sqrt |
|
f*******t
发帖数: 7549 | 22 float sqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point
bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can
be rem... 阅读全帖 |
|
o***d
发帖数: 313 | 23
,?很多case误差为1,比如sqrt(3), leetcode: results: 1, my results: 2 |
|
c***f
发帖数: 40 | 24 Implement int sqrt(int x).
Compute and return the square root of x.
这个问题的复杂度是多少呢，
both recursive way and Newton Raphson way |
|
c***f
发帖数: 40 | 25 这道题的 返回值是不是要满足：
Min(r^2 - X) 其中r＊r <= X ?
比如 sqrt(8) 返回2 而不是3？ |
|
p****e
发帖数: 3548 | 26 N是哪个数？
如果是这样的话，算多少
class Solution {
public:
int sqrt(int x) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(x < 0) return -1;
if(x == 0) return 0;
stack ss;
while(x > 0){
ss.push(x%100);
x = x/100;
}
int result = 0, t;
int residue = 0;
while(!ss.empty()){
int base = 20 * result;
t = ss.top() + residue*100;
ss.pop()... 阅读全帖 |
|
r**h
发帖数: 1288 | 27 double sqrt是说输入输出都要是double吗？
那应该用牛顿法比较好吧？ |
|
c*******y
发帖数: 1630 | 28 很小的时候，1/sqrt(1/x) 等价于很大
x很大的时候，可以把初始值猜得小一点。 肯定排除二分，起码newton-raphson |
|
c******a
发帖数: 789 | 29 newton就是优化。你画一画就明白了，比2分缩得还快。
在leetcode上，2分是过不了大oj的，非要newton，哪怕leetcode是int的sqrt。 |
|
i********y
发帖数: 153 | 30 public double sqrt(double x) {
double epsilon = 0.000001;
if (x < 0) {
throw new IllegalArgumentException();
}
double low = 0;
double high = x;
while (Math.abs(low-high) >epsilon) {
double mid = low + (high - low) / 2;
double divident = x / mid;
if (Math.abs(divident - mid)
return mid;
} else if (divident < mid) {
high = mid;
... 阅读全帖 |
|
n****e
发帖数: 678 | 31 double sqrt(double x) {
if (x == 0.0) {
return 0.0;
}
double curr = 1.0;
double prev = 0.0;
while (curr != prev) {
prev = curr;
curr = (x/prev + prev)/2;
}
return curr;
} |
|
Q****a
发帖数: 296 | 32 电面里面试官让写返回double的，可是我回去运行程序发现我的结果比Math.sqrt 精度
少一位，咋办？ |
|
S****e
发帖数: 127 | 33 Did he also ask you to have the same precision as math.sqrt? If not, you are
really zuan niu jiao jian now. |
|
b*******g
发帖数: 57 | 34 请问如何评估下面代码的时间复杂度？谢谢。
double sqrt(double x) {
double y = x/2;
double sq = y*y;
double epsilon = DBL_EPSILON;
while (abs(x-sq) > epsilon) {
y = (y+x/y)/2;
sq = y*y;
}
return y;
} |
|
c**z
发帖数: 669 | 35 class Solution {
public:
int sqrt(int x) {
int l = 0;
int r = x;
while( l<=r)
{
int m = l + (r-l)/2;
if ( m*m == x) return m;
else if ( m*m > x)
{
r = m -1;
}
else
{
l = m + 1;
}
}
return -1;
}
}; |
|
b******g
发帖数: 3616 | 36 非大牛，也在刷题。
看了你的code发现两个问题：
第一是溢出问题：当x很大时，你的第一轮m*m = x^2/4，很可能就已经溢出了。我想这
是造成为什么会time limit exceeded的原因。将乘法比较改为x/m的除法比较就可以避
免这个问题。
第二个问题：我的理解是这题求的是一个近似平方根，也就是sqrt(17)应该给出的答案
是4.但你的程序似乎对非完全平方数都会返回-1 |
|
m****r
发帖数: 6639 | 37 sqrt 怎么能就要整数? 还是我不理解你的问题? 这个api就是给你准确结果, 你要整
数就自己cast. |
|
g*****g
发帖数: 34805 | 38 这个你没有说错，如果我有10个地方，需要做这个操作。
我会自己写一个utility method包一下Math.sqrt。
原则就是看几个，一是总代码更小/更简洁，二是看
改动的时候是否要改多个地方。 |
|
g*********s
发帖数: 1782 | 39 如果用Newton's method，是否sqrt函数性质（单增且二阶连续可导）能保证任意初值
都可收敛？ |
|
c********a
发帖数: 10 | 40 ln (ln (n ^ sqrt(n) ) > 2 ln(n) == ln ln (2^n) |
|
