# fast evaluation of x(k+1) = x(k)*e(k)

6 views (last 30 days)
Michal on 8 Jan 2024
Edited: Michal on 9 Jan 2024
Is there any special trick how to evaluate fast this recurrent formula:
x(1) = x0
x(k+1) = x(k)*e(k), k= 1,2, ...N-1
where N = length(x) = length(e)+1
e ... known vector
I mean faster then standard for-loop:
x(1) = x0;
for k = 1:N-1
x(k+1) = x(k)*e(k);
end
Matt J on 8 Jan 2024
If N is large enough that speed would matter, you are likely running the risk of underflow or overflow of the successive products.
Michal on 8 Jan 2024
@Matt J Underflow or overflow is not an issue in my case, bacause 0 <= e(k) <= 1

Dyuman Joshi on 8 Jan 2024
Edited: Dyuman Joshi on 8 Jan 2024
Timings of for loop with preallocation and vectorization are comparable for a large number of elements -
x = 69420;
N = 5e6;
e = rand(1,N);
F1 = @() forloop(x, e, N);
F2 = @() forlooppre(x, e, N);
F3 = @() vectorization(x, e);
fprintf('Time taken by for loop without preallocation for a vector with %g elements = %f seconds', N, timeit(F1))
Time taken by for loop without preallocation for a vector with 5e+06 elements = 0.320160 seconds
fprintf('Time taken by for loop with preallocation approach for a vector with %g elements = %f seconds', N, timeit(F2))
Time taken by for loop with preallocation approach for a vector with 5e+06 elements = 0.034487 seconds
fprintf('Time taken by vectorized approach for a vector with %g elements = %f seconds', N, timeit(F3))
Time taken by vectorized approach for a vector with 5e+06 elements = 0.036738 seconds
y1 = F1();
y2 = F2();
y3 = F3();
%Comparing results using tolerance
all(abs(y1-y2)<1e-10 & abs(y2-y3)<1e-10)
ans = logical
1
%% Function definitions
%For loop without preallocation
function x = forloop(x, e, N)
for k=1:N
x(k+1) = x(k)*e(k);
end
end
%For loop without preallocation
function x = forlooppre(x, e, N)
%preallocation
x = [x zeros(1, N)];
for k=1:N-1
x(k+1) = x(k)*e(k);
end
end
%Vectorized approach
function x = vectorization(x, e)
x = x.*[1 cumprod(e)];
end
Dyuman Joshi on 9 Jan 2024
The code above was ran on
ver
Linux and MATLAB Version R2023b Update 5
Michal on 9 Jan 2024
Edited: Michal on 9 Jan 2024
Very strange!? The same code on R2023b_upd5 and my both machines LinuxMInt 21.2 +Windows 11 Pro machine shows:
for x = 6942000;
Time taken by for loop without preallocation for a vector with 5e+06 elements = 0.344369 seconds
Time taken by for loop with preallocation for a vector with 5e+06 elements = 0.025052 seconds
Time taken by vectorized approach for a vector with 5e+06 elements = 0.014689 seconds
ans =
logical
0
and
>> max( abs(y1-y2))
ans =
0
>> max( abs(y1-y3))
ans =
4.6566e-10
for x = 69420;
are tolerance checks OK
Just try more independent runs with different random vector e!!!

### Categories

Find more on Mathematics in Help Center and File Exchange

R2023b

### Community Treasure Hunt

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

Start Hunting!