Files
  • main.cpp
main.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <ctime>
#include <algorithm> 

using namespace std;

typedef unsigned long int line_segment;

#define RUN_GCM(name) run_gcm(#name, &name)
#define RUN_GCM_MANY(name) run_gcm(#name, &name, 1000000)
#define half(c) c/2

line_segment gcm0(line_segment a, line_segment b) {
    while (a != b) {
        if (b < a) a = a - b;
        else       b = b - a;
    }
    return a;
}
/********************************************/
line_segment gcm1(line_segment a, line_segment b) {
    while (a != b) {
        while (b < a) a = a - b;
        swap(a, b);
    }
    return a;
}
/********************************************/
line_segment segment_remainder(line_segment a, line_segment b) {
    while (b < a) a = a - b;
    return a;
}

line_segment gcm(line_segment a, line_segment b) {
    while (a != b) {
        a = segment_remainder(a, b);
        std::swap(a, b);
    }
    return a;
}
/********************************************/
line_segment fast_segment_remainder(line_segment a, line_segment b) {
    if (a <= b) return a;
    if (a - b <= b) return a - b;
    a = fast_segment_remainder(a, b + b);
    if (a <= b) return a;
    return a - b;
}

line_segment fast_segment_gcm(line_segment a, line_segment b) {
    while (a != b) {
        a = fast_segment_remainder(a, b);
        std::swap(a, b);
    }
    return a;
}
/********************************************/
line_segment largest_doubling(line_segment a, line_segment b) {
    // precondition: b != 0
    while (a - b >= b) b = b + b;
    return b;
}

line_segment remainder(line_segment a, line_segment b) {
    // precondition: b != 0
    if (a < b) return a;
    line_segment c = largest_doubling(a, b);
    a = a - c;
    while (c != b) {
        c = half(c);
        if (c <= a) a = a - c;
    }
    return a;
}

line_segment gcm_remainder(line_segment a, line_segment b) {
    while (b != line_segment(0)) {
        a = remainder(a, b);
        std::swap(a, b);
    }
    return a;
}
/********************************************/
line_segment remainder_fibonacci(line_segment a, line_segment b) {
    // Precondition: b > 0
    if (a < b) return a;
    line_segment c = b;
    do {
        line_segment tmp = c; c = b + c; b = tmp;
    } while (a >= c);
    do {
        if (a >= b) a = a - b;
        line_segment tmp = c - b; c = b; b = tmp;
    } while (b < c);

    return a;
}

line_segment gcm_remainder_fibonacci(line_segment a, line_segment b) {
    while (b != line_segment(0)) {
        a = remainder_fibonacci(a, b);
        std::swap(a, b);
    }
    return a;
}
/********************************************/
line_segment gcd(line_segment a, line_segment b) {
    while (b != 0) {
        a = a % b;
        std::swap(a, b);
    }
    return a;
}
/********************************************/
line_segment std_gcd(line_segment a, line_segment b) {
    return __gcd(a, b);
}
/********************************************/
void run_gcm(string funcName, line_segment (*gcm)(line_segment a, line_segment b), int loopcount = 1) {
  line_segment result = -1;
  clock_t begin = clock();
  for(int i = 0; i < loopcount; i++)
    result = (*gcm)(2, 4294967295);
  clock_t end = clock();
  double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
  cout << "function: " << funcName << ", gcm: " << result << ", loop: " << loopcount << ", time: " << elapsed_secs << endl;
}

int main() {
  RUN_GCM(gcm0);
  RUN_GCM(gcm1);
  RUN_GCM(gcm);
  RUN_GCM_MANY(fast_segment_gcm);
  RUN_GCM_MANY(gcm_remainder);
  RUN_GCM_MANY(gcm_remainder_fibonacci);
  RUN_GCM_MANY(gcd);
  RUN_GCM_MANY(std_gcd);

}
gcc version 4.6.3