1
|
3 |
|
import {EPSILON} from './config' |
2
|
3 |
|
import {ZERO, ONE, gcd} from './bigint' |
3
|
3 |
|
import {rationalApproximation, continuedFraction} from './SternBrocotTree' |
4
|
|
|
|
5
|
|
|
/** |
6
|
|
|
* @class Rational Number |
7
|
|
|
* @name Rat |
8
|
|
|
*/ |
9
|
3 |
|
export class Rat { |
10
|
|
|
n: bigint |
11
|
|
|
d: bigint |
12
|
|
|
|
13
|
|
|
/** |
14
|
|
|
* Initialize a rational number. |
15
|
|
|
*/ |
16
|
|
|
constructor(numerator: bigint|number=ZERO, denominator: bigint|number=ONE) { |
17
|
281 |
|
this.n = BigInt(numerator) |
18
|
281 |
|
this.d = BigInt(denominator) |
19
|
281 |
|
this.normalize() |
20
|
|
|
} |
21
|
|
|
|
22
|
|
|
/** |
23
|
|
|
* The decimal approximation. |
24
|
|
|
*/ |
25
|
|
|
valueOf(): number { |
26
|
33555607 |
|
return Number(this.n) / Number(this.d) |
27
|
|
|
} |
28
|
|
|
|
29
|
|
|
/** |
30
|
|
|
* The text representation. |
31
|
|
|
*/ |
32
|
|
|
toString(): string { |
33
|
23 |
|
return this.n.toString() + ( this.d === ONE ? '' : '/' + this.d.toString() ) |
34
|
|
|
} |
35
|
|
|
|
36
|
|
|
/** |
37
|
|
|
* Returns a text profile of the number in various formats and it's value after common transformations. |
38
|
|
|
*/ |
39
|
|
|
public get profile(): string { |
40
|
1 |
|
const p = [`${this.constructor.name}: ${this.toString()} (≈${+this})`] |
41
|
|
|
// p.push(`Continued: ${this.continuedFraction()}`) |
42
|
|
|
// p.push(`Babylonian: ${this.babylonian()}`) |
43
|
|
|
// p.push(`Egyptian: ${this.egyptian()}`) |
44
|
1 |
|
p.push(`psin(t): ${this.psin().toString()}`) |
45
|
1 |
|
p.push(`pcos(t): ${this.pcos().toString()}`) |
46
|
1 |
|
p.push(`ptan(t): ${this.ptan().toString()}`) |
47
|
1 |
|
return p.join('\n') |
48
|
|
|
} |
49
|
|
|
|
50
|
|
|
/** |
51
|
|
|
* Clone this. |
52
|
|
|
*/ |
53
|
|
|
clone(): Rat { |
54
|
20 |
|
return new Rat(this.n, this.d) |
55
|
|
|
} |
56
|
|
|
|
57
|
|
|
/** |
58
|
|
|
* Normalize the numerator and denominator by factoring out the common denominators. |
59
|
|
|
*/ |
60
|
|
|
normalize(): void { |
61
|
|
|
|
62
|
|
|
// normalize 0/1, 1/0, 0/0 |
63
|
359 |
|
if (this.n === ZERO) { |
64
|
52 |
|
if (this.d !== ZERO) { |
65
|
50 |
|
this.d = ONE |
66
|
|
|
} |
67
|
52 |
|
return |
68
|
|
|
} |
69
|
307 |
|
if (this.d === ZERO) { |
70
|
14 |
|
this.n = this.n > ZERO ? ONE : -ONE |
71
|
14 |
|
return |
72
|
|
|
} |
73
|
|
|
|
74
|
|
|
// normalize 1/1 |
75
|
293 |
|
if (this.n === this.d) { |
76
|
80 |
|
this.n = this.d = ONE |
77
|
80 |
|
return |
78
|
|
|
} |
79
|
|
|
|
80
|
|
|
// remove negative denominator |
81
|
213 |
|
if (this.d < ZERO) { |
82
|
5 |
|
this.n = -this.n |
83
|
5 |
|
this.d = -this.d |
84
|
|
|
} |
85
|
|
|
|
86
|
|
|
// reduce numerator and denomitator by the greatest common divisor |
87
|
213 |
|
const divisor = gcd(this.n, this.d) |
88
|
213 |
|
this.n /= divisor |
89
|
213 |
|
this.d /= divisor |
90
|
|
|
|
91
|
|
|
} |
92
|
|
|
|
93
|
|
|
/** |
94
|
|
|
* Add this to that. |
95
|
|
|
*/ |
96
|
|
|
add(that: Rat): Rat { |
97
|
36 |
|
const r = new Rat(this.n * that.d + that.n * this.d, this.d * that.d) |
98
|
36 |
|
r.normalize() |
99
|
36 |
|
return r |
100
|
|
|
} |
101
|
|
|
|
102
|
|
|
/** |
103
|
|
|
* Subtract this from that. |
104
|
|
|
*/ |
105
|
|
|
sub(that: Rat): Rat { |
106
|
12 |
|
return this.add(that.neg()) |
107
|
|
|
} |
108
|
|
|
|
109
|
|
|
/** |
110
|
|
|
* Multiply that by this. |
111
|
|
|
*/ |
112
|
|
|
mul(that: Rat): Rat { |
113
|
12 |
|
const r = new Rat(this.n * that.n, this.d * that.d) |
114
|
12 |
|
r.normalize() |
115
|
12 |
|
return r |
116
|
|
|
} |
117
|
|
|
|
118
|
|
|
/** |
119
|
|
|
* Divide this by that. |
120
|
|
|
*/ |
121
|
|
|
div(that: Rat): Rat { |
122
|
28 |
|
const r = new Rat(this.n * that.d, this.d * that.n) |
123
|
28 |
|
r.normalize() |
124
|
28 |
|
return r |
125
|
|
|
} |
126
|
|
|
|
127
|
|
|
/** |
128
|
|
|
* Mediant of this and that. |
129
|
|
|
*/ |
130
|
|
|
mediant(that: Rat): Rat { |
131
|
2 |
|
const r = new Rat(this.n + that.n, this.d + that.d) |
132
|
2 |
|
r.normalize() |
133
|
2 |
|
return r |
134
|
|
|
} |
135
|
|
|
|
136
|
|
|
/** |
137
|
|
|
* Minimum of this and that. |
138
|
|
|
*/ |
139
|
|
|
min(that: Rat): Rat { |
140
|
2 |
|
return this.isLessThan(that) ? this : that |
141
|
|
|
} |
142
|
|
|
|
143
|
|
|
/** |
144
|
|
|
* Maximum of this and that. |
145
|
|
|
*/ |
146
|
|
|
max(that: Rat): Rat { |
147
|
2 |
|
return this.isGreaterThan(that) ? this : that |
148
|
|
|
} |
149
|
|
|
|
150
|
|
|
/** |
151
|
|
|
* Raise this to the power of that. |
152
|
|
|
*/ |
153
|
|
|
pow(that: Rat): Rat { |
154
|
|
|
// zero |
155
|
25 |
|
if (that.n === ZERO) { |
156
|
1 |
|
return new Rat(ONE) |
157
|
|
|
} |
158
|
|
|
// integer |
159
|
24 |
|
if (that.d === ONE) { |
160
|
23 |
|
return new Rat(this.n**that.n, this.d**that.n) |
161
|
|
|
} |
162
|
|
|
// fraction |
163
|
|
|
else { |
164
|
1 |
|
const estimate = Math.pow(+this, +that) |
165
|
1 |
|
return FloatToRat(estimate) |
166
|
|
|
} |
167
|
|
|
} |
168
|
|
|
|
169
|
|
|
/** |
170
|
|
|
* Returns the dot product of this and that. |
171
|
|
|
*/ |
172
|
|
|
dot(that: Rat): bigint { |
173
|
1 |
|
return this.n * that.n + this.d * that.d |
174
|
|
|
} |
175
|
|
|
|
176
|
|
|
/** |
177
|
|
|
* Returns true if this equals that. |
178
|
|
|
*/ |
179
|
|
|
equals(that: Rat): boolean { |
180
|
2 |
|
return this.n === that.n && this.d === that.d |
181
|
|
|
} |
182
|
|
|
|
183
|
|
|
/** |
184
|
|
|
* Returns true if this approximates the number. |
185
|
|
|
*/ |
186
|
|
|
approximates(n: number): boolean { |
187
|
16777784 |
|
return Math.abs(+this - n) < EPSILON |
188
|
|
|
} |
189
|
|
|
|
190
|
|
|
/** |
191
|
|
|
* Returns true if this is greater than that. |
192
|
|
|
*/ |
193
|
|
|
isGreaterThan(that: Rat): boolean { |
194
|
3 |
|
return this.n * that.d > that.n * this.d |
195
|
|
|
} |
196
|
|
|
|
197
|
|
|
/** |
198
|
|
|
* Returns true if this is less than that. |
199
|
|
|
*/ |
200
|
|
|
isLessThan(that: Rat): boolean { |
201
|
3 |
|
return this.n * that.d < that.n * this.d |
202
|
|
|
} |
203
|
|
|
|
204
|
|
|
/** |
205
|
|
|
* Absolute value of this. |
206
|
|
|
*/ |
207
|
|
|
abs(): Rat { |
208
|
2 |
|
const r = this.clone() |
209
|
2 |
|
if (r.n < 0) r.n = -r.n |
210
|
2 |
|
return r |
211
|
|
|
} |
212
|
|
|
|
213
|
|
|
/** |
214
|
|
|
* Opposite (negative) of this. |
215
|
|
|
*/ |
216
|
|
|
neg(): Rat { |
217
|
14 |
|
const r = this.clone() |
218
|
14 |
|
r.n = -r.n |
219
|
14 |
|
return r |
220
|
|
|
} |
221
|
|
|
|
222
|
|
|
/** |
223
|
|
|
* Returns true if this is less than zero. |
224
|
|
|
*/ |
225
|
|
|
isNegative(): boolean { |
226
|
5 |
|
return this.n < 0 |
227
|
|
|
} |
228
|
|
|
|
229
|
|
|
/** |
230
|
|
|
* Returns true if this is a finite number. |
231
|
|
|
*/ |
232
|
|
|
isFinite(): boolean { |
233
|
2 |
|
return this.d !== ZERO |
234
|
|
|
} |
235
|
|
|
|
236
|
|
|
/** |
237
|
|
|
* The reciprocal, or multiplicative inverse, of this. |
238
|
|
|
*/ |
239
|
|
|
inv(): Rat { |
240
|
1 |
|
return new Rat(this.d, this.n) |
241
|
|
|
} |
242
|
|
|
|
243
|
|
|
/** |
244
|
|
|
* Square root of this. |
245
|
|
|
*/ |
246
|
|
|
sqrt(): Rat { |
247
|
2 |
|
return this.root(2) |
248
|
|
|
} |
249
|
|
|
|
250
|
|
|
/** |
251
|
|
|
* Returns the nth root, a number which approximates this when multiplied by itself n times. |
252
|
|
|
*/ |
253
|
|
|
root(n: number): Rat { |
254
|
|
|
|
255
|
|
|
// Handle 0/1, 1/0, -1/0, 0/0, 1/1 |
256
|
5 |
|
if (this.n === ZERO || this.d === ZERO || this.n === this.d) { |
257
|
2 |
|
return this.clone() |
258
|
|
|
} |
259
|
|
|
|
260
|
3 |
|
if (this.isNegative()) { |
261
|
1 |
|
throw `Roots of negative numbers like ${this.toString()} are too complex for this basic library` |
262
|
|
|
} |
263
|
|
|
|
264
|
2 |
|
return FloatToRat(Math.pow(+this, 1/n)) |
265
|
|
|
// return FunctionToRat(r => r.pow(n), +this) |
266
|
|
|
} |
267
|
|
|
|
268
|
|
|
/** |
269
|
|
|
* Return the closest integer approximation. |
270
|
|
|
*/ |
271
|
|
|
round(): bigint { |
272
|
1 |
|
return BigInt(Math.round(+this)) |
273
|
|
|
} |
274
|
|
|
|
275
|
|
|
/** |
276
|
|
|
* Parametric sine: 2t / (1 + t²) |
277
|
|
|
* @see https://youtu.be/Ui8OvmzDn7o?t=245 |
278
|
|
|
*/ |
279
|
|
|
psin(): Rat { |
280
|
13 |
|
if (this.d === ZERO) return new Rat(ZERO) |
281
|
11 |
|
const one = new Rat(1) |
282
|
11 |
|
const two = new Rat(2) |
283
|
11 |
|
const n = two.mul(this) |
284
|
11 |
|
const d = one.add(this.pow(two)) |
285
|
11 |
|
return n.div(d) |
286
|
|
|
} |
287
|
|
|
|
288
|
|
|
/** |
289
|
|
|
* Parametric cosine: (1 - t²) / (1 + t²) |
290
|
|
|
*/ |
291
|
|
|
pcos(): Rat { |
292
|
13 |
|
if (this.d === ZERO) return new Rat(-ONE) |
293
|
11 |
|
const one = new Rat(1) |
294
|
11 |
|
const two = new Rat(2) |
295
|
11 |
|
const t2 = this.pow(two) |
296
|
11 |
|
const n = one.sub(t2) |
297
|
11 |
|
const d = one.add(t2) |
298
|
11 |
|
return n.div(d) |
299
|
|
|
} |
300
|
|
|
|
301
|
|
|
/** |
302
|
|
|
* Parametric tangent: psin() / pcos() |
303
|
|
|
*/ |
304
|
|
|
ptan(): Rat { |
305
|
|
|
// const one = new Rat(1) |
306
|
|
|
// const two = new Rat(2) |
307
|
|
|
// const four = new Rat(4) |
308
|
|
|
// const n = this.pow(four).sub(one) |
309
|
|
|
// const d = this.pow(two).mul(two) |
310
|
|
|
// return n.div(d) |
311
|
5 |
|
return this.psin().div(this.pcos()) |
312
|
|
|
} |
313
|
|
|
|
314
|
|
|
/** |
315
|
|
|
* Returns the integers representing the continued fraction. |
316
|
|
|
*/ |
317
|
|
|
*continuedFraction(): Generator<number> { |
318
|
1 |
|
for (const n of continuedFraction(+this)) { |
319
|
2 |
|
yield n |
320
|
|
|
} |
321
|
|
|
} |
322
|
|
|
|
323
|
|
|
} |
324
|
|
|
|
325
|
|
|
/** |
326
|
|
|
* Find a Rat approximation of the floating point number. |
327
|
|
|
*/ |
328
|
3 |
|
export const FloatToRat = (n: number): Rat => { |
329
|
|
|
|
330
|
|
|
// Handle special values: 0/0, 1/0, -1/0 |
331
|
14 |
|
if (isNaN(n)) return new Rat(0, 0) |
332
|
13 |
|
if (n===Infinity) return new Rat(1, 0) |
333
|
8 |
|
if (n===-Infinity) return new Rat(-1, 0) |
334
|
|
|
|
335
|
|
|
// Shortcut for numbers close to an integer or 1/integer |
336
|
7 |
|
if (Math.abs(n%1) < EPSILON) return new Rat(Math.round(n)) |
337
|
5 |
|
if (Math.abs(1/n%1) < EPSILON) return new Rat(1, Math.round(1/n)) |
338
|
|
|
|
339
|
|
|
// Traverse the Stern–Brocot tree until a good approximation is found |
340
|
|
|
// If negative, search for the positive value and negate the result |
341
|
3 |
|
const negative = n < 1 |
342
|
3 |
|
const r = rationalApproximation(Math.abs(n)) |
343
|
3 |
|
return negative ? r.neg() : r |
344
|
|
|
} |
345
|
|
|
|
346
|
|
|
export default Rat |
347
|
|
|
|