-
Notifications
You must be signed in to change notification settings - Fork 12
/
functions.cpp
154 lines (126 loc) · 2.96 KB
/
functions.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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
///
/// Created by ice1000 on 2016/11/16.
///
// 我不做大哥好多年 我不爱冰冷的床沿
#include <math.h>
#include <stdlib.h>
#include "functions.h"
#include "templates.hpp"
using algo4j_util::max;
using algo4j_util::min;
using algo4j_util::swap;
using algo4j_util::abs;
//using std::istream;
//using std::ostream;
#pragma clang diagnostic push
#pragma ide diagnostic ignored "OCUnusedGlobalDeclarationInspection"
auto algo4j_math::sqrt_carmack(jfloat x) -> jfloat {
auto x_half = 0.5F * x;
auto i = *(jint *) &x;
i = SQRT_MAGIC_NUMBER - (i >> 1);
x = *(jfloat *) &i;
x *= (1.5F - x_half * x * x);
x *= (1.5F - x_half * x * x);
return 1 / x;
}
auto algo4j_math::sqrt_strict(const jdouble x) -> jdouble {
return sqrt(x);
}
/// euclid gcd
auto algo4j_math::gcd(jlong n, jlong m) -> jlong {
jlong c;
for (; m > 0; c = n % m, n = m, m = c);
return n;
}
auto algo4j_math::exgcd(const jlong a, const jlong b, jlong &x, jlong &y) -> jlong {
if (not b) {
x = 1;
y = 0;
return a;
}
auto r = exgcd(b, a % b, x, y);
auto t = x;
x = y;
y = t - a / b * y;
return r;
}
auto algo4j_math::gcd_stein(jlong a, jlong b) -> jlong {
if (not a)
return b;
if (not b)
return a;
if (not(a bitand 1) and not(b bitand 1))
return gcd_stein(a >> 1, b >> 1) << 1;
else if (not(a bitand 1))
return gcd_stein(a >> 1, b);
else if (not(b bitand 1))
return gcd_stein(a, b >> 1);
else
return gcd_stein((a + b) >> 1, abs(a - b) >> 1);
}
auto algo4j_math::sin_ice(const jdouble x) -> jdouble {
return sin(x);
}
auto algo4j_math::cos_ice(const jdouble x) -> jdouble {
return cos(x);
}
auto algo4j_math::tan_ice(const jdouble x) -> jdouble {
return tan(x);
}
auto algo4j_math::cot_ice(const jdouble x) -> jdouble {
return 1 / tan(x);
}
auto algo4j_math::csc_ice(const jdouble x) -> jdouble {
return 1 / sin(x);
}
auto algo4j_math::sec_ice(const jdouble x) -> jdouble {
return 1 / cos(x);
}
auto algo4j_math::ln_ice(const jdouble x) -> jdouble {
return log(x);
}
auto algo4j_math::lg_ice(const jdouble x) -> jdouble {
return log10(x);
}
auto algo4j_math::is_prime(const jlong num) -> bool {
if (num < 2)
return false;
if (num == 2)
return true;
if (not(num bitand 1))
return false;
for (auto a = 3; a * a <= num; a += 2) {
if (not(num % a))
return false;
}
return true;
}
auto algo4j_math::get_primes_simple(const jint cnt) -> jlong * {
auto primes = new jlong[cnt]();
auto index = 0;
for (auto i = 2; index < cnt; ++i) {
auto j = 0;
for (; j < index; ++j) {
if (not(i % j))
break;
}
if (j >= index)
primes[index++] = i;
}
return primes;
}
auto algo4j_uset::find(jint *data, jint n) -> jint {
return data[n] == n ? n : (data[n] = find(data, data[n]));
}
auto algo4j_uset::init(jint *raw, jsize len) -> void {
for (auto i = 0; i < len; ++i) {
raw[i] = i;
}
}
auto algo4j_mem::alloc(jsize size) -> jlong {
return (jlong) malloc(size);
}
auto algo4j_mem::release(jlong pointer) -> void {
free((void *) pointer);
}
#pragma clang diagnostic pop