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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
|
/* trivial rational numbers with arbitrary integer types (suitable for big int)
Copyright (C) 2023 Tibor 'Igor2' Palinkas
This file is licensed under Creative Commons CC0 version 1.0, see
https://creativecommons.org/publicdomain/zero/1.0/
Source code: svn://svn.repo.hu/genfip/trunk
*/
#ifndef RATIONAL
#error please define rational prefix: #define RATIONAL(x) rat_ ## x
#endif
#ifndef RATIONAL_INT
#error please define rational int type: #define RATIONAL_INT long or RATIONAL_INT big_word
#endif
#ifndef RATIONAL_API
#define RATIONAL_API
#endif
#ifndef RATIONAL_IMPL
#define RATIONAL_IMPL
#endif
#ifndef RATIONAL_OP_ADD
#define RATIONAL_OP_ADD(r,a,b) ((r) = (a)+(b))
#endif
#ifndef RATIONAL_OP_SUB
#define RATIONAL_OP_SUB(r,a,b) ((r) = (a)-(b))
#endif
#ifndef RATIONAL_OP_MUL
#define RATIONAL_OP_MUL(r,a,b) ((r) = (a)*(b))
#endif
#ifndef RATIONAL_OP_DIV
#define RATIONAL_OP_DIV(r,a,b) ((r) = (a)/(b))
#endif
/* returns 0 if a is 0, +1 if a is positive and -1 if a is negative */
#ifndef RATIONAL_OP_SGN
#define RATIONAL_OP_SGN(a) (((a) == 0) ? 0 : (((a) > 0) ? +1 : -1))
#endif
#ifndef RATIONAL_OP_LESS
#define RATIONAL_OP_LESS(a, b) ((a) < (b))
#endif
#ifndef RATIONAL_OP_EQU
#define RATIONAL_OP_EQU(a, b) ((a) == (b))
#endif
#ifndef RATIONAL_OP_GT0
#define RATIONAL_OP_GT0(a) ((a) > 0)
#endif
#ifndef RATIONAL_OP_LT0
#define RATIONAL_OP_LT0(a) ((a) < 0)
#endif
#ifndef RATIONAL_OP_NEG
#define RATIONAL_OP_NEG(a) ((a) = -(a))
#endif
/* if a and b are pointers, it's enough to swap the pointers */
#ifndef RATIONAL_OP_SWAP
#define RATIONAL_OP_SWAP(a, b) \
do { \
RATIONAL_INT __tmp__ = a; \
a = b; \
b = __tmp__; \
} while(0)
#endif
/* gets two pointers: (RATIONAL_INT *) */
#ifndef RATIONAL_OP_CPY
#define RATIONAL_OP_CPY(dst, src) (*(dst) = *(src))
#endif
typedef struct RATIONAL(_s) {
RATIONAL_INT num, denom; /* numerator and denomiator */
} RATIONAL(t);
/*** MAIN API ***
These do not check for integer overflow on numerator or denominator
and do not normalize the result (so the caller may perform multiple safe
operations and then perform normalization once) */
/* *r = a+b */
RATIONAL_IMPL void RATIONAL(add)(RATIONAL(t) *r, RATIONAL(t) a, RATIONAL(t) b);
/* *r = a-b */
RATIONAL_IMPL void RATIONAL(sub)(RATIONAL(t) *r, RATIONAL(t) a, RATIONAL(t) b);
/* *r = a*b */
RATIONAL_IMPL void RATIONAL(mul)(RATIONAL(t) *r, RATIONAL(t) a, RATIONAL(t) b);
/* *r = a/b */
RATIONAL_IMPL void RATIONAL(div)(RATIONAL(t) *r, RATIONAL(t) a, RATIONAL(t) b);
/* returns:
0 if a==b,
+1 if a>b,
-1 if a<b,
*/
RATIONAL_IMPL int RATIONAL(cmp)(RATIONAL(t) a, RATIONAL(t) b);
/* Normalize a so that the denomiator is always positive and the numerator
and denominator values the smallest possible */
RATIONAL_IMPL void RATIONAL(norm)(RATIONAL(t) *a);
#ifndef RATIONAL_INHIBIT_IMPLEMENTATION
RATIONAL_IMPL void RATIONAL(add)(RATIONAL(t) *r, RATIONAL(t) a, RATIONAL(t) b)
{
RATIONAL_INT n1, n2;
if (RATIONAL_OP_EQU(a.denom, b.denom)) {
RATIONAL_OP_ADD(r->num, a.num, b.num);
RATIONAL_OP_CPY(&r->denom, &a.denom);
return;
}
RATIONAL_OP_MUL(n1, a.num, b.denom);
RATIONAL_OP_MUL(n2, b.num, a.denom);
RATIONAL_OP_ADD(r->num, n1, n2);
RATIONAL_OP_MUL(r->denom, a.denom, b.denom);
}
RATIONAL_IMPL void RATIONAL(sub)(RATIONAL(t) *r, RATIONAL(t) a, RATIONAL(t) b)
{
RATIONAL_INT n1, n2;
if (RATIONAL_OP_EQU(a.denom, b.denom)) {
RATIONAL_OP_SUB(r->num, a.num, b.num);
RATIONAL_OP_CPY(&r->denom, &a.denom);
return;
}
RATIONAL_OP_MUL(n1, a.num, b.denom);
RATIONAL_OP_MUL(n2, b.num, a.denom);
RATIONAL_OP_SUB(r->num, n1, n2);
RATIONAL_OP_MUL(r->denom, a.denom, b.denom);
}
RATIONAL_IMPL void RATIONAL(mul)(RATIONAL(t) *r, RATIONAL(t) a, RATIONAL(t) b)
{
RATIONAL_OP_MUL(r->num, a.num, b.num);
RATIONAL_OP_MUL(r->denom, a.denom, b.denom);
}
RATIONAL_IMPL void RATIONAL(div)(RATIONAL(t) *r, RATIONAL(t) a, RATIONAL(t) b)
{
RATIONAL_OP_MUL(r->num, a.num, b.denom);
RATIONAL_OP_MUL(r->denom, b.num, a.denom);
}
RATIONAL_IMPL int RATIONAL(cmp)(RATIONAL(t) a, RATIONAL(t) b)
{
RATIONAL(t) r;
RATIONAL(sub)(&r, a, b);
if (RATIONAL_OP_SGN(r.denom) < 0)
return -RATIONAL_OP_SGN(r.num);
return RATIONAL_OP_SGN(r.num);
}
/* greatest common divider: Euclid's algorithm */
RATIONAL_IMPL void RATIONAL(gcd)(RATIONAL_INT *r, RATIONAL_INT u_, RATIONAL_INT v_)
{
RATIONAL_INT u, v;
RATIONAL_OP_CPY(&u, &u_);
RATIONAL_OP_CPY(&v, &v_);
do {
RATIONAL_INT tmp;
if (RATIONAL_OP_LESS(u, v)) {
RATIONAL_OP_SWAP(u, v);
}
RATIONAL_OP_SUB(tmp, u, v);
RATIONAL_OP_SWAP(u, tmp);
} while(RATIONAL_OP_GT0(u));
RATIONAL_OP_CPY(r, &v);
}
RATIONAL_IMPL void RATIONAL(norm_sgn)(RATIONAL(t) *a)
{
if (RATIONAL_OP_LT0(a->denom)) {
RATIONAL_OP_NEG(a->num);
RATIONAL_OP_NEG(a->denom);
}
}
RATIONAL_IMPL void RATIONAL(norm)(RATIONAL(t) *a)
{
RATIONAL_INT c, tmp;
RATIONAL(norm_sgn)(a);
RATIONAL(gcd)(&c, a->num, a->denom);
if (RATIONAL_OP_GT0(c)) {
RATIONAL_OP_DIV(tmp, a->num, c);
RATIONAL_OP_CPY(&a->num, &tmp);
RATIONAL_OP_DIV(tmp, a->denom, c);
RATIONAL_OP_CPY(&a->denom, &tmp);
}
}
#endif
|
