基于FPGA的零误差大数阶乘算法的设计与实现
|
摘要
随着大数据时代的到来,人们对超高精度科学计算的需求日益迫切,其中一个难点是大数阶乘问题.斯特林公式作为计算大数阶乘的传统近似方法,远不能在精度上满足要求,其它的阶乘算法可以实现较高的精度,但以牺牲大量存储空间为代价.本文提出一种具有零误差的大数阶乘算法,可以根据问题规模优化存储空间,利用并行计算的思想和FPGA的优势来提高计算速度,测试结果表明,所提出的算法具有较好的时空效率,可以应用在如大数阶乘计算器等诸多领域.
With the advent of the era of big data,there is an increasingly urgent need for ultra-high precision scientific calculation.One of the difficulties is the large number factorial problem.Stirling formula as the traditional approximate method of calculating factorial of large numbers cannot meet the accuracy requirements.Other factorial algorithm can achieve high accuracy,but at the cost of a large amount of storage space.This paper puts forward a factorial algorithm of large numbers with zero error that can optimize storage space according to the problem size.Besides,the computing speed can be improved by making full use of parallel computing and the advantages of field programmable gate array(FPGA).The test results show that the proposed algorithm has better efficiency of time and space,which can be used in many fields such as large factorial calculator.
With the advent of the era of big data,there is an increasingly urgent need for ultra-high precision scientific calculation.One of the difficulties is the large number factorial problem.Stirling formula as the traditional approximate method of calculating factorial of large numbers cannot meet the accuracy requirements.Other factorial algorithm can achieve high accuracy,but at the cost of a large amount of storage space.This paper puts forward a factorial algorithm of large numbers with zero error that can optimize storage space according to the problem size.Besides,the computing speed can be improved by making full use of parallel computing and the advantages of field programmable gate array(FPGA).The test results show that the proposed algorithm has better efficiency of time and space,which can be used in many fields such as large factorial calculator.
引文
[1] SCHEID F J.Schaum’s Outline of Theory and Problems of Numerical Analysis[M].New York,NY,USA:McGraw-Hill,1989.7-50.
[2] WANG C,YUEH,YIN C,et al.Arithmetic operations beyond floating point number precision[J].International Journal of Computational Science and Engineering,2010,6(3):206-215.
[3] MEZMAZ M,LEROY R,MELAB N,et al.A multi-core parallel branch-and-bound algorithm using factorial number system[A].Proceedings of IEEE 28th International Parallel and Distributed Processing Symposium[C].Phoenix,AZ,USA:IEEE,2014.1203-1212.
[4] 马旭,王大勇.大数的阶乘与自然对数的超高精度求解[J].计算机与现代化,2017,(3):51-53.MA X,WANG D Y.Factorial of large number and super high precision solution of natural logarithm[J].Computer and Modernization,2017,(3):51-53.(in Chinese)
[5] UY R L,MARCOS N.On the complexity of implementation of recursion on Factorial and Fibonacci algorithms using RISC-based MIPS64 instruction set architecture[A].Proceedings of TENCON 2015 IEEE Region 10 Conference[C].Macao,China:IEEE,2016.1-6.
[6] FATEMAN R J.Comments on Factorial Programs,2006[OL].https://www.pdf-archive.com/2016/10/07/ factorial-pdf0/factorial-pdf0.pdf,2018-10-16.
[7] 英昌盛,周喜龙.大整数乘法的数据结构及算法选择探究[J].长春工业大学学报,2008,29(2):204-207.YING C S,ZHOU X L.Data structure and algorithm selection of big integer multiplication[J].Journal of Changchun University of Tchnology (Natural Science Edition),2008,29(2):204-207.(in Chinese)
[8] PETER L.Factorial Prime Swing[OL].http://www.luschny.de/math/factorial/,2018-10-16.
[9] 张柳,崔晓平,董文雯.高性能并行全冗余十进制乘法器的设计[J].电子学报,2018,46(6):1519-1523.ZHANG L,CUI X-P,DONG W-W.High-performance parallel fully redundant decimal multiplier[J].Acta Electronica Sinica,2018,46(6):1519-1523.(in Chinese)
[10] 李俊志,关杰.非线性反馈移存器型序列密码的完全性通用算法研究[J].电子学报,2018,46(9):2075-2080.LI J-J,GUAN J.Universal algorithm of full diffusion of stream cipher based on nonlinear feedback shift register[J].Acta Electronica Sinica,2018,46(9):2075-2080.(in Chinese)
[11] 李康,李亚敏,胡学敏,邵芳.基于卷积神经网络的鲁棒高精度目标跟踪算法[J].电子学报,2018,46(9):2087-2093.LI K,LI Y-M,HU X-M,SHAO F.A robust and accurate object tracking algorithm based on convolutional neural network[J].Acta Electronica Sinica,2018,46(9):2087-2093.(in Chinese)
[12] 李玮,张大方,黄昆,等.面向大数据处理的高精度多维计数布鲁姆过滤器[J].电子学报,2015,43(4):652-657.LI W,ZHANG D-F,HUANG K,et al.Accurate multi-dimension counting bloom filter for big data processing[J].Acta Electronica Sinica,2015,43(4):652-657.(in Chinese)
[13] 蒋帅,汪丙南,李银伟.一种用于InSAR/INS组合导航的姿态角反演方法[J].电子学报,2018,46(3):513-519.JIANG S,WANG B-N,LI Y-W.An inversion method of the attitude for InSAR/INS integrated navigation[J].Acta Electronica Sinica,2018,46(3):513-519.(in Chinese)
[14] LIU G,SHI L.Adaptive algorithm of magnetic heading detection[J].Measurement Science and Technology,2017,28(11):115101.
[15] LIU G,SHI L-F,XUN J,CHEN S,ZHAO L,SHI Y.Orientation estimation algorithm based on multi-source information fusion[J].Measurement Science and Technology,2018,29(11):115101.
[16] 刘公绪,史凌峰.室内导航与定位技术发展综述[J].导航定位学报,2018,6(2):7-14.LIU G X,SHI L F.An overview about development of indoor navigation and positioning technology[J].Journal of Navigation and Positioning,2018,6(2):7-14.(in Chinese)
[2] WANG C,YUEH,YIN C,et al.Arithmetic operations beyond floating point number precision[J].International Journal of Computational Science and Engineering,2010,6(3):206-215.
[3] MEZMAZ M,LEROY R,MELAB N,et al.A multi-core parallel branch-and-bound algorithm using factorial number system[A].Proceedings of IEEE 28th International Parallel and Distributed Processing Symposium[C].Phoenix,AZ,USA:IEEE,2014.1203-1212.
[4] 马旭,王大勇.大数的阶乘与自然对数的超高精度求解[J].计算机与现代化,2017,(3):51-53.MA X,WANG D Y.Factorial of large number and super high precision solution of natural logarithm[J].Computer and Modernization,2017,(3):51-53.(in Chinese)
[5] UY R L,MARCOS N.On the complexity of implementation of recursion on Factorial and Fibonacci algorithms using RISC-based MIPS64 instruction set architecture[A].Proceedings of TENCON 2015 IEEE Region 10 Conference[C].Macao,China:IEEE,2016.1-6.
[6] FATEMAN R J.Comments on Factorial Programs,2006[OL].https://www.pdf-archive.com/2016/10/07/ factorial-pdf0/factorial-pdf0.pdf,2018-10-16.
[7] 英昌盛,周喜龙.大整数乘法的数据结构及算法选择探究[J].长春工业大学学报,2008,29(2):204-207.YING C S,ZHOU X L.Data structure and algorithm selection of big integer multiplication[J].Journal of Changchun University of Tchnology (Natural Science Edition),2008,29(2):204-207.(in Chinese)
[8] PETER L.Factorial Prime Swing[OL].http://www.luschny.de/math/factorial/,2018-10-16.
[9] 张柳,崔晓平,董文雯.高性能并行全冗余十进制乘法器的设计[J].电子学报,2018,46(6):1519-1523.ZHANG L,CUI X-P,DONG W-W.High-performance parallel fully redundant decimal multiplier[J].Acta Electronica Sinica,2018,46(6):1519-1523.(in Chinese)
[10] 李俊志,关杰.非线性反馈移存器型序列密码的完全性通用算法研究[J].电子学报,2018,46(9):2075-2080.LI J-J,GUAN J.Universal algorithm of full diffusion of stream cipher based on nonlinear feedback shift register[J].Acta Electronica Sinica,2018,46(9):2075-2080.(in Chinese)
[11] 李康,李亚敏,胡学敏,邵芳.基于卷积神经网络的鲁棒高精度目标跟踪算法[J].电子学报,2018,46(9):2087-2093.LI K,LI Y-M,HU X-M,SHAO F.A robust and accurate object tracking algorithm based on convolutional neural network[J].Acta Electronica Sinica,2018,46(9):2087-2093.(in Chinese)
[12] 李玮,张大方,黄昆,等.面向大数据处理的高精度多维计数布鲁姆过滤器[J].电子学报,2015,43(4):652-657.LI W,ZHANG D-F,HUANG K,et al.Accurate multi-dimension counting bloom filter for big data processing[J].Acta Electronica Sinica,2015,43(4):652-657.(in Chinese)
[13] 蒋帅,汪丙南,李银伟.一种用于InSAR/INS组合导航的姿态角反演方法[J].电子学报,2018,46(3):513-519.JIANG S,WANG B-N,LI Y-W.An inversion method of the attitude for InSAR/INS integrated navigation[J].Acta Electronica Sinica,2018,46(3):513-519.(in Chinese)
[14] LIU G,SHI L.Adaptive algorithm of magnetic heading detection[J].Measurement Science and Technology,2017,28(11):115101.
[15] LIU G,SHI L-F,XUN J,CHEN S,ZHAO L,SHI Y.Orientation estimation algorithm based on multi-source information fusion[J].Measurement Science and Technology,2018,29(11):115101.
[16] 刘公绪,史凌峰.室内导航与定位技术发展综述[J].导航定位学报,2018,6(2):7-14.LIU G X,SHI L F.An overview about development of indoor navigation and positioning technology[J].Journal of Navigation and Positioning,2018,6(2):7-14.(in Chinese)