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 的大作中提到】
: 上次想找你问点事来着
|
