Computer operations per second - Question.

Computer operations per second - Question.

[Austin Obyrne]

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

Re: Computer operations per second - Question.

[Niklas Holsti]

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
       .      @       .

Re: Computer operations per second - Question.

[Austin Obyrne]

On Monday, July 23, 2012 7:10:10 AM UTC+1, Niklas Holsti wrote:
> 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
>        .      @       .

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

Re: Computer operations per second - Question.

[Mark Murray]

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.