I got a few implementation of GCD algorithm and wondered which would run faster! The result somehow surprised me. The implementations I used are-
- C++ STD's
__gcd
functions. - GCD using assembly code.
- Parameters and inside variable are both register variables.
- Parameters are normal but inside variable is register.
- Parameters and inside variable are both normal vairables.
- Recursive GCD function.
The code goes here-
http://ideone.com/ztG05G
In my Core i7 CPU with 8GB RAM the above code gives following output for SIZ=5000
:
/*
STD's gcd:
Time: 0.841000 sec
ASM GCD:
Time: 0.582000 sec
parameter and variable both registers:
Time: 0.607000 sec
parameter normal, variable register:
Time: 0.701000 sec
parameter and variable both normal:
Time: 0.811000 sec
recursive gcd:
Time: 0.858000 sec
*/
The cruelity of nature is STD's gcd functions is lot slower than the handmade gcd functions and somewhere in between normal and recursive implementations. Assembly language is faster without doubt but register variables works as fine as assembly language code.
Note: The results I got from various judges suggests that using the non-recursive GCD function with normal parameters is a good choice. No need to make things complex to save a few nanoseconds.
# IDEONE (SIZ = 5000
)
/*
STD's gcd:
Time: 1.301771 sec
ASM GCD:
> don't know what's wrong. its gives TLE :( so I skiped it. <
parameter and variable both registers:
Time: 1.303909 sec
parameter normal, variable register:
Time: 1.301958 sec
parameter and variable both normal:
Time: 1.297589 sec
recursive gcd:
Time: 1.302489 sec
*/
# CodeForces (SIZ=5000
)
/*
STD's gcd:
Time: 0.561000 sec
ASM GCD:
> don't know what's wrong. its gives TLE :( so I skiped it. <
parameter and variable both registers:
Time: 0.560000 sec
parameter normal, variable register:
Time: 0.567000 sec
parameter and variable both normal:
Time: 0.561000 sec
recursive gcd:
Time: 0.579000 sec
*/
# tutorialspoint.com/compile_cpp_online.php [SIZ=5000
]
/*
STD's gcd:
Time: 1.230137 sec
ASM GCD:
Time: 0.911728 sec
parameter and variable both registers:
Time: 0.899274 sec
parameter normal, variable register:
Time: 1.011711 sec
parameter and variable both normal:
Time: 1.171421 sec
recursive gcd:
Time: 1.342532 sec
*/
Auto comment: topic has been updated by dipu_sust (previous revision, new revision, compare).
In my tests with optimizations enabled compiler generated identical code for all of the functions except inline assembler. The fastest function would change when reordering functions and recompiling executable. So it might be related to memory layout and cache or just random.
Your asm version doesn't work because you haven't specified clobber list.