Browse Prior Art Database

Low Cost Algorithm for a Series of Integers to an Integer Power

IP.com Disclosure Number: IPCOM000109990D
Original Publication Date: 1992-Oct-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 2 page(s) / 43K

Publishing Venue

IBM

Related People

Beims, MA: AUTHOR

Abstract

An algorithm for generating the series Xn, (X + 1)n, (X + 2)n,... (where X and N are both integers) is disclosed. This algorithm reduces the cost for generating each member of the series from N multiplications to N additions.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Low Cost Algorithm for a Series of Integers to an Integer Power

       An algorithm for generating the series Xn, (X + 1)n, (X +
2)n,... (where X and N are both integers) is disclosed.  This
algorithm reduces the cost for generating each member of the series
from N multiplications to N additions.

      The simplest non-trivial example of this algorithm can be noted
in the series of the integers squared (12, 22, 32, 42, 52...).  The
first five values in this series are:
           1     4     9     16     25
      The differences between each of these values are:
              3     5      7     9
      The differences of these differences have a constant value, 2:
                 2     2      2
      Combining these results into one table gives:
           1     4     9     16     25
              3     5      7     9
                 2     2     2

      The algorithm presented in this article generates the next
value in this series by performing two additions instead of the usual
two multiplications.  The first addition is adding two to nine:
           1     4     9     16     25
              3     5     7      9     11
                 2     2     2      2

      The second addition is adding 11 to 25 to get the result for
six squared, 36, without performing any multiplications, just two
additions....