some benchmarking

I created a formula to add all the numbers between to numbers (1-100, 1+2+3...+99+100) and compared it to a for loop which is probably much more common, and easier to think of.

I don't see anything that might cause the comparison unfair, but if there is, can you find it?

I know this is too unrealistic when it comes to average programs, but just did it for benchmarking. What it does is
it will add all numbers between 1 and 10,000,000, for 10,000 times, and records the time required to execute it.
yes, my formula is correct and works, so yeah.

using my algorithm, it took around 3.2 seconds, while on the other hand, the for loop total got raped

Output:
i made them __int64s so they could work with huge numbers

Code:

#include <iostream>
#include <time.h>
__int64 test(__int64 start, __int64 end)
{
	__int64 total = 0;
	if((end - start) % 2 == 0)
	{
		total = ((start+end)*((end-start)/2)) + (end/2) + 1;
	}
	else
	{
		total = (end + start) * (end/2);
	}
	return total;
}

__int64 test2(__int64 start, __int64 end)
{
	__int64 total = 0;
	for(__int64 i = 1; i <= end; i++)
	{
		total += i;
	}
	return total;
}
		
int main()
{
	int sum = 0;
	clock_t start, end,start2,end2;
	start = clock();
	for(int i = 0; i < 10000; i++)
	{
		std::cout << test(1,10000000) << '\n';
	}
	end = clock();
	double time1 = (double)(end-start)/CLOCKS_PER_SEC;
	std::cout << "Time required: " << time1 << " seconds.\n";

	std::cout << "For the for loop function. Press enter. . . \n";
	std::cin.get();
	start2 = clock();
	for(int i = 0; i < 10000; i++)
	{
		std::cout << test2(1,10000000) << '\n';
	}
	end2 = clock();
	double time2 =  (double)(end2-start2)/CLOCKS_PER_SEC;
	std::cout << "Time required: " << time2 << " seconds.\n";
	std::cout << "Formula executed " << time2 - time1 << " seconds faster than traditional for loop solution\n";
	return 0;
}

Remove the std::cout in the loops and look at the speed increase :P

Originally Posted by Hell_Demon

Remove the std::cout in the loops and look at the speed increase :P

Patrick has a piece of shit computer though :3

Originally Posted by Jason

Patrick has a piece of shit computer though :3

nice hax, my computer is not that shitty

i took away the couts, it is faster, but still pretty noticable.
instead of doing 10,000 for loops, i changed it to 100, and it still took my computer a while to do the 2nd one.

Changed it to 100,000 iterations and it still resulted in 0 lol, I couldn't even get QueryPerformanceCounter to show anything above 0 for the algo, which means it must've run in under 5 msec.

Upgrade patrick lawl

Try changing i++ -> ++i, you might save one ASM instruction. :P

Your function isn't actually an algorithm, it's a formula, and it would be really odd if it didn't rape the for-loop implementation.

Complexities:
test: O(1)
test2: O(n)

That means that the test-function's execution time is contant, no matter how big the input is, and the test2-function's execution time is linear (double the amount of input and the execution time will also double).

So Hell_Demon, just add a couple of zeroes and you should begin to see some more interesting numbers.

Originally Posted by CALauncher

Try changing i++ -> ++i, you might save one ASM instruction. :P

Not in this case. Most compilers are smart enough to optimize i++ to the ++i equivalent where possible anyway.

Did'nt yaw niggahs do number series in Math? It was like Gr10.

Sn = n(a1+a2)/2

Sn = Sum of numbers in a sequence
n = number of terms
a1 = initial value
a2 = final value

But:

An = a1 + (n-1)*d
An = Value of nth term in sequence
a1 = initial value
d = common difference between the terms... so..

Use some algebra and you get
Sn=(n^2 + 2*a1*n - n)/2

inline that and you should get much quicker code.

Or, better yet, make a function template for it, you should be able to calculate these values at compile-time if you're just throwing constants into them.

Originally Posted by radnomguywfq3

Sn = n(a1+a2)/2

Sn = Sum of numbers in a sequence
n = number of terms
a1 = initial value
a2 = final value

But:

An = a1 + (n-1)*d
An = Value of nth term in sequence
a1 = initial value
d = common difference between the terms... so..

Use some algebra and you get
Sn=(n^2 + 2*a1*n - n)/2
...

Actually the first one is correct and should be faster. The second formula is just the same thing said differently.

Sn = (n^2 + 2*a1n - n)/2 = n(n + 2a1 - 1)/2 = n(a1 + a1 + (n-1))/2

Now let's say b = a1 + (n-1). Now the formula looks like

Sn = n(a1 + b)/2, where b is actually just a2 (and the value of a2 was given)

Just to sum it up as code:

Code:

__int64 test3(__int64 start, __int64 end)
{
	__int64 n = end - start + 1;
        return n*(start + end)/2;
}

Originally Posted by CALauncher

Actually the first one is correct and should be faster. The second formula is just the same thing said differently.

Sn = (n^2 + 2*a1n - n)/2 = n(n + 2a1 - 1)/2 = n(a1 + a1 + (n-1))/2

Now let's say b = a1 + (n-1). Now the formula looks like

Sn = n(a1 + b)/2, where b is actually just a2 (and the value of a2 was given)

Just to sum it up as code:

Code:

__int64 test3(__int64 start, __int64 end)
{
	__int64 n = end - start + 1;
        return n*(start + end)/2;
}

Sn=(n^2 + 2*a1*n - n)/2 is the first substituted into the second. Neither says the same thing as the other.

*edit*

Oh, I see what you're saying. Yeah, I lost sight of the fact that the final term was equal to the number of terms since the difference is one when I was doing the algebra.

You could make using namespace std; better than typing std:: every time

I wrapped up a simple formula in a template so you can calculate at compile-time.

Code:

template<int N, int S=1, int D=1>
struct sequence
{
	enum { sum = (N >> 1) * ((S << 1) + (N - 1) * D) };
};

Where

Code:

N = number of elements in the sequence
S = starting number of the sequence
D = difference between each term

So you can access compile-time values like so:

Code:

sequence<100>::sum; // every term
sequence<100,1,3>::sum; // every 3rd term
..etc

some benchmarking

Post a Reply

Similar Threads

Tags for this Thread