On the Factor Refinement Principle and its Implementation on Multicore Architectures

We propose a divide and conquer adaptation of the factor refinement algorithm of Bach, Driscoll and Shallit. For an ideal cache of Z words, with L words per block, the original approach suffers from O(n2/L) cache misses, meanwhile our adaptation incurs O(n2/ZL) cache misses only. We have realized a multithreaded implementation of the latter using Cilk++ targeting multicores. Our code achieves linear speedup on 16 cores for sufficiently large input data.