p****o 发帖数: 46 | 1 求sqrt, 有人说用binary search tree. 不知道具体是怎么做的。
有没有人说一说大致的思路。谢谢 |
g*******y 发帖数: 1930 | 2 不需要BST吧
想想x^2 = a方程的数值解法(弦切,弦割法) |
p****o 发帖数: 46 | 3 你的意思是说
随便取两个点,切x轴,找到第三个点,
然后用这第三个点和前边两点中的一个点
接着做。
看到网上列出来很多方法
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
如果面试的时候,不知道哪个方法比较好。
【在 g*******y 的大作中提到】 : 不需要BST吧 : 想想x^2 = a方程的数值解法(弦切,弦割法)
|
g*******y 发帖数: 1930 | 4 Babylonian method 这个跟弦切还是弦割(忘了是哪个)是等价的
面试的时候说一个就不错了,又不是面试数学家或者数值计算专家
【在 p****o 的大作中提到】 : 你的意思是说 : 随便取两个点,切x轴,找到第三个点, : 然后用这第三个点和前边两点中的一个点 : 接着做。 : 看到网上列出来很多方法 : http://en.wikipedia.org/wiki/Methods_of_computing_square_roots : 如果面试的时候,不知道哪个方法比较好。
|
p****o 发帖数: 46 | 5 弦切, 弦割什么区别?
我数值计算没怎么学,给科普一下吧.
【在 g*******y 的大作中提到】 : Babylonian method 这个跟弦切还是弦割(忘了是哪个)是等价的 : 面试的时候说一个就不错了,又不是面试数学家或者数值计算专家
|
m*****f 发帖数: 1243 | 6 怎么这么复杂....
简单的就是从0 试到 n/2 啊,改进就是在这个区域之间binary search.
我是不会弦切弦割法。。。
【在 g*******y 的大作中提到】 : 不需要BST吧 : 想想x^2 = a方程的数值解法(弦切,弦割法)
|
z*********8 发帖数: 2070 | 7 为什么不用迭代法呢?
看看游戏Quake里面的算法吧:
float SquareRootFloat(float number) {
long i;
float x, y;
const float f = 1.5F;
x = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( f - ( x * y * y ) );
y = y * ( f - ( x * y * y ) );
return number * y;
} |
m*****f 发帖数: 1243 | 8 i = 0x5f3759df - ( i >> 1 );
? |
z*********8 发帖数: 2070 | 9 嗯我也不知道这个magic number哪里来的, 所以才显示出这个算法的神奇和伟大
google一下或许会有解释
【在 m*****f 的大作中提到】 : i = 0x5f3759df - ( i >> 1 ); : ?
|
m*****f 发帖数: 1243 | 10 explaination can be found here http://en.wikipedia.org/wiki/Fast_inverse_square_root
but I guess I will not use this as an answer in an interview...how could I
explain to
the interviewer without understanding it...
【在 z*********8 的大作中提到】 : 嗯我也不知道这个magic number哪里来的, 所以才显示出这个算法的神奇和伟大 : google一下或许会有解释
|
|
|
g*******y 发帖数: 1930 | 11 有本事写出这样code的人,绝对不会上这个版的,甚至找工作都不需要面试,要么就是
若干公司恳求他去参观一下,我觉得。
【在 m*****f 的大作中提到】 : explaination can be found here http://en.wikipedia.org/wiki/Fast_inverse_square_root : but I guess I will not use this as an answer in an interview...how could I : explain to : the interviewer without understanding it...
|
k***e 发帖数: 556 | 12 quake
sigh 多年以前在学校里和同学鏖战
结果硬是被cs搞下去了
我猜magic number是和初始位置有关 哈哈
【在 z*********8 的大作中提到】 : 为什么不用迭代法呢? : 看看游戏Quake里面的算法吧: : float SquareRootFloat(float number) { : long i; : float x, y; : const float f = 1.5F; : x = number * 0.5F; : y = number; : i = * ( long * ) &y; : i = 0x5f3759df - ( i >> 1 );
|
a****n 发帖数: 1887 | 13 John Carmack 偶像啊,ID 的创始人,曾经每天16个小时coding, 坚持了十多年
30岁就进名人堂了,当年微软为了推directX 3.0, 盖茨专门找他咨询的,
有本关于ID software的传奇历史的书, DOOM启示录,很多关于他的内容
不过quake 3 之后他的兴趣转向航天了。。。
ID software 公布过很多他们的产品的source code, 因为JC 是忠实的open source 拥护者, 曾经试图读过他的code, 全是纯C写的,很难读。。。
【在 g*******y 的大作中提到】 : 有本事写出这样code的人,绝对不会上这个版的,甚至找工作都不需要面试,要么就是 : 若干公司恳求他去参观一下,我觉得。
|
f****b 发帖数: 486 | 14 景仰
【在 a****n 的大作中提到】 : John Carmack 偶像啊,ID 的创始人,曾经每天16个小时coding, 坚持了十多年 : 30岁就进名人堂了,当年微软为了推directX 3.0, 盖茨专门找他咨询的, : 有本关于ID software的传奇历史的书, DOOM启示录,很多关于他的内容 : 不过quake 3 之后他的兴趣转向航天了。。。 : ID software 公布过很多他们的产品的source code, 因为JC 是忠实的open source 拥护者, 曾经试图读过他的code, 全是纯C写的,很难读。。。
|
a****n 发帖数: 1887 | 15 算法中最常用的两种迭代
对于高次>1单调方程, 用牛顿迭代
对于低次<1单调方程, 二分搜索
平方根一般用牛顿迭代
JC 的code 也是牛顿迭代,只不过那个初始值选的太强了, 所以只迭代一次
但是误差还是蛮大的, 5/1000 左右, 对于quake 这种3D图像生成, 也足够了 |
H*M 发帖数: 1268 | 16 好久没见你上来了!
【在 a****n 的大作中提到】 : 算法中最常用的两种迭代 : 对于高次>1单调方程, 用牛顿迭代 : 对于低次<1单调方程, 二分搜索 : 平方根一般用牛顿迭代 : JC 的code 也是牛顿迭代,只不过那个初始值选的太强了, 所以只迭代一次 : 但是误差还是蛮大的, 5/1000 左右, 对于quake 这种3D图像生成, 也足够了
|
a****n 发帖数: 1887 | 17 最近找了点活做, 所以来的少了
【在 H*M 的大作中提到】 : 好久没见你上来了!
|
a********a 发帖数: 219 | 18 我不得不说,跑偏了。这不是在准备面试,这是走火入魔了。
【在 z*********8 的大作中提到】 : 为什么不用迭代法呢? : 看看游戏Quake里面的算法吧: : float SquareRootFloat(float number) { : long i; : float x, y; : const float f = 1.5F; : x = number * 0.5F; : y = number; : i = * ( long * ) &y; : i = 0x5f3759df - ( i >> 1 );
|
H*M 发帖数: 1268 | 19 上次想找你问点事来着
【在 a****n 的大作中提到】 : 最近找了点活做, 所以来的少了
|
c*****y 发帖数: 90 | 20 我想到的也是这个方法,不过你终止的判断是什么?我能想到的就是左右两点距离小于
某个数。
【在 m*****f 的大作中提到】 : 怎么这么复杂.... : 简单的就是从0 试到 n/2 啊,改进就是在这个区域之间binary search. : 我是不会弦切弦割法。。。
|
a****n 发帖数: 1887 | 21 给我留言吧, :),最近项目是在太忙, 没时间在版上挂着
【在 H*M 的大作中提到】 : 上次想找你问点事来着
|