Computer operations per second - Question.

I have just completed writing a very strong cryptographic cipher in Ada-95 and I need to try and analyise the time complexity of this cipher i.e the time taken to test a key space of 2560, 000,000,000,000 keys at say ‘n’ operations per second.

The processor of my home computer is a 2.61 GHz AMD processor and it has 2.87 Gb of RAM.

Is it correct for me say that my computer has a capability of 2.61 Giga operations per second i.e ‘n’ = 2.61 x 10^6?

I know this question is hardly related to Ada programming but I know also that many Ada programmer readers are well-informed computer scientists.


Can I assume that an operation is performed every cycle of the computer clock at 2.61 x10^6 operations persecond

It seems a bit naïve to say that ‘n’ is dependent only on the processor frequency?

Anybody please?

- adacrypt

On Sun, 22 Jul 2012 13:20:36 -0700 (PDT), Austin Obyrne
<austin.obyrne@hotmail.com> declaimed the following in comp.lang.ada:

>
> Is it correct for me say that my computer has a capability of 2.61 Giga operations per second i.e ‘n’ = 2.61 x 10^6?
>

Unlikely...

If you have a multi-core processor you have to consider: are you
ranking a single core or distributed among them? If the cores support
"hyper-threading" do you count those?

Are you talking floating point operations or integer?

Register to register or tight loops that stay within the CPU cache,
or memory accesses out to RAM?

> I know this question is hardly related to Ada programming but I know also that many Ada programmer readers are well-informed computer scientists.
>
http://www.sgidepot.co.uk/perf.html

--
Wulfraed Dennis Lee Bieber AF6VN
wlfraed@ix.netcom.com HTTP://wlfraed.home.netcom.com/

On 12-07-22 23:20 , Austin Obyrne wrote:
> I have just completed writing a very strong cryptographic cipher in
> Ada-95 and I need to try and analyise the time complexity of this
> cipher i.e the time taken to test a key space of 2560,
> 000,000,000,000 keys at say ‘n’ operations per second.

If you are really *analysing* the time complexity (as a big-oh function
of problem size), based on the structure of the algorithm, the actual
speed of your current computer is irrelevant.

If you want to compare or verify your analysis with measurements, the
normal method is to measure the execution time as a function of problem
size and compare the shape of the measured function with the shape of
the big-oh complexity function. In other words, to adjust the unknown
constants in the big-oh function to fit the measurements.

> The processor of my home computer is a 2.61 GHz AMD processor and it
> has 2.87 Gb of RAM.
>
> Is it correct for me say that my computer has a capability of 2.61
> Giga operations per second i.e ‘n’ = 2.61 x 10^6?

First, a giga is 10^9, not 10^6. Second, it all depends on what you mean
by an "operation".

> Can I assume that an operation is performed every cycle of the
> computer clock at 2.61 x10^6 operations persecond

Some basic "operations" are certainly performed at the stated
clock-rate, but what the operations are, in terms of your program,
depends on many other factors, such as the nature and number of
processor cores, the cache size, and the memory access patterns of your
program. The number of clock cycles needed to execute even a simple
assignment statement such as X := Y can vary from less than one to
several thousand, depending on the presence or absence of X and Y in the
caches.

Current PCs are so complex that it is not useful to compare execution
speeds of different algorithms when run on different PCs, unless the
differences are very large (such as a factor of 5 or more). If you want
to compare the actual speed of your encryption method against other
methods, you should run all the methods on the same PC (and on the same
data, of course).

--
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
. @ .

On Monday, July 23, 2012 7:10:10 AM UTC+1, Niklas Holsti wrote:
> On 12-07-22 23:20 , Austin Obyrne wrote:
> &gt; I have just completed writing a very strong cryptographic cipher in
> &gt; Ada-95 and I need to try and analyise the time complexity of this
> &gt; cipher i.e the time taken to test a key space of 2560,
> &gt; 000,000,000,000 keys at say ‘n’ operations per second.
>
> If you are really *analysing* the time complexity (as a big-oh function
> of problem size), based on the structure of the algorithm, the actual
> speed of your current computer is irrelevant.
>
> If you want to compare or verify your analysis with measurements, the
> normal method is to measure the execution time as a function of problem
> size and compare the shape of the measured function with the shape of
> the big-oh complexity function. In other words, to adjust the unknown
> constants in the big-oh function to fit the measurements.
>
> &gt; The processor of my home computer is a 2.61 GHz AMD processor and it
> &gt; has 2.87 Gb of RAM.
> &gt;
> &gt; Is it correct for me say that my computer has a capability of 2.61
> &gt; Giga operations per second i.e ‘n’ = 2.61 x 10^6?
>
> First, a giga is 10^9, not 10^6. Second, it all depends on what you mean
> by an &quot;operation&quot;.
>
> &gt; Can I assume that an operation is performed every cycle of the
> &gt; computer clock at 2.61 x10^6 operations persecond
>
> Some basic &quot;operations&quot; are certainly performed at the stated
> clock-rate, but what the operations are, in terms of your program,
> depends on many other factors, such as the nature and number of
> processor cores, the cache size, and the memory access patterns of your
> program. The number of clock cycles needed to execute even a simple
> assignment statement such as X := Y can vary from less than one to
> several thousand, depending on the presence or absence of X and Y in the
> caches.
>
> Current PCs are so complex that it is not useful to compare execution
> speeds of different algorithms when run on different PCs, unless the
> differences are very large (such as a factor of 5 or more). If you want
> to compare the actual speed of your encryption method against other
> methods, you should run all the methods on the same PC (and on the same
> data, of course).
>
> --
> Niklas Holsti
> Tidorum Ltd
> niklas holsti tidorum fi
> . @ .

Thanks a lot Niklas - I suspected as much - it depends on may factors. - Austin O'Byrne.

On Sunday, July 22, 2012 10:31:33 PM UTC+1, Dennis Lee Bieber wrote:
> On Sun, 22 Jul 2012 13:20:36 -0700 (PDT), Austin Obyrne
> &lt;austin.obyrne@hotmail.com&gt; declaimed the following in comp.lang.ada:
>
> &gt;
> &gt; Is it correct for me say that my computer has a capability of 2.61 Giga operations per second i.e �n� = 2.61 x 10^6?
> &gt;
>
> Unlikely...
>
> If you have a multi-core processor you have to consider: are you
> ranking a single core or distributed among them? If the cores support
> &quot;hyper-threading&quot; do you count those?
>
> Are you talking floating point operations or integer?
>
> Register to register or tight loops that stay within the CPU cache,
> or memory accesses out to RAM?
>
> &gt; I know this question is hardly related to Ada programming but I knowalso that many Ada programmer readers are well-informed computer scientists.
> &gt;
> http://www.sgidepot.co.uk/perf.html
>
> --
> Wulfraed Dennis Lee Bieber AF6VN
> wlfraed@ix.netcom.com HTTP://wlfraed.home.netcom.com/

Thanks Dennis - that's just what I wanted to know - Austin O'Byrne

On 23/07/2012 07:56, Austin Obyrne wrote:
>> http://www.sgidepot.co.uk/perf.html
>>
>> --
>> Wulfraed Dennis Lee Bieber AF6VN
>> wlfraed@ix.netcom.com HTTP://wlfraed.home.netcom.com/
>
> Thanks Dennis - that's just what I wanted to know - Austin O'Byrne

MIPS/FLOPS and O(f(n)) are ENTIRELY different concepts.

M
--
Mark "No Nickname" Murray
Notable nebbish, extreme generalist.

On 23/07/2012 07:51, Austin Obyrne wrote:
> Thanks a lot Niklas - I suspected as much - it depends on may factors. - Austin O'Byrne.

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

M
--
Mark "No Nickname" Murray
Notable nebbish, extreme generalist.