complexity of algorithm by number of flops

[Nab]

Hello everyone,

plz i have two algorithm and i have to compare between then, i need to you use the ?
complexity of algorithm by number of flops ?

Can some one help, give me a link to understand this method or some references,


thanks to everyone and have a nice day

Nab...

 

[brmadhukar]

write the algorithm flow chart for both. See the number of arithmetic operations.
How many of them are floating point. That all.
BRM

 

[Nab]

plz what do you mean about Floating point?

 

[mowgli]

Complexity theoretically is determined by the amount of mathematical operations required to achieve the result, but in practice (when implemented in SW/HW) this criteria is not sufficient, because of the timing constraints imposed by the necessity to satisfy the real time processing and/or other timing requirements.
In case of floating point implementation the ratio

(Number of floating point operations to be performed) / (Minimum allowed processing)

gives the FLOP (FLoating-point Operations Per Second) figures used to evaluate and make the choice between different algorithms or implementations of the same algorithm.

Regards

Mowgli

 

[Nab]

THANK YOU VERY MUCH,

But plz, i did not understand how we use it, for a better understanding here is a small exemple (Matlab):

What is the number of folps of each instuction , and finally what's the number of flops of the algorithm...

%

[U,V,D]=svd(X*X');
En=U,Ns+1:end);
En2=En*En';
W=sort(X);
[I,J]=min(X);

%THANKS

 

[mowgli]

Complexity estimation in terms of FLOPs is a figure of merit typically used to evaluate if the hardware is adequate to perform the processing or not: to better understand the situation if you know that your algorithm requires a computational load of M FLOPs you have to chose a processor that is capable at least of k*M FLOPs, where k is a factor (>1) to keep count of unforeseen conditions or to face computational peaks due to execution of concurrent SW processes.
Moreover a good estimation of FLOPs helps designers (and project managers) to have an idea about the number of gates (= silicon area) in a ASIC or a FPGA, which is directly tied to project parameters like power consumption, cost and development time.
To estimate the FLOPs you have to decompose complex operations in terms of elementary math operations (+ and x), because these are the operations implemented in the ALUs, therefore it is not simple to give a precise count for your example, because there are high level instructions: in this case you can make an estimate based upon experience or similar designs with known FLOPs requirements.

Hope I didn't confuse you ...

Regards
Mowgli

 

[Nab]

Re: complexity of algorithm

Dear Mowgli,

Thank you very much for you answer, i did understand the definition and the usefulness of this concept.

Plz am I right if i said that :

%let note nX=length(X); nEn=length(En);

[U,V,D]=svd(X*X'); % has O(nX*nX)
En=U,Ns+1:end); % has no O()
En2=En*En'; % has O(nEn*En)
W=sort(X); % has no O()
[I,J]=min(X); % has no O()

%
and so the totale is O(nX*nX+nEn*En)

PLZ AM I RIGHT ?


Thank you,

Best regards ...

Nab

 

[mowgli]

I think that your estimate is good.
I forgot to say that if you have the necessity to evaluate execution time of an algorithm, or in general of a section of m-file, you could wrap it between tic-toc instructions (I don't remember if the keywords "tic" "toc" are correct, but you can verify in Mlab help) to acquire the CPU tick at starting and ending points and make the difference to see how many ticks the algorithm consumed.

Regards
Mowgli