V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zythum
V2EX  ›  程序员

朱一蛋疼的时候做的蛋疼之物 <-标题党

  •  
  •   zythum ·
    zythum · 2012-01-31 03:11:29 +08:00 · 4933 次点击
    这是一个创建于 4679 天前的主题,其中的信息可能已经有所发展或是发生改变。
    url: http://zythum.free.bg/PI

    或说这么算圆周率真的大丈夫?
    虽然用js算圆周率是很蛋疼的事情。而且这个算法无比的蛋疼。

    有木有什么好玩的算法呢?
    30 条回复    1970-01-01 08:00:00 +08:00
    greenymora
        1
    greenymora  
       2012-01-31 03:13:14 +08:00
    啊。在纠结计算时间的时候,看到这么一堆数字...
    真想去喝酒算了...为什么我会纠结在php里面...
    aeryen
        2
    aeryen  
       2012-01-31 04:53:24 +08:00
    作业党表示希望成为蛋疼党的一员,但是自己又忙又懒……
    Semidio
        3
    Semidio  
       2012-01-31 05:19:56 +08:00
    这个算法确实很蛋疼。
    yyfearth
        4
    yyfearth  
       2012-01-31 08:18:57 +08:00
    最好可以事实显示现在当前的点数和圈内的点数
    kuno
        5
    kuno  
       2012-01-31 08:49:37 +08:00
    如果点的分布是绝对平均的,最后不就是在计算圆的面积除以方形剩余的面积?
    zythum
        6
    zythum  
    OP
       2012-01-31 08:52:54 +08:00
    设圆的半径是R,那么圆的面积是R*R*PI,外面的正方形是2R*2R
    那么面积比是PI/4

    如果点是平均分布的,那么落在圆内的概率就是PI/4
    那么就可以算出来了.
    zythum
        7
    zythum  
    OP
       2012-01-31 08:57:38 +08:00
    @kuno 但是貌似这个随机数是伪随机啊...不过结果应该差不离把。
    至少js浮点数就那么多.
    makeabeeline
        8
    makeabeeline  
       2012-02-02 14:51:34 +08:00
    这是微积分投影法的应用哦
    aoyoo
        9
    aoyoo  
       2012-02-02 15:13:03 +08:00
    这算是蒙特卡罗算法么?
    zythum
        10
    zythum  
    OP
       2012-02-02 21:08:22 +08:00
    @aoyoo 我也不知道啊.
    cmonday
        11
    cmonday  
       2012-02-02 21:22:46 +08:00
    所以一切顺利的话最后就会很接近 Math.PI 了是么…… = =
    zythum
        12
    zythum  
    OP
       2012-02-02 21:23:38 +08:00
    @cmonday 别把实话说出来啊...
    zythum
        13
    zythum  
    OP
       2012-02-02 21:23:59 +08:00
    @cmonday 这是一种教学的思路。这个算个课件其实。
    cmonday
        14
    cmonday  
       2012-02-02 21:26:27 +08:00
    @zythum 原来是这样…… = =
    zythum
        15
    zythum  
    OP
       2012-02-02 21:28:39 +08:00
    @cmonday 话说怎么突破浮点的长度的拘束
    013231
        16
    013231  
       2012-02-02 21:37:03 +08:00
    没必要生成随机数. 遍历每一个点就可以了.
    http://gist.github.com/1723500
    zythum
        17
    zythum  
    OP
       2012-02-02 21:39:36 +08:00
    @013231 但是坐标是整数的话,半径要很宽才行。
    zythum
        18
    zythum  
    OP
       2012-02-02 21:40:59 +08:00
    @013231 而且这样按道理说是便利不完的。
    013231
        19
    013231  
       2012-02-02 21:48:47 +08:00
    @zythum 所谓"遍历"是指均匀的取样啦. 也不一定用整数啊, 换成浮点数也一样.
    http://gist.github.com/1723546
    zythum
        20
    zythum  
    OP
       2012-02-02 21:54:59 +08:00
    但是均匀遍历总感觉有问题... 你可以试试结果。
    因为随机数的话只要时间够久肯定是可以精确的。(排除js语言本身的问题)。

    但是均匀遍历这个算法不行。本身就有精确度上的问题
    zythum
        21
    zythum  
    OP
       2012-02-02 21:58:20 +08:00
    @013231 现在的问题怎么解决浮点数长度的拘束.
    cmonday
        22
    cmonday  
       2012-02-02 22:01:52 +08:00
    @zythum
    JS 要突破浮点数只能自己模拟了……以前学 C 的时候用过数组模拟大数类,理论上位数无限,就是效率差点。
    还可以用两个数拼一下,这样就跟 double 一样了。
    反正肯定要把加减乘除都重新封装一遍……很久没搞算法了,很头大啊 = =
    zythum
        23
    zythum  
    OP
       2012-02-02 22:03:49 +08:00
    @cmonday 我ACM什么的很渣很渣的
    cmonday
        24
    cmonday  
       2012-02-02 22:14:54 +08:00
    @zythum 大数类还算蛮好理解的,就是写起来比较麻烦,尤其是要考虑效率的情况下……
    我 Google 了一把果然有人拿 JS 写过大数的,这个是最基础的写法:
    http://www.silverna.org/blog/?p=67
    这里有个用 JS + 割圆法算圆周率的,你可以参考下:
    http://blog.csdn.net/ncs2002/article/details/429821
    zythum
        25
    zythum  
    OP
       2012-02-02 22:21:08 +08:00
    @cmonday 非常感谢。
    013231
        26
    013231  
       2012-02-02 22:25:43 +08:00
    @zythum 随机分布为什么会比均匀分布更精确? 均匀分布只要你划分的更细就可以算得更精确呀, 而且速度比随机分布快许多(不用生成随机数).
    以下是均匀分布的计算结果:
    1000 * 1000: 3.145520
    10000 * 10000: 3.141991
    100000 * 100000: 3.141633
    zythum
        27
    zythum  
    OP
       2012-02-02 22:35:49 +08:00
    @013231 举个例子把... 如果你均匀分布是间隔是0.1。那么就是0.1了。算完就完事了。如果要再精简的话要再算一次。而且只能全部算问才能知道结果。
    如果是随机的话。可以近似与多加一个个例的前后都是均匀分布的。只是均匀分布是间隔一直在取向去变小。那么只要随着个例的增多可以一直下去。每次都是一个近似的至,个例每增加就可以增加精确的程度。
    不知道朱一有木有说清楚。
    zythum
        28
    zythum  
    OP
       2012-02-02 22:36:50 +08:00
    @013231 再做着用永远没有头的运算事不要用绝对的值(这边是均匀分布的间隔).
    013231
        29
    013231  
       2012-02-02 22:56:05 +08:00
    @zythum 我知道, 随机取样的计算过程是"在线的", 这是它的优势. 我所说的是, 同样多取样点的状况下均匀取样同样可行且速度更快. 不过从另一个角度说, 用蒙特卡洛法进行PI的高精度运算本身就是蛋疼行为= =b
    eric_q
        30
    eric_q  
       2012-02-03 09:07:47 +08:00
    这东西真熟悉,8年前我在文曲星电子辞典上无聊时用BASIC编了个
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1629 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 16:58 · PVG 00:58 · LAX 08:58 · JFK 11:58
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.