fork(4) download
  1. #include <bits/stdc++.h>
  2.  
  3. #define SIZ 10000
  4.  
  5. int asmgcd(int a, int b)
  6. {
  7. /* Compute Greatest Common Divisor using Euclid's Algorithm */
  8. int result ;
  9. __asm__ __volatile__ (
  10. "movl %1, %%eax;"
  11. "movl %2, %%ebx;"
  12. "CONTD: cmpl $0, %%ebx;"
  13. "je DONE;"
  14. "xorl %%edx, %%edx;"
  15. "idivl %%ebx;"
  16. "movl %%ebx, %%eax;"
  17. "movl %%edx, %%ebx;"
  18. "jmp CONTD;"
  19. "DONE: movl %%eax, %0;"
  20. : "=g" (result) //outputs
  21. : "g" (a), "g" (b) //inputs
  22. );
  23.  
  24. return result;
  25. }
  26.  
  27. inline int mygcd1(register int a, register int b)
  28. {
  29. while(b)
  30. {
  31. register int c = b;
  32. b = a % c;
  33. a = c;
  34. }
  35. return a;
  36. }
  37.  
  38. inline int mygcd2(int a, int b)
  39. {
  40. while(b)
  41. {
  42. register int c = b;
  43. b = a % c;
  44. a = c;
  45. }
  46. return a;
  47. }
  48.  
  49. inline int mygcd3(int a, int b)
  50. {
  51. while(b)
  52. {
  53. int c = b;
  54. b = a % c;
  55. a = c;
  56. }
  57. return a;
  58. }
  59.  
  60. int recur_gcd(int a, int b)
  61. {
  62. if(b == 0) return a;
  63. return recur_gcd(b, a % b);
  64. }
  65.  
  66. int functest(int (*gcdfunc)(int, int))
  67. {
  68. int i, j;
  69. time_t start, stop;
  70.  
  71. int g = 0;
  72. start = clock();
  73. for(i = 1; i < SIZ; ++i)
  74. {
  75. for(j = 1; j <= i; ++j)
  76. {
  77. g += (gcdfunc(i, j) == 1);
  78. }
  79. }
  80. stop = clock();
  81.  
  82. //printf("result = %d\n", g);
  83. printf("Time: %lf sec\n\n", (double)(stop - start) / CLOCKS_PER_SEC);
  84. }
  85.  
  86. int main()
  87. {
  88. puts("STD's gcd:");
  89. functest(std::__gcd);
  90.  
  91. puts("ASM GCD:");
  92. functest(asmgcd);
  93.  
  94. puts("parameter and variable both registers:");
  95. functest(mygcd1);
  96.  
  97. puts("parameter normal, variable register:");
  98. functest(mygcd2);
  99.  
  100. puts("parameter and variable both normal:");
  101. functest(mygcd3);
  102.  
  103. puts("recursive gcd:");
  104. functest(recur_gcd);
  105.  
  106. return 0;
  107. }
  108.  
Time limit exceeded #stdin #stdout 15s 3412KB
stdin
Standard input is empty
stdout
Standard output is empty