Hey Everyone,

I would like to know can you calculate the absolute speed of this algorithm below and if the the time it takes to execute a memory access is 100 nanoseconds and that all other operations (arithmetic, register accesses, etc.) take 10 nanoseconds:

Click Here

Recommended Answers

All 19 Replies

Here's the thing. You can't do that without nailing down the compiler, compiler switches (optimizations) and more.

You can however ESTIMATE it but as you can guess, ESTIMATES are just that and the real numbers never match.

Do you know why the ESTIMATE doesn't match a REAL test?

@rproffitt What if I have this formula, do you think it would be possible to calculate it then? I am pretty sure this problem can be used to calculate the absolute speed. I know that we do have one of variables already which is Ta= 100 nanoseconds, right? The rest of the missing variables could be found through the lines of code I have provided? Do you think you coud help me a little better now that I have more information? Here the formula for the absolute speed : T= TNA x Nna + Ta X Na

T= Absolute speed of the algorithm

Tna= the time to execute a memory nonaccess instruction

Nna= the number of memory nonaccess machine language instructions executed

Ta= the time to execute a memory access instruction

Na= the number of memory access machine language instructions executed

You have the formula so what is the result?
How does this compare with your real world test?

Are they close?

@ rproffitt I was wondering if you help me because I am lost with how to input the right calculations; this is my first time with this formula. Do you think you could give me some pointers of how to calculate it correctly?

@rproffitt I am not actually building a java application program. I just have to input the right figures into the calculations. Any suggestions?

Try this. Take line of code and assign the time cost to it. For a loop, you put that into say a spreadsheet and for each item in the for loop, you assign the time cost for each operation and then multiply it out by the iteration of the loop.

It's very important you understand this is simply an estimate and not going to be exactly what it measures on the hardware.

On top of that, you asked about Java. Now that's a horse of another color as the Jave runtime can change and your times may change.
So again, you are simply estimating. If you get too hung up on being right, you'll never get out of first gear.

@rproffitt Do you think you can provide demonstration of what you really are trying to say?

Sure. The first line (next time don't use a graphic dump, use text in the code block) is the for loop of a million loops. So you know a multiplier of what you'll guess the time cost of what's inside the loop will be times that.

Now continue to the next line in the loop and give it your ESTIMATED time cost and multiply it by that loop count.

for(int i=0; i<1000000; i++)

{
     if(data[i]< 0)
        data[i]= data[i] * 2; 
}

@rproffitt

Ta= 100 times 1000000= 1,000, 000,00
// mathematically right but not sure if that's what you should do

Tna and Ta can be determined from the specification of the computer system hardware? Will I need compile and run the program in java?

Nna and na can be determine by how many times each individual line will run?

Line 1- will execute n (many number of times) times
Line 2- will execute only if each array's elements (which are indicated by the indexes) equal to 0
Line 3- will execute only to multiply each element by two if in fact line 2 is true

That's it. As to the Tna and Ta you are right that system hardware and Java versions will affect the times but here's the rub. It's just an estimate. It will never match all systems and since you don't know if data set you have to take the range of time from a minimum to a maximum. So in the end you'll get a low and high time span.

Anyone that wants the exact time value hasn't thought this through.

It's an estimate. Since you claim it is in Java, you can't solve this but can ESTIMATE. I didn't read your textbook because it's your homework.

Here you asked a good enough question and I don't mind writing how to ESTIMATE the time the app might take. I've been down this road (estimates) before and know we can get a low and high time estimate.

Do you realize now that to "solve" this takes much more than what you asked here? And that the "solution" (exact time cost or run time) will change not only with the target hardware but also as you change Java versions?

Until you accept it's an estimate you may be forever searching for the answer.

@ rproffitt What good is the formula then if it changes depending on the runtime and compiler you use for the small snippet of code that I have posted here?

Daron, I think I didn't write loudly enough that you can use this to ESTIMATE the low and high running time.

Why this is good enough is that it gives us a view on if the time is good enough to deploy the solution or not.

Example: An astoroid is going to strike Earth. You can launch now and the on board computer can calculate updates to the correct course while it lifts off but if your estimate is that it can't finish a calculation in time, then you know to not launch and refine your code or compute while on the ground.

@rproffitt How would you estimate it?

The same way you did. Again, it's only an estimate and won't match reality. But if you come up wiht a high and low, reality will be somewhere in between.

This can really upset folk that want more than an estimate.

@rproffitt So would the following be how I approach it? So would the absolute be calculated like this: (610 secs) T=Tna X Nna (10 X 1) + Ta X Na (100 x 6);

Line 1: for(int=0; i<1,000,000; i++)
i variable in for loop, needs memory access and rest operations. This executes 1,000,000 times
You have:
1000000 times of
2 - memory access (1 read and 1 assign)
1 - compare
1 - incr (depends. It could be -> 1 read and 1 add)
Line 3: if(data[i]< 0)
data[i] in if statement is a memory reference and a compare operation. This executs 1,000,000 times
You have:
1000000 times of
2 - memory access
1 - compare
Line 4: data[i]= data[i] * 2
You have: 0 to 1000000 times depending on value of the data. You may want to calculate the worst case.
Hence, 1000000 times.
2 - memory access (1 read and 1 assign)
1 multiply

Sounds fine. Now test but verify. You don't have that much code there. In the time you worked this out here, you should have your code on the target and timed.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.