%0 Journal Article
%T 基于k-ary消减的快速最大公约数算法
%A 王广赛
%A 曾光
%A 韩文报
%A 李永光
%J 计算机应用
%D 2015
%X ？最大公约数(gcd)算法中,对于输入b和c,利用sorenson的右移k-ary消减思想提出一个算法用于寻找整数x和y,使得x和y满足bx-cy在二进制表示下低比特位部分为0,即bx-cy=0(mod2e),其中e是常数正整数。利用该算法能够右移较多比特并大规模降低循环次数。再结合模算法,提出了快速gcd算法,其输入规模为n比特时最差复杂度仍然是o(n2),但最好的情况下复杂度能达到o(nlog2nloglogn)。实验数据表明,对于20万以上比特规模的输入,快速gcd算法比binarygcd算法速度快;对100万比特规模的输入,快速gcd算法速度是binarygcd算法的两倍。
%K 最大公约数算法
%K 欧几里得算法
%K 二进制最大公约数算法
%K 右移k-ary消减
%K 整数最大公约数算法
%U http://www.joca.cn/CN/abstract/abstract18251.shtml