Mar 22, 2017

一次算PI的小尝试

最近看到一个算 PI 的小方法，不是很高效，但是我觉得很有意思，原理(蒙特卡罗方法)也非常简单，概括就是：

已知 1*1 正方形面积为1，半径为 1 的圆的面积为 π，1/4 圆正好可以放在小正方形里，它的面积与正方形面积比为 π/4，假设小正方形内有 M 个随机点，存在于圆内的点为 N，那么 N/M = π/4，可得

π =  N / M * 4

可以写一个非常简单 JS 测试一下

function calc (count) {
  var start = new Date()
  var x
  var y
  var inCount = 0
  for (var i = 0; i < count; i++) {
    x = Math.random()
    y = Math.random()
    // 判断点是否在1/4圆里
    if (Math.sqrt(x * x + y * y) <= 1) {
      inCount++
    }
  }

  var result = inCount / count * 4
  var spent = new Date() - start
  console.log('result: %d, count: %d, spent: %dms, rate: %d%', 
    result, count, spent, Math.abs((result-Math.PI)/Math.PI)*100)
}

calc(10)
calc(100)
calc(1000)
calc(10000)
calc(100000)
calc(1000000)
calc(10000000)

跑一下可以看到结果

// MacBook Pro (Retina, 13-inch, Early 2015)
result: 3.2, count: 10, spent: 0ms, rate: 1.8591635788130243%
result: 3.16, count: 100, spent: 0ms, rate: 0.5859240340778606%
result: 3.24, count: 1000, spent: 1ms, rate: 3.1324031235481886%
result: 3.132, count: 10000, spent: 3ms, rate: 0.30534364723675406%
result: 3.13108, count: 100000, spent: 3ms, rate: 0.33462815676567087%
result: 3.141116, count: 1000000, spent: 28ms, rate: 0.015172354991620658%
result: 3.14161, count: 10000000, spent: 248ms, rate: 0.0005521533858654934%

1000万次的时候误差已经比较小，如果写一个 C 的程序跑一下看看会是怎么样呢，于是我就又写了一个 C 的版本(原理一模一样，单纯用 C 实现一下)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

void calc( int count ){
  clock_t begin = clock();
  double x;
  double y;

  int inCount = 0;
  for (int i = 0; i < count; i++) {
    x = (double) rand() / RAND_MAX;
    y = (double) rand() / RAND_MAX;
    if (sqrt(x * x + y * y) <= 1) {
      inCount++;
    }
  }

  double result = (double) inCount / count * 4;
  clock_t end = clock();
  double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  printf("result: %f, count: %d, spent:%fms, rate:%f%%\n", 
    result, count, time_spent*1000, fabs((result - M_PI)/ M_PI)*100 );
}


int main(){
  int count;
  srand((int)time(NULL));

  calc(10);
  calc(100);
  calc(1000);
  calc(10000);
  calc(100000);
  calc(1000000);
  calc(10000000);

  return 0;
}

因为好多年没写 C 了，其实 C 也不是太会，这里 search and copy 了不少代码，用 vscode 写的时候还发生了内存被吃完的囧况，gcc -o calc calc.c; ./calc 运行这后得到：

result: 3.600000, count: 10, spent:0.007000ms, rate:14.591559%
result: 3.240000, count: 100, spent:0.004000ms, rate:3.132403%
result: 3.096000, count: 1000, spent:0.027000ms, rate:1.451259%
result: 3.140800, count: 10000, spent:0.261000ms, rate:0.025231%
result: 3.149760, count: 100000, spent:2.531000ms, rate:0.259975%
result: 3.141932, count: 1000000, spent:23.312000ms, rate:0.010802%
result: 3.141936, count: 10000000, spent:230.223000ms, rate:0.010916%

真是让人悲伤，这个结果居然和 JS 差不多，经过一个帅的闪光的小同事指点后，原来是编译的时候没有加优化参数，calc 其实是个 debug 版的，重新用 gcc -O3 -o calc calc.c; ./calc 运行一下：

result: 3.200000, count: 10, spent:0.004000ms, rate:1.859164%
result: 3.120000, count: 100, spent:0.002000ms, rate:0.687316%
result: 3.200000, count: 1000, spent:0.013000ms, rate:1.859164%
result: 3.144800, count: 10000, spent:0.144000ms, rate:0.102093%
result: 3.147080, count: 100000, spent:1.481000ms, rate:0.174668%
result: 3.143316, count: 1000000, spent:13.987000ms, rate:0.054856%
result: 3.141480, count: 10000000, spent:138.983000ms, rate:0.003586%

这么一看差不多是 JS 版的 2 倍，这就正常点了，最近 WebAssembly，比较火，正好可以也尝试一下，按照官方的guide clone 了源码并安装，因为安装过程要去 github 和 s3 下载几百兆的东西，会比较慢，需要翻墙外加很有耐心，安装完成后 emcc calc.c -s WASM=1 -o calc.html，会生成对应的calc.html, calc.wasm, calc.js，因为calc.html里获取 calc.wasm 是用xhr获取的，执行这个文件，需要本地起一个小静态服务，用 Firefox 52 打开之后执行的结果如下：

result: 2.800000, count: 10, spent:0.000000ms, rate:10.873232%
result: 3.120000, count: 100, spent:0.000000ms, rate:0.687316%
result: 3.208000, count: 1000, spent:0.000000ms, rate:2.113811%
result: 3.149200, count: 10000, spent:1.000000ms, rate:0.242149%
result: 3.148920, count: 100000, spent:2.000000ms, rate:0.233237%
result: 3.143232, count: 1000000, spent:13.000000ms, rate:0.052182%
result: 3.141560, count: 10000000, spent:132.000000ms, rate:0.001027%

基本上和 C 编译后的性能差不多，性能非常给力，关于 WebAssembly 更多的知识非常推荐看 a-cartoon-intro-to-webassembly。

总结一下：一次小尝试，额外测试了一下 WebAssembly，性能非常好，目前 Web 上饱受性能折磨的游戏也许能从 WebAssembly 的普及中获得大量好处，但是鉴于编译后的 WebAssembly 调试工具并没有配套发展起来，同时在浏览器端需要高性能的场景也并不是特别常见，普及可能还需要些时日。

一次算PI的小尝试

推荐文章