#include <bits/stdc++.h>
#define SIZ 10000
int asmgcd(int a, int b)
{
/* Compute Greatest Common Divisor using Euclid's Algorithm */
int result ;
__asm__ __volatile__ (
"movl %1, %%eax;"
"movl %2, %%ebx;"
"CONTD: cmpl $0, %%ebx;"
"je DONE;"
"xorl %%edx, %%edx;"
"idivl %%ebx;"
"movl %%ebx, %%eax;"
"movl %%edx, %%ebx;"
"jmp CONTD;"
"DONE: movl %%eax, %0;"
: "=g" (result) //outputs
: "g" (a), "g" (b) //inputs
);
return result;
}
inline int mygcd1(register int a, register int b)
{
while(b)
{
register int c = b;
b = a % c;
a = c;
}
return a;
}
inline int mygcd2(int a, int b)
{
while(b)
{
register int c = b;
b = a % c;
a = c;
}
return a;
}
inline int mygcd3(int a, int b)
{
while(b)
{
int c = b;
b = a % c;
a = c;
}
return a;
}
int recur_gcd(int a, int b)
{
if(b == 0) return a;
return recur_gcd(b, a % b);
}
int functest(int (*gcdfunc)(int, int))
{
int i, j;
time_t start, stop;
int g = 0;
start = clock();
for(i = 1; i < SIZ; ++i)
{
for(j = 1; j <= i; ++j)
{
g += (gcdfunc(i, j) == 1);
}
}
stop = clock();
//printf("result = %d\n", g);
printf("Time: %lf sec\n\n", (double)(stop - start) / CLOCKS_PER_SEC);
}
int main()
{
puts("STD's gcd:");
functest(std::__gcd);
puts("ASM GCD:");
functest(asmgcd);
puts("parameter and variable both registers:");
functest(mygcd1);
puts("parameter normal, variable register:");
functest(mygcd2);
puts("parameter and variable both normal:");
functest(mygcd3);
puts("recursive gcd:");
functest(recur_gcd);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojZGVmaW5lIFNJWiAxMDAwMAoKaW50IGFzbWdjZChpbnQgYSwgaW50IGIpCnsKICAgIC8qIENvbXB1dGUgR3JlYXRlc3QgQ29tbW9uIERpdmlzb3IgdXNpbmcgRXVjbGlkJ3MgQWxnb3JpdGhtICovCiAgICBpbnQgcmVzdWx0IDsKICAgIF9fYXNtX18gX192b2xhdGlsZV9fICgKICAgICAgICAibW92bCAlMSwgJSVlYXg7IgogICAgICAgICJtb3ZsICUyLCAlJWVieDsiCiAgICAgICAgIkNPTlREOiBjbXBsICQwLCAlJWVieDsiCiAgICAgICAgImplIERPTkU7IgogICAgICAgICJ4b3JsICUlZWR4LCAlJWVkeDsiCiAgICAgICAgImlkaXZsICUlZWJ4OyIKICAgICAgICAibW92bCAlJWVieCwgJSVlYXg7IgogICAgICAgICJtb3ZsICUlZWR4LCAlJWVieDsiCiAgICAgICAgImptcCBDT05URDsiCiAgICAgICAgIkRPTkU6IG1vdmwgJSVlYXgsICUwOyIKICAgICAgICA6ICI9ZyIgKHJlc3VsdCkgIC8vb3V0cHV0cwogICAgICAgIDogImciIChhKSwgImciIChiKSAvL2lucHV0cwogICAgKTsKCiAgICByZXR1cm4gcmVzdWx0Owp9CgppbmxpbmUgaW50IG15Z2NkMShyZWdpc3RlciBpbnQgYSwgcmVnaXN0ZXIgaW50IGIpCnsKICAgIHdoaWxlKGIpCiAgICB7CiAgICAgICAgcmVnaXN0ZXIgaW50IGMgPSBiOwogICAgICAgIGIgPSBhICUgYzsKICAgICAgICBhID0gYzsKICAgIH0KICAgIHJldHVybiBhOwp9CgppbmxpbmUgaW50IG15Z2NkMihpbnQgYSwgaW50IGIpCnsKICAgIHdoaWxlKGIpCiAgICB7CiAgICAgICAgcmVnaXN0ZXIgaW50IGMgPSBiOwogICAgICAgIGIgPSBhICUgYzsKICAgICAgICBhID0gYzsKICAgIH0KICAgIHJldHVybiBhOwp9CgppbmxpbmUgaW50IG15Z2NkMyhpbnQgYSwgaW50IGIpCnsKICAgIHdoaWxlKGIpCiAgICB7CiAgICAgICAgaW50IGMgPSBiOwogICAgICAgIGIgPSBhICUgYzsKICAgICAgICBhID0gYzsKICAgIH0KICAgIHJldHVybiBhOwp9CgppbnQgcmVjdXJfZ2NkKGludCBhLCBpbnQgYikKewogICAgaWYoYiA9PSAwKSByZXR1cm4gYTsKICAgIHJldHVybiByZWN1cl9nY2QoYiwgYSAlIGIpOwp9CgppbnQgZnVuY3Rlc3QoaW50ICgqZ2NkZnVuYykoaW50LCBpbnQpKQp7CiAgICBpbnQgaSwgajsKICAgIHRpbWVfdCBzdGFydCwgc3RvcDsKCiAgICBpbnQgZyA9IDA7CiAgICBzdGFydCA9IGNsb2NrKCk7CiAgICBmb3IoaSA9IDE7IGkgPCBTSVo7ICsraSkKICAgIHsKICAgICAgICBmb3IoaiA9IDE7IGogPD0gaTsgKytqKQogICAgICAgIHsKICAgICAgICAgICAgZyArPSAoZ2NkZnVuYyhpLCBqKSA9PSAxKTsKICAgICAgICB9CiAgICB9CiAgICBzdG9wID0gY2xvY2soKTsKCiAgICAvL3ByaW50ZigicmVzdWx0ID0gJWRcbiIsIGcpOwogICAgcHJpbnRmKCJUaW1lOiAlbGYgc2VjXG5cbiIsIChkb3VibGUpKHN0b3AgLSBzdGFydCkgLyBDTE9DS1NfUEVSX1NFQyk7Cn0KCmludCBtYWluKCkKewogICAgcHV0cygiU1REJ3MgZ2NkOiIpOwogICAgZnVuY3Rlc3Qoc3RkOjpfX2djZCk7CgogICAgcHV0cygiQVNNIEdDRDoiKTsKICAgIGZ1bmN0ZXN0KGFzbWdjZCk7CgogICAgcHV0cygicGFyYW1ldGVyIGFuZCB2YXJpYWJsZSBib3RoIHJlZ2lzdGVyczoiKTsKICAgIGZ1bmN0ZXN0KG15Z2NkMSk7CgogICAgcHV0cygicGFyYW1ldGVyIG5vcm1hbCwgdmFyaWFibGUgcmVnaXN0ZXI6Iik7CiAgICBmdW5jdGVzdChteWdjZDIpOwoKICAgIHB1dHMoInBhcmFtZXRlciBhbmQgdmFyaWFibGUgYm90aCBub3JtYWw6Iik7CiAgICBmdW5jdGVzdChteWdjZDMpOwoKICAgIHB1dHMoInJlY3Vyc2l2ZSBnY2Q6Iik7CiAgICBmdW5jdGVzdChyZWN1cl9nY2QpOwoKICAgIHJldHVybiAwOwp9Cg==