整数GCD算法中的约简

Reduction in Integer GCD Algorithm

整数最大公因子(GCD)算法通常应用一种或多种基本变换以逐步减小输入整数的规模,这些变换被定义为约简。文章介绍了几种约简方法,针对通用处理器软件实现对它们进行了比较,对一类约简进行了改进和分析,并结合多种约简方法给出了一个GCD算法,软件实现结果表明该算法有较高的效率。

It is general for Integer greatest common divisor（GCD） algorithms to use one or several basic transformations which reduce the size of the inputs integers and has been defined as Reduction in this paper. This paper presents some reductions, and they are compared based on general purpose processor implementation, improvement and analysis has been made to a type of reduction. A GCD algorithm are made up of these reductions, it is efficient for software implementation.