Raise Binomials to integer powers

It's needed to raise first-degree binomials (ax+b) (i.e. polynomial vectors [a b]) to integer powers. Is there any fast solution? Polynomial multiplication with convolutions is not fast if the required degree is high..

I know about the Pascal triangle, but I don't know/have an algorithm.

Answer 1

[Matt J]

Polynomial multiplication with convolutions is not fast if the required degree is high.

What about with FFTs, e.g.,

n=3;
p=[1,1];

p_to_the_n = real(ifft(fft(p,n+1).^n))

      p_to_the_n =

           1     3     3     1

[Ilya]

This is indeed fast!

[John D'Errico]

Be careful though, as this will return floating point numbers, NOT integers as you might want.

format long g
n=20;
p=[1,1];
p_to_the_n = real(ifft(fft(p,n+1).^n))
p_to_the_n =
  Columns 1 through 5
          1.00000000003881          20.0000000000111          189.999999999978          1139.99999999998          4844.99999999996
  Columns 6 through 10
                     15504                     38760                     77520                    125970                    167960
  Columns 11 through 15
                    184756                    167960                    125970          77520.0000000001          38760.0000000001
  Columns 16 through 20
                     15504          4844.99999999992          1139.99999999992          189.999999999956          19.9999999999778
  Column 21
          1.00000000003326

For high enough orders, even rounding might not be sufficient to restore them to integers.

[Ilya]

That's a valuable remark! I suspected this, but didn't know exactly that it might be so bad even with integers!