Matlab recursion code: inefficient or complex problem?

7 ビュー (過去 30 日間)
Gabriel Otero
Gabriel Otero 2018 年 2 月 27 日
編集済み: Gabriel Otero 2018 年 2 月 27 日
Hi, I am struggling to get the solution of this recursion problem in reasonable execution times.
Here, I show the recursive function which basically computes the coefficients of a polynomial.
function [ coeff ] = get_coeff( n, k, tau, x )
if(n == 0) % 1st exit condition
coeff = 0;
else
if(k == 0) % 2nd exit condition
coeff = max(0, n*tau-x)^n;
else % Else recursion
total = 0;
for l = k-1:n-2
total = total + nchoosek(l, k-1)*tau^(l-k+1)*get_coeff(n-1, l, tau, x);
end
coeff = (n/k) * total;
end
end
end
% This symbolic summation solution gives numerical errors, probably due to rounding
% effects.
% syms l;
% f = nchoosek(l, k-1)*tau^(l-k+1)*get_coeff(n-1, l, tau, x);
% coeff = (n/k) * symsum(f, l, k-1, n-2);
And this is the main script where I make use of the recursive function:
Tau = 1;
ns = [3];
%delays = 0:0.25:8;
delays = [0];
F_x = zeros(1, size(delays, 2));
rho = 0.95;
tic
for ns_index = 1: size(ns, 2)
T = Tau*(ns(ns_index)+1)/rho;
% Iterate delays (x)
for delay_index = 1:size(delays, 2)
total = 0;
% Iterate polynomial.
for l = 0:ns(ns_index)-1
total = total + get_coeff(ns(ns_index), l, Tau, delays(delay_index))*(T - ns(ns_index)*Tau + delays(delay_index))^l;
end
F_x(1, delay_index) = T^(-ns(ns_index))*total;
end
end
toc
I've simplified, "ns" and "delays" vectors to contain a single value so that it is easier to follow. In summary, for a fixed value of "ns", I need to compute all the coefficients of the polynomial using the recursive function and compute its final value at "delays". By increasing the number of points in "delays", I can see a curve for a fixed "ns". My question is: for any "ns" between 1 and 10, the computation is really fast, in the order of 0.069356 seconds (even for the whole "delays" vector). Conversely, for ns = [15] or [20], the computation time increases A LOT (I didn't even manage to see the result). I'm not keen on assessing computational complexity, so I don't know if there is a problem in my code (maybe nchoosek function?, or for loops?) or maybe it is the way it has to be having in mind this recursion problem.
I would be grateful if someone could shed light on this matter, or point me in the right direction.
Thanks in advance for the time you take in reading this question :)

回答 (0 件)

カテゴリ

Help Center および File ExchangeNumber Theory についてさらに検索

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by