一种大整数乘法Karatsuba算法的并行实现方法

摘要

本发明公开了一种大整数乘法Karatsuba算法的并行实现方法，基于64位无符号长整型整数操作，通过巧妙的公式转换技巧，指针运算以及存储方式，以解决部分积存储与计算的相关性问题，通过OpenMP多线程编程，采用section任务分担策略将算法进行并行化，从而开启8个线程在递归程序的第一层并行求取8个部分积，每个section负责一个部分积的计算任务，待部分积均求取完毕后进行串行归并，从而并行化Karatsuba算法，提高算法效率。

主权项

一种大整数乘法Karatsuba算法的并行实现方法，其特征在于包括如下步骤：(1)申请长度为N的64位无符号长整型临时数组tmp[N]，数组长度N＝3*w+s+2，其中w为乘数与被乘数的位数，其不一定被3整除，且s＝w‑2*(w/3)；(2)根据公式(9)r＝u₂*v₂*R⁴ⁿ+[u₁*v₂+u₂*v₁]*R³ⁿ+[u₁*v₁+u₀*v₂+u₂*v₀]*R²ⁿ+[(u₁+u₀)*(v₁+v₀)‑u₁*v₁‑u₀*v₀]R_n+u₀*v₀  (9)其中，u₀、u₁、u₂分别为乘数u的低n位，中n位，高s位，v₀、v₁、v₂被乘数v的低n位，中n位，高s位，n为位数，R为基；在递归算法第一层，计算部分积u₀*v₀、u₁*v₁、u₂*v₂、(u₁+u₀)*(v₁+v₀)、u₀*v₂、u₂*v₀、u₁*v₂以及u₂*v₁，且在求此8个部分积时，仍然调用原始串行递归Karatsuba算法，u₀*v₀、u₁*v₁、u₂*v₂的计算结果分别存储在rp指向数组的低2*n，中2*n位，以及高2*s位，(u₁+u₀)*(v₁+v₀)、u₀*v₂、u₂*v₀、u₁*v₂以及u₂*v₁的计算结果由低到高连续存储在步骤(1)申请的临时数组的tmp的2*n+2，n+s，n+s，n+s，n+s位，其中rp为最终存储乘数与被乘数乘积结果的数组指针，n＝w/3；在递归算法第一层计算8个部分积u₀*v₀、u₁*v₁、u₂*v₂、(u₁+u₀)*(v₁+v₀)、u₀*v₂、u₂*v₀、u₁*v₂以及u₂*v₁时，采用OpenMP并行编程section并行策略进行并行化，开启8个计算线程并行计算这8个部分积，每个线程执行一个部分积的计算过程；(3)由步骤(2)所述得到的8个部分积分别存储在数组rp以及临时数组tmp中，根据公式(9)将存储在数组rp以及临时数组tmp中的部分积进行大整数加减归并运算，并将最终结果存储在数组rp中。