设为首页收藏本站|繁體中文

Project1

 找回密码
 注册会员
搜索
查看: 1680|回复: 4

[胡扯] 超快的Java乘方算法在Ruby里面没用??

[复制链接]

Lv3.寻梦者

梦石
0
星屑
1934
在线时间
403 小时
注册时间
2015-8-30
帖子
395
发表于 2018-8-23 10:20:39 | 显示全部楼层 |阅读模式

加入我们,或者,欢迎回来。

您需要 登录 才可以下载或查看,没有帐号?注册会员

x
你们知道我在搞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
小仙女一枚~

Lv5.捕梦者 (版主)

梦石
1
星屑
23963
在线时间
3338 小时
注册时间
2011-7-8
帖子
3925

开拓者

发表于 2018-8-23 13:28:43 | 显示全部楼层
本帖最后由 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)


点评

似乎Ruby的pack和unpack太慢了  发表于 2018-8-24 14:00
对,但是这里的分析表明float和int的转换才是大头,计算本身并没有这么明显  发表于 2018-8-24 13:03
fast_pow(1.5, 3.0) == 3.396 是精度低造成的,我自己测试的时候也发现了  发表于 2018-8-23 14:28
熟悉rgss和ruby,xp区版主~
正在填坑:《膜拜组传奇》讲述膜拜组和学霸们的故事。
已上steam:与TXBD合作的Reformers《变革者》
* 战斗调用公共事件 *
* RGSOS 网络脚本 *
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册会员

本版积分规则

拿上你的纸笔,建造一个属于你的梦想世界,加入吧。
 注册会员
找回密码

站长信箱:[email protected]|手机版|小黑屋|无图版|Project1游戏制作

GMT+8, 2024-3-29 21:57

Powered by Discuz! X3.1

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表