0

I have a bunch of code to find the primitive operations for. The thing is that there aren't really many detailed resources out on the web on the subject. In this loop:

for i:=0 to n do
  print test
end

How many steps do we really have? In my first guess I would say n+1 considering n for the times looping and 1 for the print. Then I thought that maybe I am not precise enough. Isn't there an operation even to add 1 to i in every loop? In that matter we have n+n+1=2n+1. Is that correct?

5
  • look here, its more common to put an upper bound on the growth rate than to count exactly: en.wikipedia.org/wiki/Big_O_notation Feb 21, 2011 at 18:40
  • 1
    Seems strange to me that you'd include no less than five tags, and yet not select one that indicate the language you're using. Is that some sort of Pascal? Feb 21, 2011 at 18:47
  • 4
    What's a "primitive operation"? In a C library implementation, printf is pages of code, and even puts is highly non-trivial once you follow it into the OS. If you don't follow it into the OS then you're computing a count of items where some items are "increment an integer" (approx one CPU cycle), and other things are "print a string to stdout" (several thousands of CPU cycles). So it's a pretty meaningless number unless you can think of something important and interesting as your definition of "primitive", and that's probably why there's not many resources about it. Feb 21, 2011 at 19:01
  • @Steve you're right. It was my mistake to use print for this example. I should have used a variable assignment instead
    – Pithikos
    Feb 22, 2011 at 10:48
  • Be aware the compiler might perform loop unrolling which will change number of primitive operations.
    – sdcvvc
    Aug 2, 2012 at 20:14

2 Answers 2

4

The loop can be broken down into its "primitive operations" by re-casting it as a while:

int i = 0;
while (i < n)
{
    print test;
    i = i + 1;
}

Or, more explicitly:

loop:
    if (i < n) goto done
    print test
    i = i + 1
    goto loop
done:

You can then see that for each iteration, there is a comparison, an increment, and a goto. That's just the loop overhead. You'd have to add to that whatever work is done in the loop. If the print is considered a "primitive operation," then you have:

  • n+1 comparisons
  • n calls to print
  • n increments
  • n+1 goto instructions (one to branch out of the loop when done)

Now, how that all gets converted to machine code is highly dependent on the compiler, the runtime library, the operating system, and the target hardware. And perhaps other things.

5
  • Thanks! Rewriting the code in a while loop makes things clearer for me I guess :)
    – Pithikos
    Feb 22, 2011 at 10:46
  • 2
    For example, on a particular architecture, two of these "primitive operations" might be done as a single CPU instruction (compare-and-branch) by a sufficiently smart compiler for whatever language they're written in. Conversely the comparison i < n might require 2: subtract and check the carry bit. Of course that's architecture-dependent, but what's described above is one possible transformation a compiler might perform on produce an internal structure for translation to machine code. So the definition of "primitive operations" is still language- and compiler-dependent. Feb 22, 2011 at 11:06
  • @Steve Jessop: very good point that I should have been more explicit in making. The definition of "primitive operation" is pretty slippery. Feb 22, 2011 at 14:09
  • Is assignment operation also considered a "primitive operation"? I read it in an algorithms book that it is considered.
    – K.K
    Sep 3, 2015 at 6:52
  • @K.K: There are many different thoughts on what is considered a primitive operation. As described in a previous comment, the definition of "primitive operation" depends a lot on the language, the compiler, and the architecture. Or on the rules set forth in whatever text you're reading. Sep 3, 2015 at 7:47
0

This question may be from a decade ago however since the core theme of the question is of algorithm related that is important even over such period of time I feel it is critical knowing it. In Neutral Algorithm language let's look into the below example:

  1. sum ← 0
  2. for i ← 0 to n-1 do
  3.   sum ← sum + 1

so, we already know primitive operations happens to exist when basic operations are computed by an algorithm. Mainly when:

  A. When arithmetic operations are performed (e.g +, -, *, etc)
  B. When comparing two operands,
  C. When assigning a value to variable,
  D. When indexing an array with a value,
  E. When calling a method,
  F. When returning from a method and,
  G. When following object reference.

so, when justify the above scenario with ultimate primitive operations we find that:

  I. ONE basic operation when assigning to sum.

  II. n+1 comparisons in the simple for loop (mind you have compared n times from 0 to n-1 and the other 1 comparison is which failed checking i < m. so total n+1 comparisons.

  III. The third line sum has two primitive operations; 1 assigning to sum and another 1 performing arithmetic operations. which is since it is checked n times in the simple for loop it becomes 2*n= 2n;

  IV. Last one but that is shadowed by the pseudocode is the increment which can be explicitly represented as i ← i+1 which has two primitive operation that is gone n times 2*n= 2n;

Overall the above example has a total of 1 + 1 + n + 2n + 2n = 5n+2 primitive operations

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.