Computing time for .^(1/2) or .^(1/p)

Question

Maxime Polichetti 2019-4-29

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/459179-computing-time-for-1-2-or-1-p

评论： Walter Roberson 2019-5-8

Hi,

I realised that computing the square root element-wise of a matrix using .^(1/2) is faster than computing the pth root whatever the value of p :

I found (with the provided code below):

Averaged time for A.^(1/2): 0.0337 s

Averaged time for A.^(1/3): 0.0972 s

Averaged time for A.^(1/5): 0.0946 s

Does anyone know why ? (I am clearly not an expert in algorithm complexity and optimization, but I'd like to know if there is a special case of the square root implemented in the function (.^), and eventually to understand how it works in a simple way).

Thanks in advance :) !

clear all
close all
clc
% Data
A = randn(1024,1024);
% Averaged time to Compute the square root of each element in A
t_squareroot = 0;
for u = 1 : 50
    tic
    B = A.^(1/2);
    t_squareroot = t_squareroot + toc/50;
end
disp('Averaged time for A.^(1/2):')
disp(t_squareroot)
% Averaged time to Compute the cubic root of each element in A
t_cubicroot = 0;
for u = 1 : 50
    tic
    C = A.^(1/3);
    t_cubicroot = t_cubicroot + toc/50;
end
disp('Averaged time for A.^(1/3)')
disp(t_cubicroot)
% Averaged time to Compute the 5th root of each element in A
t_5throot = 0;
for u = 1 : 50
    tic
    D = A.^(1/5);
    t_5throot = t_5throot + toc/50;
end
disp('Averaged time for A.^(1/5)')
disp(t_5throot)

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Stephane Dauvillier 2019-4-29

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/459179-computing-time-for-1-2-or-1-p#answer_372820

Explanation in french here

In order to compute the square root of any number you only need to be able to compute the square root of the mantisse (which is between 1 and 2). You only have to subtract 1 to the exposant which is absolutly costless.

There is no such thing for the other power.

7 个评论
显示 5更早的评论隐藏 5更早的评论

Maxime Polichetti 2019-5-8

Thank you for answering :). I can understand now how square root could be faster than others.

One last thing, I can't find in the matlab documentation, that they use such a "trick" for it (I tried F1 for sqrt, power, nthroot, functions and their corresponding m version)... but nothing in the "More About" Section. Is it a "confidential" information ?

Thanks again :) !

Walter Roberson 2019-5-8

In situations such as these, it is not necessarily the case that similar speed-ups could not be found for other specific roots, but rather that they may need custom coding for each different root, and so there become questions of whether it is worth writing any particular one -- is the programming/debugging time and code maintenance time worth the extra performance compared to the amount of time that particular exponent is used?

sqrt() gets used a lot, so it is a natural. Cube root... maybe . 4th root... I do see that used, but I probably see random non-integer roots used more often.

请先登录，再进行评论。

Answer 2

James Tursa 2019-4-29

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/459179-computing-time-for-1-2-or-1-p#answer_372815

编辑：James Tursa 2019-4-29

I am unaware of any documentation on how TMW has chosen to implement their rooting/power algorithms, but it would not surprise me that they use a custom fast algorithm for sqrt vs a slower more generic algorithm for other powers & roots. E.g., one could use a rational function approximation for the mantissa combined with direct exponent bit manipulation for square root, and then something else for all the other powers. (This is just an example of what could be done ... not necessarily my guess at what the library code that MATLAB uses does do).