《用Java实现超大Fibonacci数的计算.pdf》由会员分享，可在线阅读，更多相关《用Java实现超大Fibonacci数的计算.pdf（2页珍藏版）》请在三一文库上搜索。
1、1 2 0 福 建 电脑 2 0 1 0年第 9期 用 J a v a实现超大 F i b o n a c c i 冯 ( 福 州大学至诚 学院 数的计算 新 福 建 福 州 3 5 0 0 2 5 1 【 摘 要】 ：F i b o n a c c i 数列的理论在初等数学、 组合数 学、 运筹学以及最优化理论中已经被广泛应用 同 时它在信 息隐藏、 密码学等方 面q - &有着重要 的应用， 在 实际使用中， 常常需要较大的 F i b o n a c c i 数。本文 讨论 了几种 F i b o n a c c i 数 的实现算法， 并用J a v a实现 了超大 F i b o n
2、a c c i 数的计算。 【 关键词】 ：F i b o n a c c i 数； 超大整数；J a v a 1 、 引言 1 3世纪意大利数学家 F i b o n a c c i 在他的名著 算盘 全 书 中提 出 了一个 关 于兔子 繁殖 的问题 ： 初始 有雌 雄 兔子一对 假定过两月便可繁殖雌雄各一的一对幼兔 f 假定不发生死亡1 ，问第 n个月时共有多少对兔子? 由 此 引 出了一个 充 满 奇趣 的数列 一 F i b o n a c c i 数 列本 文 用 F n表 示第 n个 F i b o n a c c i 数 其数学 定 义如下 ： F o ： 1 F 1 = l
3、， F = F - 1 十 F ( n 1 ) 。 从最 初 的兔子 问题 开始 历经 七百 多年 F i b o n a c c i 数列 的理论 在初 等数 学 、 组合 数学 、 运筹 学 以及最 优 化 理论中已经被广泛应用 ， 同时它在信息隐藏 、 密码学等 方面中也有着重要 的应用。 在实际使用中， 常常需要较 大的 F i b o n a c c i 数 F n ，对于 目前 的 i n t 型 ， 3 2位计算机 只能计算到 F 4 5 ； 对于 i n t 6 4型， 也只能计算到 F 9 。由 于 J a v a提供了 B i g I n t e g e r 类 在内存足够
4、大的情况下 能实现任意精度 的大数计算 故本文使用 J a v a来实现 超 大 F i b o n a c c i 数 。 2 、 F i b o n a c c i 数列 的实 现算 法及 时 间复杂性 分析 2 1逐项递归算法 f 1 n：0 1 根 据 定 义 1 一 + 一： i ( ) 其 J a v a 实现如下 ： p u b li c s t a t ic B i g l n t e g e r fi b o ( i n t n ) l if ( u I 时可得二分求解公式 ： = F麦 2 麓 【 + 一 为 偶 数 由于该算法的递归实现有些值需重复计算 如计 算 F 加需
5、要先算出 F 。 和 F ， 而计算 F 需要计算 F 7 和 F ， 计算 F 我们仍需计算 F 和 F ， 所以本算法采用备 忘录 的方 法米 避免 重复计 算所 造成 的开销 对分递归算法对于任意的 F n 我们只需要计算出 和 ， 其时间复杂度为 ： O( 1 o g ( n ) ) 2 3直接求值法 直接求值 的计算式在数学中称 为比内 ( B i n e t ) 公 式 ： = 1 1+ x 一 c 2 0 1 0年第 9期 福建 电脑 1 2 1 直接求值法不需计算第 1 3 项以外的其它项 。直接 算出第 n项 ， 时间复杂度为 0( 1 ) ， 看起来应当很快 ， 但 由于其
6、使用开方和幂运算 ， 在 n较大时 ， 执行效率并不 高。同时 由于精度限制 ， 在 n取较大值时 ， 无法计算 出 精确值 。 2 4迭代算法 迭代算法是 F i b o n a c c i 数列最简单 ，最 自然的一种 算法 计算公式为： F 0 = l ， F l =1 当 n = 2时 ， 迭代执行( 4 ) 式执行 n 一 1 次 f F= F 0 + = (4 ) 【 = F p u b l i c s t a t i c B i g l n te g e r fi b o ( i n t n ) Big l n t e g c r f 0=Big l n te g e r ON
7、E ； B i g l n t c g e r f l=Big l n t e g e r O NE ； Big l n t e g e r f：B i g l n t e g e r v a l u e Of( 2 ) ； f o r ( i n t i =2 ； i = 2时 ， In= n 2 ， 执 行 ( 4 ) 式 i n 一 1次 后 得 F m和 F r - 1 。则 F ：j + 2 F F m 一 为 奇 数 l + 碌 为偶数 ( 5 ) p u b l i c s t a t i c B i g l n t e g e r fi b o ( i n t n ) i n
8、t m=n 2 ； B i g l n t e g e r f 0=B i g l n t c g c r ON E； Bi g l n te g e r f l=B i g l n t e g e r ON E； B i g l n te g e r f =B i g l n t e g e r v a l u e O f ( 2 ) ； f o r ( i n t i =2 ； i =m ； i + + ) f=f 0 a d d ( f 1 ) ； f 0=f l ； ( 上接第 1 0 5页) f l=i ： 】 B i g l n t e g e r T WO=B i g I n t
9、 e g e r v a l u e O f ( 2 ) ； n 2 = =1 ) r e t u r n f 1 m u h i p l y ( f 1 ) a d d ( f 1 m u l t i p l y ( f O m u l t i p l y ( T WO ) ) ) ； e l s e r e t u r n f 1 m u l t i p l y ( f 1 ) ,i d ( f O m u h i p l y ( f O ) ) ； J 这种算法在计算 f n 时 ， 先用迭代方程计算 及它 前面一项 ， 然后利用公式 ( 5 ) 得到 F n 。由于在计算 F n 时
10、并不是把它前面的所有项都计算出来 大约只计算 它们的一半 。 从而大大减少了迭代所花费的时间。 其时 间复杂度为： O ( n 2 1 3 、 实验 结果 和结 论 以下是在 C P U为双核 2 0 G内存为 2 G的计算机 上 运 行 ， 分 别 用 逐项 递 归 算法 ， 对 分递 归算 法 ， 直 接 求 值算 法 迭代 算法 和对分递 归算法 计算 不 同的 F i b o n a c c i 数所 需 的时 问 ( 表 1 ) 。实 验结 果 表 明逐项 递 归 算 法在 计 算 F 4 5时 就 需 要 两分 钟 以 上 不 适 用 于 F i b o n a c c i 大数计
11、算 ： 在计算 F I O 0 0 0时 直接求值算法需 要 5秒钟 且得不到精确值 也不适 用于 F i b o n a c c i 大 数计算 ：而对分递归算法在计算 F 1 0 0 0 0 0时只需要 0 2 5秒。 是计算超大 F i b o n a c c i 数的最好选择。 4 5 10 O O 1 万 l 0 万 50 万 逐项递 归算法 1 3 8 3 5 9 对分递 归算法 1 1 1 5 2 5 O 5 6 7 2 直接求值算法 1 7 9 5 2 1 9 迭代算法 1 1 3 l l 3 5 9 3 3 1 2 5 对分迭代算法 1 1 1 5 5 4 7 1 2 0 4
12、 7 表 1几种算法计算 F i b o n a c c i 数 的时 间 ( 单 位 ： m s ) 注： ” 一 ” 表示不可计算 参考文献： 【 1 】陈莲娜， 梁 自力 超 大 F i h o n a c c i 数 的快速迭代算 法U 】 中国计 量学院学报 ， 2 0 0 7 w， 1 8 ( 3 ) ：2 2 5 2 2 7 【 2 粱艳楠， F i b o n a c c i 数列 的推 广与 应用 D 】 大连 ： 大连 理 工大 学 2 0 0 8 【 3 】 赵学森 计算 F i b o n a c c i 数 的对分迭代算法卟 计算机 工程 与应 用技术 2 0 0 3
13、 ( 2 2 ) ： 9 8 - 1 0 2 【 4 】李晓虹 ， 李世 奇 ， 杨有 F i b o n a c c i 大数计算及搜 索算法改进 重庆文理 学院 学报 ( 自然科 学版) ，2 0 0 6 ， 5 ( 4 ) ：2 7 3 0 参考文献： 【 2 】 E s c h e n a u e r L ， G l i g o r V A k e y ma n a g e me n t s c h e me f o r d i s t r i b u t e d s e n s o r n e t wo r k s I n ：Pr o c o f t he 9 t h ACM Co
14、n o n Co mp u t e r a n d Co mmu n i c a t i o n s S e c u r i t y Ne w Yo r k ： ACM P r e s s 20 0 241 -47 v 3 C h a n H，P e r r i g A ，S o n g DRa n d o m k e y p r e d i s t r i b u t i o n s c h e me s for s e n s or ne tw or ksI n：Pr oc of t he 20 03 I EEE S y mpon S e c u r i t y a n d P ri v
15、a c y W a s h i n g t o n ：I E E E Co mp u t e r S o c i e ty，2 0 0 3 1 97 21 3 r 7 】S h a m i r A HO W t o s h a r e a s e c r e t Co mmu n i c a t l o i I s o f t I l e A C M， 1 9 7 9 ， 2 2 ( 1 1 ) ： 6 1 2 6 1 3 6 6 Ne u ma n BC ， T s o T K e r b e r o s ： A n a u t l l e n t i c a t i o n s e r v i c e f o r c o mp u t e r n e tw o r ksI E E E Co mmu n i c a t i o n s ， 1 9 9 4 ， 3 2 ( 9 ) ： 3 3 3 8