Remove the std::cout in the loops and look at the speed increase :P
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; }
Last edited by Auxilium; 10-20-2012 at 09:50 PM.
Remove the std::cout in the loops and look at the speed increase :P
Last edited by Hell_Demon; 10-21-2012 at 04:56 AM.
Ah we-a blaze the fyah, make it bun dem!
You can win the rat race,Originally Posted by Jeremy S. Anderson
But you're still nothing but a fucking RAT.
++Latest Projects++
[Open Source] Injection Library
Simple PE Cipher
FilthyHooker - Simple Hooking Class
CLR Injector - Inject .NET dlls with ease
Simple Injection - An in-depth look
MPGH's .NET SDK
eJect - Simple Injector
Basic PE Explorer (BETA)
giniyat101 (10-23-2012),Hell_Demon (10-21-2012)
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.
Ah we-a blaze the fyah, make it bun dem!
Upgrade patrick lawl
Light travels faster than sound. That's why most people seem bright until you hear them speak.
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.
You can win the rat race,Originally Posted by Jeremy S. Anderson
But you're still nothing but a fucking RAT.
++Latest Projects++
[Open Source] Injection Library
Simple PE Cipher
FilthyHooker - Simple Hooking Class
CLR Injector - Inject .NET dlls with ease
Simple Injection - An in-depth look
MPGH's .NET SDK
eJect - Simple Injector
Basic PE Explorer (BETA)
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.
Last edited by radnomguywfq3; 10-27-2012 at 11:19 AM.
There are two types of tragedies in life. One is not getting what you want, the other is getting it.
If you wake up at a different time in a different place, could you wake up as a different person?
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; }
Last edited by CALauncher; 10-31-2012 at 06:02 AM.
You could make using namespace std; better than typing std:: every time
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.
Last edited by radnomguywfq3; 10-31-2012 at 04:19 PM.
There are two types of tragedies in life. One is not getting what you want, the other is getting it.
If you wake up at a different time in a different place, could you wake up as a different person?
I wrapped up a simple formula in a template so you can calculate at compile-time.
WhereCode:template<int N, int S=1, int D=1> struct sequence { enum { sum = (N >> 1) * ((S << 1) + (N - 1) * D) }; };
So you can access compile-time values like so:Code:N = number of elements in the sequence S = starting number of the sequence D = difference between each term
Code:sequence<100>::sum; // every term sequence<100,1,3>::sum; // every 3rd term ..etc
You can win the rat race,Originally Posted by Jeremy S. Anderson
But you're still nothing but a fucking RAT.
++Latest Projects++
[Open Source] Injection Library
Simple PE Cipher
FilthyHooker - Simple Hooking Class
CLR Injector - Inject .NET dlls with ease
Simple Injection - An in-depth look
MPGH's .NET SDK
eJect - Simple Injector
Basic PE Explorer (BETA)