Project1

标题: 超快的Java乘方算法在Ruby里面没用？？ [打印本页]
作者: 有丘直方    时间: 2018-8-23 10:20
标题: 超快的Java乘方算法在Ruby里面没用？？
你们知道我在搞RGSS的物理引擎
最近在研究JBox2D的源码
看到里面有这一段
JAVA 代码复制
  1. package org.jbox2d.common;
  2.  
  3. /**
  4.  * Contains methods from MathUtils that rely on JVM features. These are separated out from
  5.  * MathUtils so that they can be overridden when compiling for GWT.
  6.  */
  7. class PlatformMathUtils {
  8.  
  9.   private static final float SHIFT23 = 1 << 23;
  10.   private static final float INV_SHIFT23 = 1.0f / SHIFT23;
  11.  
  12.   public static final float fastPow(float a, float b) {
  13.     float x = Float.floatToRawIntBits(a);
  14.     x *= INV_SHIFT23;
  15.     x -= 127;
  16.     float y = x - (x >= 0 ? (int) x : (int) x - 1);
  17.     b *= x + (y - y * y) * 0.346607f;
  18.     y = b - (b >= 0 ? (int) b : (int) b - 1);
  19.     y = (y - y * y) * 0.33971f;
  20.     return Float.intBitsToFloat((int) ((b + 127 - y) * SHIFT23));
  21.   }
  22. }
这是个用于快速计算乘方的算法，精度不高，根号2算出来大概是1.415
为了测试这个算法到底有多快，我写了一段代码进行测试
JAVA 代码复制
  1. public class Test {
  2.  
  3.     private static final float SHIFT23 = 1 << 23;
  4.     private static final float INV_SHIFT23 = 1.0f / SHIFT23;
  5.  
  6.     public static final float fastPow(float a, float b) {
  7.       float x = Float.floatToRawIntBits(a);
  8.       x *= INV_SHIFT23;
  9.       x -= 127;
  10.       float y = x - (x >= 0 ? (int) x : (int) x - 1);
  11.       b *= x + (y - y * y) * 0.346607f;
  12.       y = b - (b >= 0 ? (int) b : (int) b - 1);
  13.       y = (y - y * y) * 0.33971f;
  14.       return Float.intBitsToFloat((int) ((b + 127 - y) * SHIFT23));
  15.     }
  16.  
  17.     public static long times(int timesCount, Runnable runnable) {
  18.         long time = System.currentTimeMillis();
  19.         for (int i = 0; i < timesCount; i++) {
  20.             runnable.run();
  21.         }
  22.         return System.currentTimeMillis() - time;
  23.     }
  24.  
  25.     public static void main(String[] args) {
  26.         System.out.println(Test.times(100000000, () -> Test.fastPow(1.5f, 3.0f)));
  27.         System.out.println(Test.times(100000000, () -> StrictMath.pow(1.5f, 3.0f)));
  28.     }
  29. }
原理是，执行一亿次新算法，输出消耗的时间，再执行一亿次StrictMath自带的算法，输出消耗时间
结果吓我一大跳：
代码复制
  1. 7
    

  2. 16918
新算法可以在7毫秒内执行一亿次乘方运算，比标准库自带算法快了2400多倍？
这么好的算法一定要移植到Ruby中用啊！
RUBY 代码复制
  1. SHIFT23 = (1 << 23).to_f
  2. INV_SHIFT23 = 1.0 / SHIFT23
  3. def fast_pow(a, b)
  4.   x = a.int_bits
  5.   x *= INV_SHIFT23
  6.   x -= 0x7f
  7.   y = x - (x >= 0 ? x.to_i : x.to_i - 1)
  8.   b *= x + (y - y * y) * 0.346607
  9.   y = b - (b >= 0 ? b.to_i : b.to_i - 1)
  10.   y = (y - y * y) * 0.33971
  11.   Float.get_from_int_bits(((b + 0x7f - y) * SHIFT23).to_i)
  12. end
  13. class Float
  14.   def int_bits
  15.     [self].pack('g').unpack('B*').first.to_i(2)
  16.   end
  17.   class << self
  18.     def get_from_int_bits(i)
  19.       [sprintf("%032b", i)].pack('B*').unpack('g').first
  20.     end
  21.   end
  22. end
  23. def times(n, &block)
  24.   time = Time.now
  25.   n.times(&block)
  26.   Time.now - time
  27. end
  28.  
  29. puts(times(100000000) { fast_pow(1.5, 3.0) })
  30. puts(times(100000000) { 1.5 ** 3.0 })
代码内还附带了根据IEEE 754浮点“单一格式”位布局返回指定浮点值的表示形式的方法，和返回对应于给定位表示形式的浮点数值的方法
运行结果再次让我大吃一惊：
代码复制
  1. 223.896929
    

  2. 8.523068
作者: guoxiaomi    时间: 2018-8-23 13:28
本帖最后由 guoxiaomi 于 2018-8-23 13:53 编辑

虽然不知道为什么，但是你这个程序算出来的
  1. fast_pow(1.5, 3.0) = 3.395968437194824
  2. 1.5 ** 3.0 = 3.375
复制代码


测试了一下，其中fast_pow2是把第7和9行改成了 y = x % 1和 y = b % 1
RUBY 代码复制
  1. Benchmark.bm(10) do |t|
  2.   t.report('**_pow'){
  3.     1_000_000.times{1.5 ** 3.0}
  4.   }
  5.   t.report('fast_pow'){
  6.     1_000_000.times{fast_pow(1.5, 3.0)}
  7.   }
  8.   t.report('fast_pow2'){
  9.     1_000_000.times{fast_pow2(1.5, 3.0)}
  10.   }
  11.   a = 1.5
  12.   t.report('init_bits'){
  13.     1_000_000.times{x = a.int_bits}
  14.   }
  15.   b = 3.0
  16.   y = 0.06197100837140948
  17.   t.report('get_from'){
  18.     1_000_000.times{Float.get_from_int_bits(((b + 0x7f - y) * SHIFT23).to_i)}
  19.   }
  20. end
结果如下：
代码复制
  1. user     system      total        real
    

  2. **_pow       0.093000   0.000000   0.093000 (  0.092967)
    

  3. fast_pow     2.485000   0.000000   2.485000 (  2.485887)
    

  4. fast_pow2    2.406000   0.000000   2.406000 (  2.417023)
    

  5. init_bits    0.625000   0.000000   0.625000 (  0.621773)
    

  6. get_from     1.453000   0.000000   1.453000 (  1.463776)






欢迎光临 Project1 (https://rpg.blue/) Powered by Discuz! X3.1