共查询到16条相似文献,搜索用时 62 毫秒
1.
2.
3.
4.
为解决超出计算机系统基本整数类型表达能力的整数(大整数)计算问题,以基础算法--大整数乘法为研究对象,根据大整数的表示形式与多项式表示形式上的一致性,结合大整数乘法进位与取模的特点,给出了一种关于大整数乘法的多项式算法.与现有的大整数位乘法进行了比较,证明该算法将大数相乘问题的复杂度降低到位乘法的1/3,并通过程序验证了该算法的性能,其结果与对于它们时间复杂度的分析基本一致. 相似文献
5.
针对快速傅里叶变换下的快速大整数乘法,给出了一种基于CUDA架构的GPU并行化加速的实现方法。通过分析整数快速乘法中的每一步骤,分别给出各步骤的并行化实现方法,并采用数据压缩等策略,对算法进行优化。实验表明该方法有效地提高了算法效率,随着数据规模的增长,可获得18倍以上的加速比。 相似文献
6.
7.
大整数运算广泛地应用于公钥加密算法、大规模科学计算中高精度浮点数运算类以及构建大特征值等领域,然而其大部分算法空间和时间开销都很大,尤其对于核心运算之一的大整数乘法,当数据达到一定规模时,超长的串行计算时间已成为制约算法应用的巨大瓶颈.近几年来,伴随着多核、众核芯片的迅猛发展,通过充分挖掘算法本身的并行度以利用并行处理器的强大计算能力,进而高效地提升算法性能,成为一种研究趋势.本文基于通用多核并行计算平台,研究了大整数乘法Comba及Karatsuba快速算法的并行化,提出了高效的多核并行算法.在算法实现及性能优化上,采用了OpenMP+SIMD的多级并行技术,使性能获得巨大提升.在性能测试上,我们使用优化的并行算法与原始串行算法进行对比试验,结果显示,8线程并行Comba算法和Karatsuba算法相比串行对应算法分别实现了5.85倍以及6.14倍的性能加速比提升. 相似文献
8.
基于数论转换的Schönhage-Strassen算法(简称SSA)是目前实际应用中使用较多、速度较快的大整数乘法算法之一.首先对SSA算法原理进行了详细分析,然后从细粒度的角度对SSA算法在多核平台进行比较细致的并行优化.基于大整数运算开源库GMP实现了SSA算法并行化方案,并在Intel X86平台进行了验证和测试.经测试,8线程时的最大加速比可达到6.59,平均加速比6.41.在浪潮TS850服务器对并行方案的扩展性进行测试,实验结果表明:SSA算法并行方案具有良好的扩展性,最大加速比可达21.42. 相似文献
9.
在天文学、RSA、Diffie-Hellman密码系统的算法中都要用到超大整数的乘法算术,而FFT常常被认为是20世纪数值计算和算法领域最重要的成果之一,本文主要介绍了基于FFT超大整数乘法在CPU平台下计算的实现,在此基础上提出了一个在CPU+GPU异构平台下实现超大整数乘法方法,通过两种平台下实验结果显示随着超大整数位数的增加,在CPU+GPU平台下能够获得更高的效率。 相似文献
10.
大整数取模运算是密码学应用的一种基本运算,尤其是在基于因子分解假设的公钥密码学中占有极其重要的地位。提出的m位和n位两个大整数快速取模算法,是利用分治法思想,将n位的大整数分解为n个独立十进制整数的组合,通过八次大整数乘法建立一个预处理表,能够有效地将大整数取模的计算复杂度降为[O(n(m-n))],经大量实验数据验证该算法的合理性和高效性。 相似文献
11.
在程序设计中,每种数据类型有数值范围限制,若两个位数较长的大数值整数相乘,积容易溢出,一般处理对策是将整数乘法转换成浮点乘法以提高计算精度,拓宽数值计算的范围.文章分析了印度数学家婆什伽罗名著《丽罗娃提》中的格子乘法规则,借用三维数组替代格子乘法中斜线宫格,将两个大整数每个位数进行交叉相乘,利用程序设计的循环结构将斜线宫格中的同位数值进行相加、依次进位,完成了大整数乘法算法研究,并给出了c++语言的实现代码. 相似文献
12.
13.
Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations
and ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Analyzing
the limits of symbolic graph algorithms for the reachability problem Sawitzki (Proc. of LATIN, LNCS, vol. 3887, pp. 781–792,
Springer, Berlin, 2006) has presented the first exponential lower bound on the π-OBDD size for the most significant bit of integer multiplication according to one predefined variable order π. Since the choice of the variable order is a main issue to obtain OBDDs of small size the investigation is continued. As
a result a new upper bound method and the first non-trivial upper bound on the size of OBDDs according to an arbitrary variable
order is presented. Furthermore, Sawitzki’s lower bound is improved. 相似文献
14.
在椭圆曲线密码系统中,其核心操作是点乘运算κP,P是椭圆曲线上的点,忌是整数。怎样提高点乘计算速度,已成为热点研究领域。本文提出了一种新的基于整数拆分与预计算相结合的快速点乘算法。 相似文献
15.
Simple and fast (10?), this new procedure requires no hardware and features a 10-6 approximation error. 相似文献
16.
用C语言实现超长整数的加减乘除四则运算 总被引:1,自引:0,他引:1
通过对 C语言链表、字符串的应用 ,解决了高级程序设计语言处理数据存储空间的问题 ,实现了高级语言数据类型无法完成的超长整数、高精度加减乘除四则运算 ,并对其实现算法进行了简要的分析和介绍 相似文献