Execution time

[Ken]

Hello

Anyone know of a site with tutorial on calculating the steps in program or
in a pseudo code:
Ex: for( int =0 ; i<n ; i++) so int=0 will be executed once / i<n will
be executed n times / and i++ will be executed n-1 times.

I need a deeper analysis, looking for the timing steps for a nested loops .

thanks

KEN

 

[Howard]

Hello

Anyone know of a site with tutorial on calculating the steps in program or
in a pseudo code:
Ex: for( int =0 ; i<n ; i++) so int=0 will be executed once / i<n
will be executed n times / and i++ will be executed n-1 times.

I need a deeper analysis, looking for the timing steps for a nested loops
.

thanks

KEN

Define "steps".

Programs are compiled into machine code, and the results may not be anything
like you expect. Some loops, for example, can be executed by loading up
specific registers, then executing a _single_ machine instruction!
Internally, there are obviously "steps" of some sort, based on the clock,
but they're not related to the original C++ code in any way like you've
described above.

When analyzing machine code (and the C++ code that generated it), it's
usually "machine cycles" (if I recall the term correctly) that are checked.
There are tables for the various chips which tell how many machine cycles
each op-code takes (sometimes with allowances made for different parameters
used with those op-codes). It's pretty complex stuff.

You seem to know what you're looking for as far as results. If such results
are meaningful to you, just keep up that line of thought and you be should
be able to work it out for yourself on paper. I don't know if there's any
tutorial on such things, though, since they don't really tell you anything
about the time a given machine will spend on a given problem.

Perhaps a google search for "programming time complexity calculation" (or
similar searches) might help?

-Howard

 

[Kevin Handy]

Hello

Anyone know of a site with tutorial on calculating the steps in program or
in a pseudo code:
Ex: for( int =0 ; i<n ; i++) so int=0 will be executed once / i<n will
be executed n times / and i++ will be executed n-1 times.

An optimizer usually sits between your source code and
the generated machine code. It can rearrange your loop
so that 'i' disappears completely, replace your entire
loop with one single instruction, and move random bits
of code out of the loop. It may even drop some bits of
code entirely. Which optimization passes you select to
run on your code causes major differences in the final
generated code.

Source code to machine language translation, if you're
using an optimizing compiler, isn't easily calculated.
You'll need to know much about the compiler before you
could even try guessing what code will be generated.

You can pretend your optimizer is turned off, then the
problem becomes understanding what your compiler would
generate from a particular bit of source. It should be
easier to examine the actual code generated.

It might be an interesting student exercise, but isn't
useful to analyse actual code. Try using a profiler on
the actual compiled code instead.