# Raise Binomials to integer powers

1 view (last 30 days)
Ilya on 13 Jun 2014
Edited: Ilya on 17 Jun 2014
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.

Matt J on 13 Jun 2014
Edited: Matt J on 13 Jun 2014
Polynomial multiplication with convolutions is not fast if the required degree is high.
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 on 15 Jun 2014
This is indeed fast!
John D'Errico on 15 Jun 2014
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 on 17 Jun 2014
That's a valuable remark! I suspected this, but didn't know exactly that it might be so bad even with integers!