真心请教如何计算sqrt(20.8)或者 exp(1.2)最快 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PDA - 掌中宝

真心请教如何计算sqrt(20.8)或者 exp(1.2)最快

真心请教如何计算sqrt(20.8)或者 exp(1.2)最快# PDA - 掌中宝

z*h2013-03-01 08:03

1 楼

16. [Microsft] 给出平面上第一象限内landscape 的轮廓，也就是一些列的(x,y)坐标
, x=0,1,...,N
，以及Y 轴上光源坐标(0,H)。问这N+1 个点钟那些被照亮那些是阴影。(叉乘)
一一计算光源到(x,y)的角度，再与左边的角度对比即可知是否被遮挡，复杂度O(N)
只需要与左边角度对比？O(N)?
我还是觉得必须n方阿。
哪位大牛指点一下？谢谢！

y*u2013-03-01 08:03

2 楼

我今天晚上哪都不去，吃过饭就上床，我要睡够１２小时

g*t2013-03-01 08:03

3 楼

前面说的AAPL某人当年的圆角矩形算法如何NB,
但我老从没听说过AAPL的办法.
谁能展开说说,或者给个link?
Thanks in advance

l*a2013-03-01 08:03

4 楼

我认为
每个点跟之前的极值点比较即可
所以是线性

【在 z****h 的大作中提到】

: 16. [Microsft] 给出平面上第一象限内landscape 的轮廓，也就是一些列的(x,y)坐标
: , x=0,1,...,N
: ，以及Y 轴上光源坐标(0,H)。问这N+1 个点钟那些被照亮那些是阴影。(叉乘)
: 一一计算光源到(x,y)的角度，再与左边的角度对比即可知是否被遮挡，复杂度O(N)
: 只需要与左边角度对比？O(N)?
: 我还是觉得必须n方阿。
: 哪位大牛指点一下？谢谢！

b*i2013-03-01 08:03

5 楼

【在 y*********u 的大作中提到】

: 我今天晚上哪都不去，吃过饭就上床，我要睡够１２小时

z*e2013-03-01 08:03

6 楼

e^1.2不就是cauchy多项式展开咯

【在 g****t 的大作中提到】

: 前面说的AAPL某人当年的圆角矩形算法如何NB,
: 但我老从没听说过AAPL的办法.
: 谁能展开说说,或者给个link?
: Thanks in advance

z*h2013-03-01 08:03

7 楼

请问什么是极值点？

l*o2013-03-01 08:03

8 楼

我也要睡觉。。。
昨天只睡了两个钟头，困死我了。。。

g*t2013-03-01 08:03

9 楼

啥叫cauchy多项式?
wiki没找到.我从没听说过.

e^1.2不就是cauchy多项式展开咯

【在 z*********e 的大作中提到】

: e^1.2不就是cauchy多项式展开咯

l*a2013-03-01 08:03

10 楼

(0,h) 与 (x,y)的角度/斜率。。

【在 l*****a 的大作中提到】

: 我认为
: 每个点跟之前的极值点比较即可
: 所以是线性

x*u2013-03-01 08:03

11 楼

ft
你做神仙?

【在 l*****o 的大作中提到】

: 我也要睡觉。。。
: 昨天只睡了两个钟头，困死我了。。。

z*e2013-03-01 08:03

12 楼

哈，好久没用连名字都搞错了，taylor展开挺好算吧，10来20级就差不多到精度极限了

【在 g****t 的大作中提到】

: 啥叫cauchy多项式?
: wiki没找到.我从没听说过.
:
: e^1.2不就是cauchy多项式展开咯

p*22013-03-01 08:03

13 楼

没看明白。几何的东西？

l*o2013-03-01 08:03

14 楼

不是神仙，是僵尸，恩。。。

【在 x********u 的大作中提到】

: ft
: 你做神仙?

l*s2013-03-01 08:03

15 楼

级数大学高数必教，可见以前的程序员很少读过本科。

【在 g****t 的大作中提到】

: 啥叫cauchy多项式?
: wiki没找到.我从没听说过.
:
: e^1.2不就是cauchy多项式展开咯

m*g2013-03-01 08:03

16 楼

blockedPoints = []
for point in points:
angle = getAngle(point, lightOrig)
allAngles[angle]++;
if allAngles[angle] > 1 :
blockedPoints += points

【在 z****h 的大作中提到】

t*g2013-03-01 08:03

17 楼

昨晚，第一觉1.5小时，第二觉5小时
我幸福死了

g*t2013-03-01 08:03

18 楼

tylor 展开很慢.
不可能比Newton法快.

哈，好久没用连名字都搞错了，taylor展开挺好算吧，10来20级就差不多到精度极限了

【在 z*********e 的大作中提到】

: 哈，好久没用连名字都搞错了，taylor展开挺好算吧，10来20级就差不多到精度极限了

A*l2013-03-01 08:03

19 楼

我连题目都没看懂，到底是N+1个“点”互相遮挡，还是这些点形成的多边形遮挡
另外这些点给出来的顺序也很重要，从左到右、从上到下顺时针、逆时针。。。
不过基本上是计算几何的问题

【在 z****h 的大作中提到】

x*u2013-03-01 08:03

20 楼

僵尸好象永远都在睡觉的,恩

【在 l*****o 的大作中提到】

: 不是神仙，是僵尸，恩。。。

g*t2013-03-01 08:03

21 楼

级数跟 cauchy多项式能有关系么.
人家说了写错名字,你发的感慨真扯.

级数大学高数必教，可见以前的程序员很少读过本科。

【在 l*********s 的大作中提到】

: 级数大学高数必教，可见以前的程序员很少读过本科。

G*e2013-03-01 08:03

22 楼

没看懂题

wh2013-03-01 08:03

23 楼

咋都这么累。我是过敏睡不好，很早就醒。大家都多睡点吧。

【在 l*****o 的大作中提到】

: 我也要睡觉。。。
: 昨天只睡了两个钟头，困死我了。。。

a*e2013-03-01 08:03

24 楼

压根不计算根号
用的是累加，就是X走一步Y走几步的问题
直线，斜率就是个常数
2次曲线，斜率就是个累加器，加个边界条件就齐活了
6~70年代的技术被不读文献的主再次发明了

【在 g****t 的大作中提到】

: 前面说的AAPL某人当年的圆角矩形算法如何NB,
: 但我老从没听说过AAPL的办法.
: 谁能展开说说,或者给个link?
: Thanks in advance

z*h2013-03-01 08:03

25 楼

多谢，这是空间换时间吧。
space O(n), time O(n).
不过从原作者描述好像是有space O(1) time O(n)的解法。。。

【在 m*****g 的大作中提到】

: blockedPoints = []
: for point in points:
: angle = getAngle(point, lightOrig)
: allAngles[angle]++;
: if allAngles[angle] > 1 :
: blockedPoints += points

p*i2013-03-01 08:03

26 楼

我昨天睡了11小时

g*t2013-03-01 08:03

27 楼

sqrt(x)不是你想的那么容易. exp(x)更难.

压根不计算根号
用的是累加，就是X走一步Y走几步的问题
直线，斜率就是个常数
2次曲线，斜率就是个累加器，加个边界条件就齐活了
6~70年代的技术被不读文献的主再次发明了

【在 a***e 的大作中提到】

: 压根不计算根号
: 用的是累加，就是X走一步Y走几步的问题
: 直线，斜率就是个常数
: 2次曲线，斜率就是个累加器，加个边界条件就齐活了
: 6~70年代的技术被不读文献的主再次发明了

z*h2013-03-01 08:03

28 楼

confused.不能只跟之前的极值比吧。比如 X1 (1,h), X2(3, h), .... Xi-1(49, h)
Xi(50,h)。Xi不会被Xi-1遮挡但是会被不相临的x1遮挡。

【在 l*****a 的大作中提到】

: 我认为
: 每个点跟之前的极值点比较即可
: 所以是线性

s*M2013-03-01 08:03

29 楼

tjjtds!!!!

【在 p********i 的大作中提到】

: 我昨天睡了11小时

l*s2013-03-01 08:03

30 楼

taylor公式的特殊形式往往有特定名称，甚至有时候同一个公式不同领域都有不同的叫
法，要是有gauchy那也毫不奇怪，我怎么知道他是记错了。

【在 g****t 的大作中提到】

: 级数跟 cauchy多项式能有关系么.
: 人家说了写错名字,你发的感慨真扯.
:
: 级数大学高数必教，可见以前的程序员很少读过本科。

z*h2013-03-01 08:03

31 楼

我是这样理解的。假设每个点都是一个物理点的实体，在光源照射后都有阴影，而且阴
影就是一条直线。如果有两个点和光源在一条直线上，离光源近的点被照亮，后面的点
被遮挡。比如光源在(0,h), x1( 1, h), x2(2, h)，x1被照亮，x2被遮挡。

【在 p*****2 的大作中提到】

: 没看明白。几何的东西？

p*i2013-03-01 08:03

32 楼

简写太复杂，强烈要求翻译

【在 s******M 的大作中提到】

: tjjtds!!!!

l*s2013-03-01 08:03

33 楼

sqrt有啥难度可言？

【在 g****t 的大作中提到】

: sqrt(x)不是你想的那么容易. exp(x)更难.
:
: 压根不计算根号
: 用的是累加，就是X走一步Y走几步的问题
: 直线，斜率就是个常数
: 2次曲线，斜率就是个累加器，加个边界条件就齐活了
: 6~70年代的技术被不读文献的主再次发明了

I*l2013-03-01 08:03

34 楼

If all the points are already sorted based on x-coordinate, then O(n) time
should be enough. Otherwise you need O(nlogn) time to first sort these
points and then process the n points from left to right and use a hash table
to store the blocked (or shadowed) angles.

【在 z****h 的大作中提到】

: 我是这样理解的。假设每个点都是一个物理点的实体，在光源照射后都有阴影，而且阴
: 影就是一条直线。如果有两个点和光源在一条直线上，离光源近的点被照亮，后面的点
: 被遮挡。比如光源在(0,h), x1( 1, h), x2(2, h)，x1被照亮，x2被遮挡。

y*u2013-03-01 08:03

35 楼

！！！！！！

【在 s******M 的大作中提到】

: tjjtds!!!!

g*t2013-03-01 08:03

36 楼

你要算的快,就不容易.
如果要在各种资源约束下trade off,更难.

sqrt有啥难度可言？

【在 l*********s 的大作中提到】

: sqrt有啥难度可言？

z*h2013-03-01 08:03

37 楼

就算按x排序了也不行吧。
光源(0,h), x1( 1, h), x2 ( 2, 1) .... xn (n, h)
x1会挡xn

table

【在 I*******l 的大作中提到】

: If all the points are already sorted based on x-coordinate, then O(n) time
: should be enough. Otherwise you need O(nlogn) time to first sort these
: points and then process the n points from left to right and use a hash table
: to store the blocked (or shadowed) angles.

b*r2013-03-01 08:03

38 楼

re
我昨晚起来两次check小兔崽子，一是怕他用药用得过去了(我老强迫症他睡过去)，二
是怕他要bb，一天没便昨天。结果人家不去，活着就好。

a*e2013-03-01 08:03

39 楼

俺说的是画图，压根不需要知道那个值

【在 g****t 的大作中提到】

I*l2013-03-01 08:03

40 楼

In this case, after processing x1, slope k=0 will be stored in the hash
table. Then xn knows it will be blocked.

【在 z****h 的大作中提到】

: 就算按x排序了也不行吧。
: 光源(0,h), x1( 1, h), x2 ( 2, 1) .... xn (n, h)
: x1会挡xn
:
: table

y*u2013-03-01 08:03

41 楼

同学们，我已经在被窝里啦，看着电视，灌着水，神仙日子呀

g*t2013-03-01 08:03

42 楼

你不知道值,就很可能画的不够圆啊.
误差会不会累积起来? 不同半径的圆，肯定是不同的最好fitting.
我本科还真做过工控机，带一支铅笔画图。就是你说的要计算x每走一步，
y走几步什么的。画在纸上一个圆。
当时学的日本人的code,忘了算法了。

俺说的是画图，压根不需要知道那个值

【在 a***e 的大作中提到】

: 俺说的是画图，压根不需要知道那个值

y*g2013-03-01 08:03

43 楼

只需用一个变量记录之前点中的最高点，每次与这个最高点比较即可。算法其余的部分
与楼主的想法一样。这样的复杂度是O（n）。

f*y2013-03-01 08:03

44 楼

真舒服呀~

【在 y*********u 的大作中提到】

: 同学们，我已经在被窝里啦，看着电视，灌着水，神仙日子呀

l*s2013-03-01 08:03

45 楼

就一加法，除法的迭代，两三行的小东西你还能雕出花来？还搞啥资源约束，不解。

【在 g****t 的大作中提到】

: 你要算的快,就不容易.
: 如果要在各种资源约束下trade off,更难.
:
: sqrt有啥难度可言？

l*o2013-03-01 08:03

46 楼

我刚遛狗归来，琢磨着干点啥呢。。。

r*n2013-03-01 08:03

47 楼

就牛顿法就好了，damped newton method, 收敛不要太快哈，每一个iteration 误差减
低99% 要更fancy的算法题参见convex optimization by boyd and vandenberghe
另外sqrt用taylor series做也不会慢，只要初始值不要太离谱

【在 g****t 的大作中提到】

A*a2013-03-01 08:03

48 楼

几乎每天睡到自然醒，哈哈哈哈哈。。。。

g*t2013-03-01 08:03

49 楼

你知道不知道IEEE 浮点数的设计是拿过图灵奖的？
这些东西的最底层优化，不一定是什么大东西。但也是专门的技术。
你不懂就对了。但最好别装懂。我老这个贴是真心请教AAPL当年的技术的。

就一加法，除法的迭代，两三行的小东西你还能雕出花来？还搞啥资源约束，不解。

【在 l*********s 的大作中提到】

: 就一加法，除法的迭代，两三行的小东西你还能雕出花来？还搞啥资源约束，不解。

b*i2013-03-01 08:03

50 楼

无语。。。

【在 l*****o 的大作中提到】

: 我刚遛狗归来，琢磨着干点啥呢。。。

z*e2013-03-01 08:03

51 楼

想到一个办法计算sqrt
迭代 x_{n+1} = a*x_n + b*1/x_n, a, b为常数
可以设计成x_n是个下降的数列，但是收敛到2*sqrt(a*b)
收敛速度不一定好了

b*i2013-03-01 08:03

52 楼

再次无语。。。

【在 A***a 的大作中提到】

: 几乎每天睡到自然醒，哈哈哈哈哈。。。。

g*t2013-03-01 08:03

53 楼

有截断误差的情况下，
damped newton method一定能收敛?
误差一定不会累积起来?

【在 r*********n 的大作中提到】

: 就牛顿法就好了，damped newton method, 收敛不要太快哈，每一个iteration 误差减
: 低99% 要更fancy的算法题参见convex optimization by boyd and vandenberghe
: 另外sqrt用taylor series做也不会慢，只要初始值不要太离谱

g*t2013-03-01 08:03

54 楼

你们说的收敛，都是理想实数。不是机器实数。
不控制异常，除法多半会出问题。

想到一个办法计算sqrt
迭代 x_{n+1} = a*x_n + b*1/x_n, a, b为常数
可以设计成x_n是个下降的数列，但是收敛到2*sqrt(a*b)
收敛速度不一定好了

【在 z*********e 的大作中提到】

: 想到一个办法计算sqrt
: 迭代 x_{n+1} = a*x_n + b*1/x_n, a, b为常数
: 可以设计成x_n是个下降的数列，但是收敛到2*sqrt(a*b)
: 收敛速度不一定好了

l*s2013-03-01 08:03

55 楼

误会了，我的意思是说这么浅显的东西你怎么都不懂。

【在 g****t 的大作中提到】

: 你知道不知道IEEE 浮点数的设计是拿过图灵奖的？
: 这些东西的最底层优化，不一定是什么大东西。但也是专门的技术。
: 你不懂就对了。但最好别装懂。我老这个贴是真心请教AAPL当年的技术的。
:
: 就一加法，除法的迭代，两三行的小东西你还能雕出花来？还搞啥资源约束，不解。

t*s2013-03-01 08:03

56 楼

为什么提到开根号？画圆用的都是整数，根本不开根号。

【在 g****t 的大作中提到】

l*n2013-03-01 08:03

57 楼

http://en.wikipedia.org/wiki/Midpoint_circle_algorithm
AAPL的人自称是自己又重新发明了次轮子.

【在 g****t 的大作中提到】

: 前面说的AAPL某人当年的圆角矩形算法如何NB,
: 但我老从没听说过AAPL的办法.
: 谁能展开说说,或者给个link?
: Thanks in advance

g*t2013-03-01 08:03

58 楼

前面有人说的，我也不理解为啥要算sqrt。

【在 t***s 的大作中提到】

: 为什么提到开根号？画圆用的都是整数，根本不开根号。

g*t2013-03-01 08:03

59 楼

1962年IBM,这个不可能和Mac早年的机器有关吧？
网上看来很多人就是喜欢以讹传讹阿。

http://en.wikipedia.org/wiki/Midpoint_circle_algorithm
AAPL的人自称是自己又重新发明了次轮子.

【在 l******n 的大作中提到】

: http://en.wikipedia.org/wiki/Midpoint_circle_algorithm
: AAPL的人自称是自己又重新发明了次轮子.

g*g2013-03-01 08:03

60 楼

这些数值计算里都讲过。都有现成的算法。近年估计有改进，但我想改进不会很大。

【在 g****t 的大作中提到】

: 你要算的快,就不容易.
: 如果要在各种资源约束下trade off,更难.
:
: sqrt有啥难度可言？

l*n2013-03-01 08:03

61 楼

jobs的自传说apple的某个工程师在不知道这个事情的情况下也搞出了这么个算法

【在 g****t 的大作中提到】

: 1962年IBM,这个不可能和Mac早年的机器有关吧？
: 网上看来很多人就是喜欢以讹传讹阿。
:
: http://en.wikipedia.org/wiki/Midpoint_circle_algorithm
: AAPL的人自称是自己又重新发明了次轮子.

g*t2013-03-01 08:03

62 楼

这个倒不是不可能。把问题描述往
数学版发一下，过几天说不定就有人
给解决掉。
你要给Terrace Tao发个email，说不定10分钟就解决了。

jobs的自传说apple的某个工程师在不知道这个事情的情况下也搞出了这么个算法

【在 l******n 的大作中提到】

: jobs的自传说apple的某个工程师在不知道这个事情的情况下也搞出了这么个算法

i*w2013-03-01 08:03

63 楼

jobs 是个sales/marketer
他自传是个writer写的
这路子事情当励志故事看即可

【在 l******n 的大作中提到】

: jobs的自传说apple的某个工程师在不知道这个事情的情况下也搞出了这么个算法

b*v2013-03-01 08:03

64 楼

预先算好，每次用的时候直接读取。

★ 发自iPhone App: ChineseWeb 7.8

【在 g****t 的大作中提到】

: 前面说的AAPL某人当年的圆角矩形算法如何NB,
: 但我老从没听说过AAPL的办法.
: 谁能展开说说,或者给个link?
: Thanks in advance

r*n2013-03-01 08:03

65 楼

it will converge and will converge quadratically when reasonably close to
the solution. for sqrt, it converges very very fast since x^2 itself is
quadratic.
error improves 2 digits very iteration.

【在 g****t 的大作中提到】

: 有截断误差的情况下，
: damped newton method一定能收敛?
: 误差一定不会累积起来?