Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Sign In with Facebook Sign In with Google Sign In with OpenID

Categories

We have migrated to a new platform! Please note that you will need to reset your password to log in (your credentials are still in-tact though). Please contact lee@programmersheaven.com if you have questions.
Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

Number of cycles

stiank81stiank81 Posts: 12Member
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

Comments

  • VanilleBertVanilleBert Posts: 29Member
    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
  • DrMartenDrMarten Posts: 748Member
    [b][red]This message was edited by DrMarten at 2006-2-28 17:38:3[/red][/b][hr]
    : 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.



  • tsagldtsagld Posts: 621Member
    : [b][red]This message was edited by DrMarten at 2006-2-28 17:38:3[/red][/b][hr]
    : : 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

  • CyGuyCyGuy Posts: 312Member
    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.
  • stiank81stiank81 Posts: 12Member

    :
    : 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

Sign In or Register to comment.