Raise Binomials to integer powers
1 view (last 30 days)
Show older comments
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.
0 Comments
Accepted Answer
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.
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
3 Comments
John D'Errico
on 15 Jun 2014
Edited: 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.
More Answers (0)
See Also
Categories
Find more on Polynomials in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!