Computing Integer powers without multiplication.

An interesting fact about the squares is that if you're computing a list of them, you can do it without multiplication. A quick examination of the squares and their differences shows how:

 3 5 7  9  11  13  15  17  19
1 4 9 16 25  36  49  64  81  100


Cursory examination shows that the differences of the differences is 2. We could exploit this to create an infinite list of the squares in Haskell:


squares = scanl (+) 1 $ scanl (+) 3 $ repeat 2


scanl is a cousin to foldl, but it computes all the intermediate results as well. (If this is unfamiliar, scans and folds are fairly simple ways to learn a little Haskell.)


For a programming task, I needed a list of all the cubes. It turns out that you can do something similar with the cubes.

    6   6   6   6    6
  12  18  24  30   36    42 
 7  19  37  61   91   127   169
1 8   27  64  125  216   343  512  729  1000


cubes = scanl (+) 1 $ scanl (+) 7 $ scanl (+) 12 $ repeat 6


In order to do the cubes, you have to have one more level of indirection. Being curious, I wanted to figure out where the inital values came from, and If we could generalize to any integer power of integers. I calculated out the values for n^4, and the starting values were 1,15,50,60,24. This, combined with the initial values for cubes, made me think of the Stirling numbers. It looks like the starting values are:

{n} * k!
{k}


Where n is the power, and k is the row, bottom first. You can prove this is true for any n. Consider the operator ∆: ∆f(x) = f(x+1) - f(x). (∆ is the h-derivative for h = 1). ∆(xⁿ) is hard to compute, but the function x to the n falling: xⁿ = x*(x-1)*(x-2)*...*(x-n) is much nicer. ∆xⁿ = nx^n-1. The Stirling numbers relate ordinary powers to falling powers. xⁿ = ∑{n k}x^k


Applying ∆ to the above equation, we get:
∆¹xⁿ = ∑_k>1k{n k}x^n-1 + 1!{n 1}.
Repeating, we get
∆²xⁿ = ∑_k>2k(k-1){n k}x^n-2 + 2!{n 2}.
By extension,
∆^j(xⁿ) = ∑_k>jk!/(k-j)!{n k}x^n-l + j!{n j}.
∆ⁿ(xⁿ) = n!{n n} = n!.

A quick test on n = 5 helps to verify this. The stirling numbers for n = 5 are: 1, 31, 90, 65, 15, 1. So the starting coefficients for n = 5 are 1*0! = 1, 31*1! = 31, 90 * 2! = 180, 65 * 3! = 390, 15 * 4! = 360, 1 * 5! = 120.


            120
         360   480
      390   750    1330
   180   570   1320    2550
 31   211   781    2101    4651
1   32   243   1024    3125    7776


Yep, everything looks like 5th powers.