Hi.
I'm not quiet sure where to post this question, but as it has relations to measuring efficiency of algorithms I figured this might be the place.

I'm currently working on the implementation of an algorithm within cryptology, and I'm comparing its runningtime with an existing algorithm. Now I compare them in actual running time, but I see that people often refer to the "number of cycles" when they talk about how much work is needed to do something. So; I'm not quiet sure what's ment by these cycles. Is this actual operations on the lowest level - like in the gates on hardware level?

I've been working on some assembly programming lately and I've seen authors speak about the number of cycles on assembly instructions as well (without further explanation..). So; is that how I measure the number of cycles on my algorithm? By checking the assemblycode generated when I compile my program (written in C++), and then counting the number of cycles for the instructions. Or is there parhaps a better way?.. Or am I just way of with all I've been saying here?

Any answers will be gladly accepted! And if this is the wrong messageboard for this question and you have a better idea please let me know...

Best Regards,
Stian Karlsen

I think they talk about the Big-O.

http://en.wikipedia.org/wiki/Big_O_notation

if you speak german, there is a good article about the O:
http://www.linux-related.de/index.html?/coding/o-notation.htm

This message was edited by DrMarten at 2006-2-28 17:38:3

---

: Hi.
: I'm not quiet sure where to post this question, but as it has relations to measuring efficiency of algorithms I figured this might be the place.
:
: I'm currently working on the implementation of an algorithm within cryptology, and I'm comparing its runningtime with an existing algorithm. Now I compare them in actual running time, but I see that people often refer to the "number of cycles" when they talk about how much work is needed to do something. So; I'm not quiet sure what's ment by these cycles. Is this actual operations on the lowest level - like in the gates on hardware level?
:
: I've been working on some assembly programming lately and I've seen authors speak about the number of cycles on assembly instructions as well (without further explanation..). So; is that how I measure the number of cycles on my algorithm? By checking the assemblycode generated when I compile my program (written in C++), and then counting the number of cycles for the instructions. Or is there parhaps a better way?.. Or am I just way of with all I've been saying here?
:
: Any answers will be gladly accepted! And if this is the wrong messageboard for this question and you have a better idea please let me know...
:
: Best Regards,
: Stian Karlsen

======================================================================

CYCLES or another word used is ITERATIONS is the number of times a program needs to loop round to find an answer.

Take the following output ( from a program i wrote )>>

1) 3141592 + 2951413 = 6093005
2) 6093005 + 5003906 = 11096911
3) 11096911 + 11969011 = 23065922
4) 23065922 + 22956032 = 46021954
5) 46021954 + 45912064 = 91934018
6) 91934018 + 81043919 = 172977937
7) 172977937 + 739779271 = 912757208
8) 912757208 + 802757219 = 1715514427
9) 1715514427 + 7244155171 = 8959669598

It took 9 goes at finding the PALINDROME of a number when added to reverse of itself. Output of line one becomes input to line 2 etc till result is found.

PALINDROME means "Reads the same forwards as well as backwards".

2006 + 6002 = 8008 gives only one go round the loop but 1985 gives 4>>

1985 + 5891 = 7876
7876 + 6787 = 14663
14663 + 36641 = 51304
51304 + 40315 = 91619


Regards,

Dr M.

: This message was edited by DrMarten at 2006-2-28 17:38:3

---

: : Hi.
: : I'm not quiet sure where to post this question, but as it has relations to measuring efficiency of algorithms I figured this might be the place.
: :
: : I'm currently working on the implementation of an algorithm within cryptology, and I'm comparing its runningtime with an existing algorithm. Now I compare them in actual running time, but I see that people often refer to the "number of cycles" when they talk about how much work is needed to do something. So; I'm not quiet sure what's ment by these cycles. Is this actual operations on the lowest level - like in the gates on hardware level?
: :
: : I've been working on some assembly programming lately and I've seen authors speak about the number of cycles on assembly instructions as well (without further explanation..). So; is that how I measure the number of cycles on my algorithm? By checking the assemblycode generated when I compile my program (written in C++), and then counting the number of cycles for the instructions. Or is there parhaps a better way?.. Or am I just way of with all I've been saying here?
: :
: : Any answers will be gladly accepted! And if this is the wrong messageboard for this question and you have a better idea please let me know...
: :
: : Best Regards,
: : Stian Karlsen
:
: ======================================================================
:
: CYCLES or another word used is ITERATIONS is the number of times a program needs to loop round to find an answer.
:
: Take the following output ( from a program i wrote )>>
:
: 1) 3141592 + 2951413 = 6093005
: 2) 6093005 + 5003906 = 11096911
: 3) 11096911 + 11969011 = 23065922
: 4) 23065922 + 22956032 = 46021954
: 5) 46021954 + 45912064 = 91934018
: 6) 91934018 + 81043919 = 172977937
: 7) 172977937 + 739779271 = 912757208
: 8) 912757208 + 802757219 = 1715514427
: 9) 1715514427 + 7244155171 = 8959669598
:
: It took 9 goes at finding the PALINDROME of a number when added to reverse of itself. Output of line one becomes input to line 2 etc till result is found.
:
: PALINDROME means "Reads the same forwards as well as backwards".
:
: 2006 + 6002 = 8008 gives only one go round the loop but 1985 gives 4>>
:
: 1985 + 5891 = 7876
: 7876 + 6787 = 14663
: 14663 + 36641 = 51304
: 51304 + 40315 = 91619
:
:
: Regards,
:
: Dr M.
:
:
:
:

By cycles, one means the number of cpu-cycles. Every machine-code instruction takes one or more cpu-cycles to execute.
A 3.0 Ghz cpu processes (approx.) 3 billion cpu-cycles a second.
The Intel Pentium series know the instruction RDTSC which gets the 64-bit cycle count since boot. Executing that instruction at the start and end of the algorithm gives the number of cpu-cycles needed for the algorithm (after subtraction, ofcourse).

By the way, Dr. M, since you do something with numerical palindromes, I am the coder of the worlds fastes program that tries to resolve 196. See www.p196.org

Greets,
Eric Goldstein
www.gvh-maatwerk.nl

:
: By cycles, one means the number of cpu-cycles. Every machine-code instruction takes one or more cpu-cycles to execute.
: A 3.0 Ghz cpu processes (approx.) 3 billion cpu-cycles a second.
: The Intel Pentium series know the instruction RDTSC which gets the 64-bit cycle count since boot. Executing that instruction at the start and end of the algorithm gives the number of cpu-cycles needed for the algorithm (after subtraction, ofcourse).
:

Great, thanks. I've understood what cycles is now, but I still miss a way to find the number of cycles for mye algorithms. This instruction sounds like what I want. So, is this a function available some place in c++? Or do I have to make a systemcall to find it?

-Stian

Hi, I have done little to no assembly programming, although I would love to, the education process is slow, as I am learning VBasic now. I have read a great tutorial on this, and I will share the link:
http://maven.smith.edu/~thiebaut/ArtOfAssembly/CH03/CH03-1.html

note: hyper-threads and dual channel memory wasn't around whan this was written, so you may need to take this into account.