@article{10.11648/j.acm.20241304.12,
  author = {Mervat Mohamed Adel Mahmoud and Nahla Elazab Elashker},
  title = {Novel Integer Division for Embedded Systems: Generic Algorithm Optimal for Large Divisors},
  journal = {Applied and Computational Mathematics},
  volume = {13},
  number = {4},
  pages = {83-93},
  doi = {10.11648/j.acm.20241304.12},
  url = {https://doi.org/10.11648/j.acm.20241304.12},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acm.20241304.12},
  abstract = {The integer Constant Division (ICD) is the type of integer division in which the divisor is known in advance, enabling pre-computing operations to be included. Therefore, it can be more efficient regarding computing resources and time. However, most ICD techniques are restricted by a few values or narrow boundaries for the divisor. On the other hand, the main approaches of the division algorithms, where the divisor is variable, are digit-by-digit and convergence methods. The first techniques are simple and have less sophisticated conversion logic for the quotient but also have the problem of taking significantly long latency. On the contrary, the convergence techniques rely on multiplication rather than subtraction. They estimate the quotient of division providing the quotient with minimal latency at the expense of precision. This article suggests a precise, generic, and novel integer division algorithm based on sequential recursion with fewer iterations. The suggested methodology relies on extracting the division results for non-powers-of-two divisors from those for the closest power-of-two divisors, which are obtained simply using the right bit shifting. To the authors’ best knowledge of the state-of-the-art, the number of iterations in the recurrent variable division is half the divisor bit size, and the Sweeney, Robertson, and Tocher (SRT) division, which is named after its developers, involves log2(n) iterations. The suggested algorithm has an [(m/(n-1))-1] number of recursive iterations, where m and n are the number of bits of the dividend and the divisor, respectively. The design is simulated in the Vivado tool for validation and implemented with a Zynq UltraScale FPGA. The technique performance depends on the number of nested divisions and the size of a LUT. The two factors change according to the value of the divisor. Nevertheless, the size of the LUT is proportional to the range and the number of bits of the divisor. Furthermore, the equation that controls the number of nested blocks is illustrated in the manuscript. The proposed technique applies to both constant and variable divisors with a compact hardware area in the case of constant division. The hardware implementation of constant division has unlimited values for dividends and divisors with a compact hardware area in the case of large divisors. However, using the design in the hardware implementation of variable division is up to 64-bit dividend and 12-bit divisor. The result analysis demonstrates that this algorithm is more efficient for constant division for large numbers.},
 year = {2024}
}

Copy | Download

TY  - JOUR
T1  - Novel Integer Division for Embedded Systems: Generic Algorithm Optimal for Large Divisors
AU  - Mervat Mohamed Adel Mahmoud
AU  - Nahla Elazab Elashker
Y1  - 2024/07/24
PY  - 2024
N1  - https://doi.org/10.11648/j.acm.20241304.12
DO  - 10.11648/j.acm.20241304.12
T2  - Applied and Computational Mathematics
JF  - Applied and Computational Mathematics
JO  - Applied and Computational Mathematics
SP  - 83
EP  - 93
PB  - Science Publishing Group
SN  - 2328-5613
UR  - https://doi.org/10.11648/j.acm.20241304.12
AB  - The integer Constant Division (ICD) is the type of integer division in which the divisor is known in advance, enabling pre-computing operations to be included. Therefore, it can be more efficient regarding computing resources and time. However, most ICD techniques are restricted by a few values or narrow boundaries for the divisor. On the other hand, the main approaches of the division algorithms, where the divisor is variable, are digit-by-digit and convergence methods. The first techniques are simple and have less sophisticated conversion logic for the quotient but also have the problem of taking significantly long latency. On the contrary, the convergence techniques rely on multiplication rather than subtraction. They estimate the quotient of division providing the quotient with minimal latency at the expense of precision. This article suggests a precise, generic, and novel integer division algorithm based on sequential recursion with fewer iterations. The suggested methodology relies on extracting the division results for non-powers-of-two divisors from those for the closest power-of-two divisors, which are obtained simply using the right bit shifting. To the authors’ best knowledge of the state-of-the-art, the number of iterations in the recurrent variable division is half the divisor bit size, and the Sweeney, Robertson, and Tocher (SRT) division, which is named after its developers, involves log2(n) iterations. The suggested algorithm has an [(m/(n-1))-1] number of recursive iterations, where m and n are the number of bits of the dividend and the divisor, respectively. The design is simulated in the Vivado tool for validation and implemented with a Zynq UltraScale FPGA. The technique performance depends on the number of nested divisions and the size of a LUT. The two factors change according to the value of the divisor. Nevertheless, the size of the LUT is proportional to the range and the number of bits of the divisor. Furthermore, the equation that controls the number of nested blocks is illustrated in the manuscript. The proposed technique applies to both constant and variable divisors with a compact hardware area in the case of constant division. The hardware implementation of constant division has unlimited values for dividends and divisors with a compact hardware area in the case of large divisors. However, using the design in the hardware implementation of variable division is up to 64-bit dividend and 12-bit divisor. The result analysis demonstrates that this algorithm is more efficient for constant division for large numbers.
VL  - 13
IS  - 4
ER  - 

Copy | Download