基于FPGA的零误差大数阶乘算法的设计与实现

doi:10.3969/j.issn.0372-2112.2019.05.027

电子学报 ›› 2019, Vol. 47 ›› Issue (5): 1180-1184.DOI: 10.3969/j.issn.0372-2112.2019.05.027

基于FPGA的零误差大数阶乘算法的设计与实现

刘公绪, 史凌峰, 辛东金

西安电子科技大学电子工程学院, 陕西西安 710071

收稿日期:2018-03-15 修回日期:2018-10-15 出版日期:2019-05-25
- 作者简介:
- 刘公绪 男,1992年出生于河南兰考.2015年毕业于中北大学仪器与电子学院,同年保送至西安电子科技大学电子工程学院,现为硕博连读生.研究方向为惯性导航、室内定位、多传感器融合算法等.E-mail:liugx@stu.xidian.edu.cn;史凌峰 男,1970年生于陕西省宝鸡市.1995年,分别于1995年、2003年和2008年从中国计量学院获得无线电学士、西安电子科技大学获得电路与系统硕士和博士学位.现为西安电子科技大学电子工程学院教授/博导.主要研究兴趣为导航与定位、射频与微波技术等.E-mail:lfshi@mail.xidian.edu.cn;辛东金 男,1986年出生于山东济宁.西安电子科技大学超高速电路与电磁兼容教育部重点实验室博士研究生,研究方向为物联网通信及滤波器.E-mail:xindj@stu.xidian.edu
- 基金资助:
- 卫星导航系统与装备技术国家重点实验室开放基金 (No.SKX182010927）

FPGA-Based Zero-Error Factorial Algorithm for Large Integer

LIU Gong-xu, SHI Ling-feng, XIN Dong-jin

School of Electronic Engineering, Xidian University, Xi'an, Shaanxi 710071, China

Received:2018-03-15 Revised:2018-10-15 Online:2019-05-25 Published:2019-05-25

摘要/Abstract

摘要： 随着大数据时代的到来，人们对超高精度科学计算的需求日益迫切，其中一个难点是大数阶乘问题.斯特林公式作为计算大数阶乘的传统近似方法，远不能在精度上满足要求，其它的阶乘算法可以实现较高的精度，但以牺牲大量存储空间为代价.本文提出一种具有零误差的大数阶乘算法，可以根据问题规模优化存储空间，利用并行计算的思想和FPGA的优势来提高计算速度，测试结果表明，所提出的算法具有较好的时空效率，可以应用在如大数阶乘计算器等诸多领域.

关键词: 阶乘算法, 存储空间, 并行计算, FPGA

Abstract: 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.

Key words: factorial algorithm, storage space, parallel computation, FPGA (field programmable gate array)

中图分类号:

TP311

刘公绪, 史凌峰, 辛东金. 基于FPGA的零误差大数阶乘算法的设计与实现[J]. 电子学报, 2019, 47(5): 1180-1184.

LIU Gong-xu, SHI Ling-feng, XIN Dong-jin. FPGA-Based Zero-Error Factorial Algorithm for Large Integer[J]. Acta Electronica Sinica, 2019, 47(5): 1180-1184.

参考文献

[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)

基于FPGA的零误差大数阶乘算法的设计与实现

FPGA-Based Zero-Error Factorial Algorithm for Large Integer

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	袁海英, 曾智勇, 成君鹏. 面向灵活并行度的稀疏卷积神经网络加速器[J]. 电子学报, 2022, 50(8): 1811-1818.
[2]	陈晓杰, 李斌, 周清雷. RTL级可扩展高性能数据压缩方法实现[J]. 电子学报, 2022, 50(7): 1548-1557.
[3]	许皓文, 陆浩, 王振占. 高光谱微波辐射计系统中2GHz带宽数字谱仪设计[J]. 电子学报, 2022, 50(6): 1472-1479.
[4]	曲立国, 陈国豪, 胡俊, 陈鹏. 单次扫描连通域分析算法研究综述[J]. 电子学报, 2022, 50(6): 1521-1536.
[5]	田春生, 陈雷, 王源, 王硕, 周婧, 张瑶伟, 庞永江, 周冲, 马筱婧, 杜忠, 薛钰. 面向FPGA的布局与布线技术研究综述[J]. 电子学报, 2022, 50(5): 1243-1254.
[6]	王鹏, 邹彬, 刘金枝, 周丹阳. 基于Xilinx型FPGA系统单粒子效应评估方法研究[J]. 电子学报, 2022, 50(11): 2716-2721.
[7]	李斌, 齐延荣, 周清雷. 基于Winograd算法的目标检测加速器设计与优化[J]. 电子学报, 2022, 50(10): 2387-2397.
[8]	蔡莹, 朱翔, 王舰, 李昊远, 韩建伟. 基于激光注入的FPGA加密防护设计验证研究[J]. 电子学报, 2022, 50(10): 2381-2386.
[9]	张建民, 黎铁军, 马柯帆, 肖立权. 一种加速FPGA布线的不可满足子式求解算法[J]. 电子学报, 2021, 49(6): 1210-1216.
[10]	刘杰, 葛一凡, 田明, 马力强. 基于ZYNQ的可重构卷积神经网络加速器[J]. 电子学报, 2021, 49(4): 729-735.
[11]	王卫杰, 胡少亮, 郑宇腾, 赵振国, 周海京. 并行预处理有限元方法及其在系统级封装结构电磁模拟中的应用[J]. 电子学报, 2021, 49(1): 58-63.
[12]	孙明乾, 乔庐峰, 陈庆华. 一种无匹配时间损耗的DFA压缩算法的研究与实现[J]. 电子学报, 2020, 48(6): 1132-1139.
[13]	蹇强, 张培勇, 王雪洁. 一种可配置的CNN协加速器的FPGA实现方法[J]. 电子学报, 2019, 47(7): 1525-1531.
[14]	王卫杰, 陈晓洁, 周海京. 基于区域分解的大规模并行有限元快速算法[J]. 电子学报, 2019, 47(3): 741-747.
[15]	杨林峰, 胡桂莉, 张晨, 张振荣. 基于CPU-GPU协同并行内点算法求解结构化非线性规划[J]. 电子学报, 2019, 47(2): 382-389.