注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

Java的BigInteger中的乘法真的是用FFT实现的吗?  

2011-03-12 19:21:54|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
曾经听说Java中的BigInteger的乘法是用fft实现的,比较快。通过poj上某些“高精度语言歧视题”后,我对此曾坚信不疑。

最近,我突然又开始研究高精度运算了。我想出了一个快速计算整数除法的思路,我目前能够做到一次2n位除以n位加取模的时间约为一次n位乘n位的8倍。
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/bigint.cpp
(内含乘法、除法、求sqrt(2)的演示程序。在我的机器上求sqrt(2)前1000000位用了20s)

为了测试我的程序的常数,我打算和Java的BigInteger作比较。
我的机器上java -version的结果是:
java version "1.6.0_22"
Java(TM) SE Runtime Environment (build 1.6.0_22-b04)
Java HotSpot(TM) Client VM (build 17.1-b03, mixed mode, sharing)
各个jre版本的实现可能不一样,我只实验了我用的这个版本的。

第一个实验:两个100000位相乘
BigInteger版 3.2秒。
我的程序 0.359秒。
我对此感到很震惊:难道我的常数就如此的小,以至于秒杀了BigInteger?
带着这个疑惑,我试验了一下200000位除以100000的除法
BigInteger版 4.8秒
我的程序 2.8秒
我感到十分惊讶:Java的BigInteger的除法是如何写的?怎么只比乘法慢那么点?

于是,我再做了50000位数相乘以及200000位数相乘,汇总如下:
位数 Java版用时 我写的FFT版用时
50000 0.9 0.156
100000 3.2 0.359
200000 11.5 0.825
很明显,数据规模增大一倍,我的程序时间约增长一倍,而BigInteger版的约增长3倍。
如果BigInteger的乘法和除法都是朴素乘除法,那么上面的实验数据以及除法的速度就很好解释了。
于是,我得到了一个令人心灰意冷的结论:BigInteger根本就不是用FFT实现的!

话说回来,即使是朴素乘法,BigInteger版也比我们自己手写的朴素乘法快了很多。
这是为什么呢?
我再次做了一个实验,发现,BigInteger的toString()的速度比multiply()还慢!
这说明,BigInteger中数是用非10进制的方式存储的。
我测试了一下,在用65536进制的情况下,朴素乘法就大约是BigInteger的速度了。


上面的实验都是针对我的windows的机器上的jre进行的。是否linux下的jre会有不同的表现呢?
值得我们去进一步探索。
  评论这张
 
阅读(2238)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017