求解双基链的改进型贪心算法
Greedy Algorithm of Convert Integers into Double-Base Chains
-
摘要: 为了提升贪心算法的表现, 更有效地求解整数的双基展开, 文中采用了2-LineSearch方法, 将树形分支结构引入了贪心算法.改进加速了贪心算法的收敛, 使得在相同输入下, 新算法返回的双基表达式的长度比普通的贪心算法减少了8%以上, 在椭圆曲线标量乘法的计算代价方面也获得了至少2%的收益.Abstract: In order to improve greedy algorithm so that it could convert integers into Double-Base Chains more efficiently, we introduce tree structure into greedy algorithm by taking advantage of 2-Line Search method.This improvement accelerates the convergence of greedy algorithm.Compared with the greedy algorithm, new algorithm gains more than 8% in the average length of double-base expansions and 2% in the cost of scalar multiplication.
下载:
