@TaeHunKim/

FMTGP_4.1

C++11

No description

fork
loading
Files
  • main.cpp

This Plugin Crashed!

Error: Error: must not create an existing file {"type":"CREATE_FILE","wid":"0.8564666183199314","path":"main.cpp","file":{"path":"main.cpp","content":{"asEncoding":{"base64":"I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3RpbWU+CiNpbmNsdWRlIDxhbGdvcml0aG0+IAoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnR5cGVkZWYgdW5zaWduZWQgbG9uZyBpbnQgbGluZV9zZWdtZW50OwoKI2RlZmluZSBSVU5fR0NNKG5hbWUpIHJ1bl9nY20oI25hbWUsICZuYW1lKQojZGVmaW5lIFJVTl9HQ01fTUFOWShuYW1lKSBydW5fZ2NtKCNuYW1lLCAmbmFtZSwgMTAwMDAwMCkKI2RlZmluZSBoYWxmKGMpIGMvMgoKbGluZV9zZWdtZW50IGdjbTAobGluZV9zZWdtZW50IGEsIGxpbmVfc2VnbWVudCBiKSB7CiAgICB3aGlsZSAoYSAhPSBiKSB7CiAgICAgICAgaWYgKGIgPCBhKSBhID0gYSAtIGI7CiAgICAgICAgZWxzZSAgICAgICBiID0gYiAtIGE7CiAgICB9CiAgICByZXR1cm4gYTsKfQovKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCmxpbmVfc2VnbWVudCBnY20xKGxpbmVfc2VnbWVudCBhLCBsaW5lX3NlZ21lbnQgYikgewogICAgd2hpbGUgKGEgIT0gYikgewogICAgICAgIHdoaWxlIChiIDwgYSkgYSA9IGEgLSBiOwogICAgICAgIHN3YXAoYSwgYik7CiAgICB9CiAgICByZXR1cm4gYTsKfQovKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCmxpbmVfc2VnbWVudCBzZWdtZW50X3JlbWFpbmRlcihsaW5lX3NlZ21lbnQgYSwgbGluZV9zZWdtZW50IGIpIHsKICAgIHdoaWxlIChiIDwgYSkgYSA9IGEgLSBiOwogICAgcmV0dXJuIGE7Cn0KCmxpbmVfc2VnbWVudCBnY20obGluZV9zZWdtZW50IGEsIGxpbmVfc2VnbWVudCBiKSB7CiAgICB3aGlsZSAoYSAhPSBiKSB7CiAgICAgICAgYSA9IHNlZ21lbnRfcmVtYWluZGVyKGEsIGIpOwogICAgICAgIHN0ZDo6c3dhcChhLCBiKTsKICAgIH0KICAgIHJldHVybiBhOwp9Ci8qKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKi8KbGluZV9zZWdtZW50IGZhc3Rfc2VnbWVudF9yZW1haW5kZXIobGluZV9zZWdtZW50IGEsIGxpbmVfc2VnbWVudCBiKSB7CiAgICBpZiAoYSA8PSBiKSByZXR1cm4gYTsKICAgIGlmIChhIC0gYiA8PSBiKSByZXR1cm4gYSAtIGI7CiAgICBhID0gZmFzdF9zZWdtZW50X3JlbWFpbmRlcihhLCBiICsgYik7CiAgICBpZiAoYSA8PSBiKSByZXR1cm4gYTsKICAgIHJldHVybiBhIC0gYjsKfQoKbGluZV9zZWdtZW50IGZhc3Rfc2VnbWVudF9nY20obGluZV9zZWdtZW50IGEsIGxpbmVfc2VnbWVudCBiKSB7CiAgICB3aGlsZSAoYSAhPSBiKSB7CiAgICAgICAgYSA9IGZhc3Rfc2VnbWVudF9yZW1haW5kZXIoYSwgYik7CiAgICAgICAgc3RkOjpzd2FwKGEsIGIpOwogICAgfQogICAgcmV0dXJuIGE7Cn0KLyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqLwpsaW5lX3NlZ21lbnQgbGFyZ2VzdF9kb3VibGluZyhsaW5lX3NlZ21lbnQgYSwgbGluZV9zZWdtZW50IGIpIHsKICAgIC8vIHByZWNvbmRpdGlvbjogYiAhPSAwCiAgICB3aGlsZSAoYSAtIGIgPj0gYikgYiA9IGIgKyBiOwogICAgcmV0dXJuIGI7Cn0KCmxpbmVfc2VnbWVudCByZW1haW5kZXIobGluZV9zZWdtZW50IGEsIGxpbmVfc2VnbWVudCBiKSB7CiAgICAvLyBwcmVjb25kaXRpb246IGIgIT0gMAogICAgaWYgKGEgPCBiKSByZXR1cm4gYTsKICAgIGxpbmVfc2VnbWVudCBjID0gbGFyZ2VzdF9kb3VibGluZyhhLCBiKTsKICAgIGEgPSBhIC0gYzsKICAgIHdoaWxlIChjICE9IGIpIHsKICAgICAgICBjID0gaGFsZihjKTsKICAgICAgICBpZiAoYyA8PSBhKSBhID0gYSAtIGM7CiAgICB9CiAgICByZXR1cm4gYTsKfQoKbGluZV9zZWdtZW50IGdjbV9yZW1haW5kZXIobGluZV9zZWdtZW50IGEsIGxpbmVfc2VnbWVudCBiKSB7CiAgICB3aGlsZSAoYiAhPSBsaW5lX3NlZ21lbnQoMCkpIHsKICAgICAgICBhID0gcmVtYWluZGVyKGEsIGIpOwogICAgICAgIHN0ZDo6c3dhcChhLCBiKTsKICAgIH0KICAgIHJldHVybiBhOwp9Ci8qKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKi8KbGluZV9zZWdtZW50IHJlbWFpbmRlcl9maWJvbmFjY2kobGluZV9zZWdtZW50IGEsIGxpbmVfc2VnbWVudCBiKSB7CiAgICAvLyBQcmVjb25kaXRpb246IGIgPiAwCiAgICBpZiAoYSA8IGIpIHJldHVybiBhOwogICAgbGluZV9zZWdtZW50IGMgPSBiOwogICAgZG8gewogICAgICAgIGxpbmVfc2VnbWVudCB0bXAgPSBjOyBjID0gYiArIGM7IGIgPSB0bXA7CiAgICB9IHdoaWxlIChhID49IGMpOwogICAgZG8gewogICAgICAgIGlmIChhID49IGIpIGEgPSBhIC0gYjsKICAgICAgICBsaW5lX3NlZ21lbnQgdG1wID0gYyAtIGI7IGMgPSBiOyBiID0gdG1wOwogICAgfSB3aGlsZSAoYiA8IGMpOwoKICAgIHJldHVybiBhOwp9CgpsaW5lX3NlZ21lbnQgZ2NtX3JlbWFpbmRlcl9maWJvbmFjY2kobGluZV9zZWdtZW50IGEsIGxpbmVfc2VnbWVudCBiKSB7CiAgICB3aGlsZSAoYiAhPSBsaW5lX3NlZ21lbnQoMCkpIHsKICAgICAgICBhID0gcmVtYWluZGVyX2ZpYm9uYWNjaShhLCBiKTsKICAgICAgICBzdGQ6OnN3YXAoYSwgYik7CiAgICB9CiAgICByZXR1cm4gYTsKfQovKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKiovCmxpbmVfc2VnbWVudCBnY2QobGluZV9zZWdtZW50IGEsIGxpbmVfc2VnbWVudCBiKSB7CiAgICB3aGlsZSAoYiAhPSAwKSB7CiAgICAgICAgYSA9IGEgJSBiOwogICAgICAgIHN0ZDo6c3dhcChhLCBiKTsKICAgIH0KICAgIHJldHVybiBhOwp9Ci8qKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKi8KbGluZV9zZWdtZW50IHN0ZF9nY2QobGluZV9zZWdtZW50IGEsIGxpbmVfc2VnbWVudCBiKSB7CiAgICByZXR1cm4gX19nY2QoYSwgYik7Cn0KLyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqLwp2b2lkIHJ1bl9nY20oc3RyaW5nIGZ1bmNOYW1lLCBsaW5lX3NlZ21lbnQgKCpnY20pKGxpbmVfc2VnbWVudCBhLCBsaW5lX3NlZ21lbnQgYiksIGludCBsb29wY291bnQgPSAxKSB7CiAgbGluZV9zZWdtZW50IHJlc3VsdCA9IC0xOwogIGNsb2NrX3QgYmVnaW4gPSBjbG9jaygpOwogIGZvcihpbnQgaSA9IDA7IGkgPCBsb29wY291bnQ7IGkrKykKICAgIHJlc3VsdCA9ICgqZ2NtKSgyLCA0Mjk0OTY3Mjk1KTsKICBjbG9ja190IGVuZCA9IGNsb2NrKCk7CiAgZG91YmxlIGVsYXBzZWRfc2VjcyA9IGRvdWJsZShlbmQgLSBiZWdpbikgLyBDTE9DS1NfUEVSX1NFQzsKICBjb3V0IDw8ICJmdW5jdGlvbjogIiA8PCBmdW5jTmFtZSA8PCAiLCBnY206ICIgPDwgcmVzdWx0IDw8ICIsIGxvb3A6ICIgPDwgbG9vcGNvdW50IDw8ICIsIHRpbWU6ICIgPDwgZWxhcHNlZF9zZWNzIDw8IGVuZGw7Cn0KCmludCBtYWluKCkgewogIFJVTl9HQ00oZ2NtMCk7CiAgUlVOX0dDTShnY20xKTsKICBSVU5fR0NNKGdjbSk7CiAgUlVOX0dDTV9NQU5ZKGZhc3Rfc2VnbWVudF9nY20pOwogIFJVTl9HQ01fTUFOWShnY21fcmVtYWluZGVyKTsKICBSVU5fR0NNX01BTlkoZ2NtX3JlbWFpbmRlcl9maWJvbmFjY2kpOwogIFJVTl9HQ01fTUFOWShnY2QpOwogIFJVTl9HQ01fTUFOWShzdGRfZ2NkKTsKCn0="},"asBuffer":null},"loaded":true}}
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);

}