Блог пользователя dipu_sust

Автор dipu_sust, 9 лет назад, По-английски

I got a few implementation of GCD algorithm and wondered which would run faster! The result somehow surprised me. The implementations I used are-

  1. C++ STD's __gcd functions.
  2. GCD using assembly code.
  3. Parameters and inside variable are both register variables.
  4. Parameters are normal but inside variable is register.
  5. Parameters and inside variable are both normal vairables.
  6. 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
*/

Полный текст и комментарии »

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится