对乘幂问题引入除法运算

APPLING DIVISION OPERATIONS TO POWER PROBLEMS

在一些芯片上进行一次乘除法运算的时间基本一致。基于这个前提,本文引进除法运算来解决乘幂问题,使二进法的乘(除)法次数的上界从2log_2n降为3/2log_2n,使m进法的乘(除)法次数的上界从(s+1)/s log_2n+m-2降为(s+1)/s log_2n+m/2(m=2s),又将m进法的思想用于二进法,用非均匀分组的方法对二进法作了进一步的改进。本文的思想对乘除法运算时间不一致的情况也适用。

The time consumed by multiplication and division operations basically are the same on some kinds of chips (2,3). In view of this premise, this paper introduces division operations into power problems, thus decreasing upper bounds of multiplications (including divisions) from 2log_2n to 3/2log_2n for binary method and from(s+1)/s log_2n+m-2to(s+1)/s log_2n+m/2 for radix-m method (where m= 2s). A further modification to the binary method with inhomogeneous grouping is given. The results in this paper is also applicable to the case where the time consumed by multiplicalion and division operations are not the same.