Implementation and evaluation of a polynomial-based division algorithm

Abstract: In comparison to other basic arithmetic operations, such as addition, subtraction and multiplication,division is far more complex and expensive. Many division algorithms, except for lookup tables, rely on recursion with usually complex operations in the loop. Even if the cost in terms of area and computational complexity sometimes can be made low, the latency is usually high anyway, due to the number of iterations required. Therefore, in order to find a faster method and a method that provides better precision, a non-recursive polynomial-based algorithm was developed by the Department of Electrical Engineering at Linköping University. After having performed high-level modelling in Matlab, promising results were achieved for up to 32 bits of accuracy. However, since the cost model did not take in account other factors that are important when implementing in hardware, the question remained whether the division algorithm was also competitive in practice or not. Therefore, in order to investigate that, this thesis work was initiated. This report describes the hardware implementation, the optimization and the evaluation of this division algorithm, regarding latency and hardware cost for numbers with different precisions. In addition to this algorithm, the common Newton-Raphson algorithm has also been implemented, to serve as a reference.