SHARE
TWEET

Untitled

a guest Jan 7th, 2015 1,863 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6.  
  7. inline ll gcdZban(ll a, ll b) {
  8.     while(b) b ^= a ^= b ^= a %= b;
  9.     return a;
  10. }
  11. inline ll gcdT(ll a, ll b) {
  12.     while(a&&b) a > b ? a %= b: b %= a;
  13.     return a + b;
  14. }
  15. inline ll gcdA(ll a, ll b) {
  16.     while(b) a %= b, swap(a, b);
  17.     return a;
  18. }
  19. inline ll gcd(ll a, ll b) {
  20.     return (b ? gcd(b, a % b): a);
  21. }
  22. ll gcd1(ll a, ll b) {
  23.     while(b) {
  24.         ll t = a % b;
  25.         b = a;
  26.         a = t;
  27.     }
  28.     return a;
  29.  
  30. }
  31.  
  32. int a[10000100];
  33. int b[10000100];
  34.  
  35. int main() {
  36.     freopen("input.txt", "r", stdin);
  37.     freopen("output.txt", "w", stdout);
  38.     ios_base::sync_with_stdio(0);
  39. srand(time(0));
  40.     int n = 10000000, i, g;
  41.     double t;
  42.     for(i = 0; i <= n; i++) {
  43.         a[i] = rand() % INT_MAX;
  44.         b[i] = rand() % INT_MAX;
  45.     }
  46.     t = clock();
  47.     for(i = 0; i <= n; i++)
  48.         g = __gcd(a[i], b[i]);
  49.     cout << (clock() - t) / CLOCKS_PER_SEC << " __gcd\n";
  50.    t = clock();
  51.     for(i = 0; i <= n; i++)
  52.         g = gcdZban(a[i], b[i]);
  53.     cout << (clock() - t) / CLOCKS_PER_SEC << " gcdZban\n";
  54.    t = clock();
  55.     for(i = 0; i <= n; i++)
  56.         g = gcdA(a[i], b[i]);
  57.     cout << (clock() - t) / CLOCKS_PER_SEC << " gcdA\n";
  58.    t = clock();
  59.     for(i = 0; i <= n; i++)
  60.         g = gcdT(a[i], b[i]);
  61.     cout << (clock() - t) / CLOCKS_PER_SEC << " gcdT\n";
  62.    t = clock();
  63.     for(i = 0; i <= n; i++)
  64.         g = gcd(a[i], b[i]);
  65.     cout << (clock() - t) / CLOCKS_PER_SEC << " gcd\n";
  66.    t = clock();
  67.     for(i = 0; i <= n; i++)
  68.         g = gcd1(a[i], b[i]);
  69.     cout << (clock() - t) / CLOCKS_PER_SEC << " gcd1\n";
  70. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top