A digit serial algorithm for the integer power operation

ABSTRACT

We introduce a right-to-left digit serial algorithm for the integer power operation x^y where x and y are positive integers. For n-bit words the algorithm utilizes o(n) additions and does not require use of a multiplier. We describe a hardware implementation and evaluate the effectiveness employing a Synopsys tool set with a standard cell implementation. Out digit serial algorithm compares favorably with a popular iterative square and multiply algorithm implemented with the same tool set.

REFERENCES

• 1: Alex Fit-Florea , David W. Matula, A Digit-Serial Algorithm for the Discrete Logarithm Modulo 2^k, Proceedings of the Application-Specific Systems, Architectures and Processors, 15th IEEE International Conference on (ASAP'04), p.236-246, September 27-29, 2004 [doi>10.1109/ASAP.2004.1]
• 2: A. Fit-Florea, D.W. Matula, M.A. Thornton, "Additive Bit-serial Algorithm for the Discrete Logarithm Modulo 2k ", IEE Electronics Letters Jan. 2005, Vol. 41, No. 2, pp: 57--59.
• 3: Benschop N.F., "Multiplier for the multiplication of at least two figures in an original format" US Patent Nr. 5,923,888, July 13, 1999.
• 4: Szabo, N.S., Tanaka, R.I., "Residue arithmetic and its applications to computer technology", McGraw-Hill Book Company, 1967.
• 5: Synopsys Design/physical Compiler Student Guide. 2003.
• 6: A. Fit-Florea, D.W. Matula, M.A. Thornton, "Addition-Based Exponentiation Modulo 2k ", IEE Electronics Letters, Jan. 2005, Vol. 41, No. 2, pp: 56--57.
• 7: James E. Stine , Johannes Grad , Ivan Castellanos , Jeff Blank , Vibhuti Dave , Mallika Prakash , Nick Iliev , Nathan Jachimiec, A Framework for High-Level Synthesis of System-on-Chip Designs, Proceedings of the 2005 IEEE International Conference on Microelectronic Systems Education (MSE'05), p.67-68, June 12-13, 2005 [doi>10.1109/MSE.2005.8]
• 8: David W. Matula , Alex Fit-Florea, Table Lookup Structures for Multiplicative Inverses Modulo 2^k, Proceedings of the 17th IEEE Symposium on Computer Arithmetic, p.156-163, June 27-29, 2005 [doi>10.1109/ARITH.2005.43]
• 9: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 10: Behrooz Parhami, Computer arithmetic: algorithms and hardware designs, Oxford University Press, Oxford, 1999
• 11: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic
          Subjects: Algorithms

Additional Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic
          Subjects: Cost/performance

General Terms:
Algorithms, Design, Performance

Keywords:
discrete log, exponential, power operation, standard cell implementation