Thread Subject: Number of operations (FLOPS)

Hi,
do you know which is the new command to compute the number
of operations in an algorithm?

In article <fk60dd$o7q$1@fred.mathworks.com>,
Flavio Eripi <didad30@libero.it> wrote:

>do you know which is the new command to compute the number
>of operations in an algorithm?

There are computing theorems that prove that it is not generally
*possible* to compute the number of operations in arbitrary
algorithms. (If you could reliably compute the number of
operations in arbitrary algorithms, then you would have solved
"the halting problem".)

If you want to compute the number of operations for a -given-
algorithm, then you will have to create a mathematical proof
of how the algorithm behaves. You will need to distinguish
"best case", "worst case", and "average case"; the average case
is the one that is usually the most difficult to prove.


I know from your past postings that you are trying to
evaluate the complexity of an algorithm, not just measure
the running time for one particular dataset.


[
Historical references for those who missed the previous postings:

http://groups.google.ca/group/comp.soft-sys.matlab/msg/cd42e17e9c2b108c

http://groups.google.ca/group/comp.soft-sys.matlab/browse_thread/thread/67400593670938b5/a40d4463a6425518
]
--
  "Is there any thing whereof it may be said, See, this is new? It hath
  been already of old time, which was before us." -- Ecclesiastes

Thanks again for your reply.
Do you think that the elapsed time (computed with tic,toc)
for best and worst case could be a possibility to evaluate
the algorithm?

roberson@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote in
message <fk63ts$lej$1@canopus.cc.umanitoba.ca>...
> In article <fk60dd$o7q$1@fred.mathworks.com>,
> Flavio Eripi <didad30@libero.it> wrote:
>
> >do you know which is the new command to compute the
number
> >of operations in an algorithm?
>
> There are computing theorems that prove that it is not
generally
> *possible* to compute the number of operations in
arbitrary
> algorithms. (If you could reliably compute the number of
> operations in arbitrary algorithms, then you would have
solved
> "the halting problem".)
>
> If you want to compute the number of operations for a -
given-
> algorithm, then you will have to create a mathematical
proof
> of how the algorithm behaves. You will need to distinguish
> "best case", "worst case", and "average case"; the
average case
> is the one that is usually the most difficult to prove.
>
>
> I know from your past postings that you are trying to
> evaluate the complexity of an algorithm, not just measure
> the running time for one particular dataset.
>
>
> [
> Historical references for those who missed the previous
postings:
>
> http://groups.google.ca/group/comp.soft-
sys.matlab/msg/cd42e17e9c2b108c
>
> http://groups.google.ca/group/comp.soft-
sys.matlab/browse_thread/thread/67400593670938b5/a40d4463a64
25518
> ]
> --
> "Is there any thing whereof it may be said, See, this
is new? It hath
> been already of old time, which was before us." --
Ecclesiastes

Thanks again for your reply.
Do you think that the elapsed time (computed with tic,toc)
for best and worst case could be a possibility to evaluate
the algorithm?

roberson@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote in
message <fk63ts$lej$1@canopus.cc.umanitoba.ca>...
> In article <fk60dd$o7q$1@fred.mathworks.com>,
> Flavio Eripi <didad30@libero.it> wrote:
>
> >do you know which is the new command to compute the
number
> >of operations in an algorithm?
>
> There are computing theorems that prove that it is not
generally
> *possible* to compute the number of operations in
arbitrary
> algorithms. (If you could reliably compute the number of
> operations in arbitrary algorithms, then you would have
solved
> "the halting problem".)
>
> If you want to compute the number of operations for a -
given-
> algorithm, then you will have to create a mathematical
proof
> of how the algorithm behaves. You will need to distinguish
> "best case", "worst case", and "average case"; the
average case
> is the one that is usually the most difficult to prove.
>
>
> I know from your past postings that you are trying to
> evaluate the complexity of an algorithm, not just measure
> the running time for one particular dataset.
>
>
> [
> Historical references for those who missed the previous
postings:
>
> http://groups.google.ca/group/comp.soft-
sys.matlab/msg/cd42e17e9c2b108c
>
> http://groups.google.ca/group/comp.soft-
sys.matlab/browse_thread/thread/67400593670938b5/a40d4463a64
25518
> ]
> --
> "Is there any thing whereof it may be said, See, this
is new? It hath
> been already of old time, which was before us." --
Ecclesiastes

In article <fk6829$9a9$1@fred.mathworks.com>,
Flavio Eripi <didad30@libero.it> wrote:
>Do you think that the elapsed time (computed with tic,toc)
>for best and worst case could be a possibility to evaluate
>the algorithm?

Not really. But you could run each test case several times
(to reduce the measurement uncertainty), and run with
different problem set sizes, and plot the increase in time
as the size of the problem grows, and attempt to fit the
resulting graph. The fit will not be easy, as each result
will probably be a mix of terms, some proportional to the
problem size, some proportional to the problem size raised
to some power (such as squared or cubed), and some proportional
to the log of the problem size (or to the problem size multiplied
by the log of the problem size).

You also have to know how to write good benchmarks to do this
properly. For example, once you pass a problem size of a few
million, you will be exceeding the primary cache sizes
and everything will start to slow down as more main memory
fetches get involved. But that slowdown does not reflect
the complexity of the algorithm itself: it reflects the complexity
of computer architectures. On the other hand, the behaviour of
the algorithm as you exceed cache sizes -is- often of interest.

The best way to measure algorithm complexity is through
theoretical analysis.
--
  "I will speculate that [...] applications [...] could actually see a
  performance boost for most users by going dual-core [...] because it
  is running the adware and spyware that [...] are otherwise slowing
  down the single CPU that user has today" -- Herb Sutter

Hi,

you can measure the amount of FLOPS.

Take look here:
http://icl.cs.utk.edu/papi/

There's also a version that runs directly under Matlab.
It supports Pentium II, III and Athlon.

http://icl.cs.utk.edu/projects/papi/downloads/WinPAPI303.exe

For me it worked find with P3.

Regards,
Stefan


roberson@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote in
message <fk6aj8$487$1@canopus.cc.umanitoba.ca>...
> In article <fk6829$9a9$1@fred.mathworks.com>,
> Flavio Eripi <didad30@libero.it> wrote:
> >Do you think that the elapsed time (computed with
tic,toc)
> >for best and worst case could be a possibility to
evaluate
> >the algorithm?
>
> Not really. But you could run each test case several times
> (to reduce the measurement uncertainty), and run with
> different problem set sizes, and plot the increase in time
> as the size of the problem grows, and attempt to fit the
> resulting graph. The fit will not be easy, as each result
> will probably be a mix of terms, some proportional to the
> problem size, some proportional to the problem size raised
> to some power (such as squared or cubed), and some
proportional
> to the log of the problem size (or to the problem size
multiplied
> by the log of the problem size).
>
> You also have to know how to write good benchmarks to do
this
> properly. For example, once you pass a problem size of a
few
> million, you will be exceeding the primary cache sizes
> and everything will start to slow down as more main memory
> fetches get involved. But that slowdown does not reflect
> the complexity of the algorithm itself: it reflects the
complexity
> of computer architectures. On the other hand, the
behaviour of
> the algorithm as you exceed cache sizes -is- often of
interest.
>
> The best way to measure algorithm complexity is through
> theoretical analysis.
> --
> "I will speculate that [...] applications [...] could
actually see a
> performance boost for most users by going dual-core
[...] because it
> is running the adware and spyware that [...] are
otherwise slowing
> down the single CPU that user has today" --
Herb Sutter