Article citationsMore>>

F. Ablayev and M. Karpinski, “A Lower Bound for Integer Multiplication on Randomized Ordered Read-once Branching Programs,” Information and Computation, Vol. 186, No. 1, 2003, pp. 78-89. doi:10.1016/S0890-5401(03)00118-4

has been cited by the following article:

• TITLE: Large-Integer Multiplication Based on Homogeneous Polynomials

  AUTHORS: Boris S. Verkhovsky

  KEYWORDS: Homogeneous Polynomials; Toom-Cook Algorithm; Multidigit Integers; Multi-Stage Multiplication; Generalized Horner Rule; Large-Integer Multiplication

  JOURNAL NAME: International Journal of Communications, Network and System Sciences, Vol.5 No.8, August 28, 2012

  ABSTRACT: Several algorithms based on homogeneous polynomials for multiplication of large integers are described in the paper. The homogeneity of polynomials provides several simplifications: reduction of system of equations and elimination of necessity to evaluate polynomials in points with larger coordinates. It is demonstrated that a two-stage implementation of the proposed and Toom-Cook algorithms asymptotically require twice as many standard multiplications than their direct implementation. A multistage implementation of these algorithms is also less efficient than their direct implementation. Although the proposed algorithms as well as the corresponding Toom-Cook algorithms require numerous algebraic additions, the Generalized Horner rule for evaluation of homogeneous polynomials, provided in the paper, decrease this number twice.