Rat.egyptianFraction - Code Metrics - Inspection of "add the polyrat and some formats and tests" - acerix/cnum - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — main ( 12d9ec...5a557a )

by Dylan

created 2021-07-26 06:16 UTC

Rat.egyptianFraction A

↳ Parent: Rat

Complexity

Conditions

Size

Total Lines	17
Code Lines	12

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	10
CRAP Score	3

Importance

Changes

Metric	Value
eloc	12
dl	0
loc	17
ccs	10
cts	10
cp	1
rs	9.8
c	0
b	0
f	0
cc	3
crap	3

import {EPSILON} from './config'
import {gcd} from './bigint'
import {rationalApproximation, continuedFraction} from './SternBrocotTree'

/**
 * @class Rational Number
 * @name Rat
 */
export class Rat {
  n: bigint
  d: bigint

  /**
   * Initialize a rational number.
   */
  constructor(numerator: bigint|number=0n, denominator: bigint|number=1n) {
    this.n = BigInt(numerator)
    this.d = BigInt(denominator)
    this.normalize()
  }

  /**
   * The decimal approximation.
   */
  valueOf(): number {
    return Number(this.n) / Number(this.d)
  }

  /**
   * The text representation.
   */
  toString(): string {
    return this.n.toString() + ( this.d === 1n ? '' : '/' + this.d.toString() )
  }

  /**
   * Returns a text profile of the number in various formats and it's value after common transformations.
   */
  public get profile(): string {
    const p = [`${this.constructor.name}: ${this.toString()} (≈${+this})`]
    p.push(`Continued: ${this.continuedFractionString()}`)
    p.push(`Babylonian: ${this.babylonianFractionString()}`)
    // p.push(`Egyptian: ${this.egyptianFractionString()}`)
    p.push(`psin(t): ${this.psin().toString()}`)
    p.push(`pcos(t): ${this.pcos().toString()}`)
    p.push(`ptan(t): ${this.ptan().toString()}`)
    return p.join('\n')
  }

  /**
   * Clone this.
   */
  clone(): Rat {
    return new Rat(this.n, this.d)
  }

  /**
   * Normalize the numerator and denominator by factoring out the common denominators.
   */
  normalize(): void {

    // normalize 0/1, 1/0, 0/0
    if (this.n === 0n) {
      if (this.d !== 0n) {
        this.d = 1n
      }
      return
    }
    if (this.d === 0n) {
      this.n = this.n > 0n ? 1n : -1n
      return
    }
    
    // normalize 1/1
    if (this.n === this.d) {
      this.n = this.d = 1n
      return
    }

    // remove negative denominator
    if (this.d < 0n) {
      this.n = -this.n
      this.d = -this.d
    }
    
    // reduce numerator and denomitator by the greatest common divisor
    const divisor = gcd(this.n, this.d)
    this.n /= divisor
    this.d /= divisor

  }

  /**
   * Add this to that.
   */
  add(that: Rat): Rat {
    const r = new Rat(this.n * that.d + that.n * this.d, this.d * that.d)
    r.normalize()
    return r
  }

  /**
   * Subtract this from that.
   */
  sub(that: Rat): Rat {
    return this.add(that.neg())
  }

  /**
   * Multiply that by this.
   */
  mul(that: Rat): Rat {
    const r = new Rat(this.n * that.n, this.d * that.d)
    r.normalize()
    return r
  }

  /**
   * Divide this by that.
   */
  div(that: Rat): Rat {
    const r = new Rat(this.n * that.d, this.d * that.n)
    r.normalize()
    return r
  }

  /**
   * Mediant of this and that.
   */
  mediant(that: Rat): Rat {
    const r = new Rat(this.n + that.n, this.d + that.d)
    r.normalize()
    return r
  }

  /**
   * Minimum of this and that.
   */
  min(that: Rat): Rat {
    return this.isLessThan(that) ? this : that
  }

  /**
   * Maximum of this and that.
   */
  max(that: Rat): Rat {
    return this.isGreaterThan(that) ? this : that
  }

  /**
   * Raise this to the power of that.
   */
  pow(that: Rat): Rat {
    // zero
    if (that.n === 0n) {
      return new Rat(1n)
    }
    // integer
    if (that.d === 1n) {
      return new Rat(this.n**that.n, this.d**that.n)
    }
    // fraction
    else {
      const estimate = Math.pow(+this, +that)
      return FloatToRat(estimate)
    }
  }

  /**
   * Returns the dot product of this and that.
   */
  dot(that: Rat): bigint {
    return this.n * that.n + this.d * that.d
  }

  /**
   * Returns true if this equals that.
   */
  equals(that: Rat): boolean {
    return this.n === that.n && this.d === that.d
  }

  /**
   * Returns true if this approximates the number.
   */
  approximates(n: number): boolean {
    return Math.abs(+this - n) < EPSILON
  }

  /**
   * Returns true if this is greater than that.
   */
  isGreaterThan(that: Rat): boolean {
    return this.n * that.d > that.n * this.d
  }

  /**
   * Returns true if this is less than that.
   */
  isLessThan(that: Rat): boolean {
    return this.n * that.d < that.n * this.d
  }

  /**
   * Absolute value of this.
   */
  abs(): Rat {
    const r = this.clone()
    if (r.n < 0) r.n = -r.n
    return r
  }

  /**
   * Opposite (negative) of this.
   */
  neg(): Rat {
    const r = this.clone()
    r.n = -r.n
    return r
  }

  /**
   * Returns true if this is less than zero.
   */
  isNegative(): boolean {
    return this.n < 0
  }

  /**
   * Returns true if this is a finite number.
   */
  isFinite(): boolean {
    return this.d !== 0n
  }

  /**
   * The reciprocal, or multiplicative inverse, of this.
   */
  inv(): Rat {
    return new Rat(this.d, this.n)
  }

  /**
   * Square root of this.
   */
  sqrt(): Rat {
    return this.root(2)
  }
 
  /**
   * Returns the nth root, a number which approximates this when multiplied by itself n times.
   */
  root(n: number): Rat {

    // Handle 0/1, 1/0, -1/0, 0/0, 1/1
    if (this.n === 0n || this.d === 0n || this.n === this.d) {
      return this.clone()
    }
    
    if (this.isNegative()) {
      throw `Roots of negative numbers like ${this.toString()} are too complex for this basic library`
    }

    return FloatToRat(Math.pow(+this, 1/n))
    // return FunctionToRat(r => r.pow(n), +this)
  }

  /**
   * Return the closest integer approximation.
   */
  round(): bigint {
    return BigInt(Math.round(+this))
  }

  /**
   * Return the integer part.
   */
  floor(): bigint {
    return BigInt(Math.floor(+this))
  }

  /**
   * Parametric sine: 2t / (1 + t²)
   * @see https://youtu.be/Ui8OvmzDn7o?t=245
   */
  psin(): Rat {
    if (this.d === 0n) return new Rat(0n)
    const one = new Rat(1)
    const two = new Rat(2)
    const n = two.mul(this)
    const d = one.add(this.pow(two))
    return n.div(d)
  }

  /**
   * Parametric cosine: (1 - t²) / (1 + t²)
   */
  pcos(): Rat {
    if (this.d === 0n) return new Rat(-1n)
    const one = new Rat(1)
    const two = new Rat(2)
    const t2 = this.pow(two)
    const n = one.sub(t2)
    const d = one.add(t2)
    return n.div(d)
  }

  /**
   * Parametric tangent: psin() / pcos()
   */
  ptan(): Rat {
    return this.psin().div(this.pcos())
  }

  /**
   * Returns the integers representing the continued fraction.
   */
  *continuedFraction(): Generator<number> {
    for (const n of continuedFraction(+this)) {
      yield n
    }
  }

  /**
   * Continued fraction as a string.
   */
  continuedFractionString(): string {
    const a: string[] = []
    for (const r of this.continuedFraction()) {
      a.push(r.toString())
    }
    const n = a.shift()
    if (n !== undefined) {
      let s = n.toString()
      if (a.length) {
        s += '; ' + a.join(', ')
      }
      return `[${s}]`
    }
    return '[1]'
  }

  /**
   * A dictionary with the exponents of 60 and their coefficents, which add up to this number.
   */
  babylonianFraction(): Array<string> {
    const a: string[] = []
    let n = Number(this.floor())
    let r = +this - n
    let d = 0
    // consume increasing powers until the integer part is divided
    for (let p=0; n > 0; p++) {
      d = n % 60
      //if (d !== 0) {
      a.unshift(`${d} * 60^${p}`)
      //}
      n = (n - d) / 60
    }
    // consume decreasing powers until the remainder is accumulated
    for (let p=-1; r > 0; p--) {
      r *= 60
      d = Math.floor(r)
      r -= d
      if (d !== 0) {
        a.push(`${d} * 60^${p}`)
      }
      if (Math.abs(d) < EPSILON) break
      n = (n - d) / 60
    }
    return a
  }

  /**
   * Babylonian fraction as a calc string.
   */
  babylonianFractionString(): string {
    const a: string[] = []
    const f = this.babylonianFraction()
    for (const i of f) {
      a.push(`${i}`)
    }
    return a.join(' + ')
  }

  /**
   * A list of unit fractions which add up to this number.
   */
  egyptianFraction(): Array<Rat> {
    const r: Rat[] = []
    const f = new Rat(1n)
    let t = this.abs()
    while (t.n !== 1n) {
      f.d++
      if (t.isGreaterThan(f)) {
        r.push(f.clone())
        t = t.sub(f)
      }
    }
    r.push(t)
    return r
  }

  /**
   * Egyptian fraction as a calc string.
   */
  egyptianFractionString(): string {
    return this.egyptianFraction().join(' + ')
  }

}

/**
 * Find a Rat approximation of the floating point number.
 */
export const FloatToRat = (n: number): Rat => {

  // Handle special values: 0/0, 1/0, -1/0
  if (isNaN(n)) return new Rat(0, 0)
  if (n===Infinity) return new Rat(1, 0)
  if (n===-Infinity) return new Rat(-1, 0)

  // Shortcut for numbers close to an integer or 1/integer
  if (Math.abs(n%1) < EPSILON) return new Rat(Math.round(n))
  if (Math.abs(1/n%1) < EPSILON) return new Rat(1, Math.round(1/n))

  // Traverse the Stern–Brocot tree until a good approximation is found
  // If negative, search for the positive value and negate the result
  const negative = n < 1
  const r = rationalApproximation(Math.abs(n))
  return negative ? r.neg() : r
}

/**
 * Parse the string for a numeric value and return it as a Rat.
 */
export const StringToRat = (s: string): Rat => {

  // Handle special values: 0/0, 1/0, -1/0
  if (s==='NaN') return new Rat(0, 0)
  if (s==='Infinity') return new Rat(1, 0)
  if (s==='-Infinity') return new Rat(-1, 0)

  const [n, d] = s.split('/', 2)
  if (d === undefined) {
    return FloatToRat(Number(n))
  }
  return new Rat(BigInt(n), BigInt(d))

}

/**
 * Pi, an approximation of the ratio between a circle's circumference and it's diameter.
 */
export const π = new Rat(3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587n, 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000n)

export default Rat


1	4	import {EPSILON} from './config'
2	4	import {gcd} from './bigint'
3	4	import {rationalApproximation, continuedFraction} from './SternBrocotTree'
4
5		/**
6		* @class Rational Number
7		* @name Rat
8		*/
9	4	export class Rat {
10		n: bigint
11		d: bigint
12
13		/**
14		* Initialize a rational number.
15		*/
16		constructor(numerator: bigint\|number=0n, denominator: bigint\|number=1n) {
17	321	this.n = BigInt(numerator)
18	321	this.d = BigInt(denominator)
19	321	this.normalize()
20		}
21
22		/**
23		* The decimal approximation.
24		*/
25		valueOf(): number {
26	33556538	return Number(this.n) / Number(this.d)
27		}
28
29		/**
30		* The text representation.
31		*/
32		toString(): string {
33	35	return this.n.toString() + ( this.d === 1n ? '' : '/' + 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	1	p.push(`Continued: ${this.continuedFractionString()}`)
42	1	p.push(`Babylonian: ${this.babylonianFractionString()}`)
43		// p.push(`Egyptian: ${this.egyptianFractionString()}`)
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	29	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	402	if (this.n === 0n) {
64	53	if (this.d !== 0n) {
65	50	this.d = 1n
66		}
67	53	return
68		}
69	349	if (this.d === 0n) {
70	16	this.n = this.n > 0n ? 1n : -1n
71	16	return
72		}
73
74		// normalize 1/1
75	333	if (this.n === this.d) {
76	90	this.n = this.d = 1n
77	90	return
78		}
79
80		// remove negative denominator
81	243	if (this.d < 0n) {
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	243	const divisor = gcd(this.n, this.d)
88	243	this.n /= divisor
89	243	this.d /= divisor
90
91		}
92
93		/**
94		* Add this to that.
95		*/
96		add(that: Rat): Rat {
97	39	const r = new Rat(this.n * that.d + that.n * this.d, this.d * that.d)
98	39	r.normalize()
99	39	return r
100		}
101
102		/**
103		* Subtract this from that.
104		*/
105		sub(that: Rat): Rat {
106	15	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 === 0n) {
156	1	return new Rat(1n)
157		}
158		// integer
159	24	if (that.d === 1n) {
160	23	return new Rat(this.nthat.n, this.dthat.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	16778245	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	569	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	4	const r = this.clone()
209	4	if (r.n < 0) r.n = -r.n
210	4	return r
211		}
212
213		/**
214		* Opposite (negative) of this.
215		*/
216		neg(): Rat {
217	17	const r = this.clone()
218	17	r.n = -r.n
219	17	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 !== 0n
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 === 0n \|\| this.d === 0n \|\| 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		* Return the integer part.
277		*/
278		floor(): bigint {
279	5	return BigInt(Math.floor(+this))
280		}
281
282		/**
283		* Parametric sine: 2t / (1 + t²)
284		* @see https://youtu.be/Ui8OvmzDn7o?t=245
285		*/
286		psin(): Rat {
287	13	if (this.d === 0n) return new Rat(0n)
288	11	const one = new Rat(1)
289	11	const two = new Rat(2)
290	11	const n = two.mul(this)
291	11	const d = one.add(this.pow(two))
292	11	return n.div(d)
293		}
294
295		/**
296		* Parametric cosine: (1 - t²) / (1 + t²)
297		*/
298		pcos(): Rat {
299	13	if (this.d === 0n) return new Rat(-1n)
300	11	const one = new Rat(1)
301	11	const two = new Rat(2)
302	11	const t2 = this.pow(two)
303	11	const n = one.sub(t2)
304	11	const d = one.add(t2)
305	11	return n.div(d)
306		}
307
308		/**
309		* Parametric tangent: psin() / pcos()
310		*/
311		ptan(): Rat {
312	5	return this.psin().div(this.pcos())
313		}
314
315		/**
316		* Returns the integers representing the continued fraction.
317		*/
318		*continuedFraction(): Generator<number> {
319	6	for (const n of continuedFraction(+this)) {
320	8	yield n
321		}
322		}
323
324		/**
325		* Continued fraction as a string.
326		*/
327		continuedFractionString(): string {
328	5	const a: string[] = []
329	5	for (const r of this.continuedFraction()) {
330	6	a.push(r.toString())
331		}
332	5	const n = a.shift()
333	5	if (n !== undefined) {
334	3	let s = n.toString()
335	3	if (a.length) {
336	2	s += '; ' + a.join(', ')
337		}
338	3	return `[${s}]`
339		}
340	2	return '[1]'
341		}
342
343		/**
344		* A dictionary with the exponents of 60 and their coefficents, which add up to this number.
345		*/
346		babylonianFraction(): Array<string> {
347	4	const a: string[] = []
348	4	let n = Number(this.floor())
349	4	let r = +this - n
350	4	let d = 0
351		// consume increasing powers until the integer part is divided
352	4	for (let p=0; n > 0; p++) {
353	5	d = n % 60
354		//if (d !== 0) {
355	5	a.unshift(`${d} * 60^${p}`)
356		//}
357	5	n = (n - d) / 60
358		}
359		// consume decreasing powers until the remainder is accumulated
360	4	for (let p=-1; r > 0; p--) {
361	61	r *= 60
362	61	d = Math.floor(r)
363	61	r -= d
364	61	if (d !== 0) {
365	59	a.push(`${d} * 60^${p}`)
366		}
367	61	if (Math.abs(d) < EPSILON) break
368	59	n = (n - d) / 60
369		}
370	4	return a
371		}
372
373		/**
374		* Babylonian fraction as a calc string.
375		*/
376		babylonianFractionString(): string {
377	4	const a: string[] = []
378	4	const f = this.babylonianFraction()
379	4	for (const i of f) {
380	64	a.push(`${i}`)
381		}
382	4	return a.join(' + ')
383		}
384
385		/**
386		* A list of unit fractions which add up to this number.
387		*/
388		egyptianFraction(): Array<Rat> {
389	2	const r: Rat[] = []
390	2	const f = new Rat(1n)
391	2	let t = this.abs()
392	2	while (t.n !== 1n) {
393	566	f.d++
394	566	if (t.isGreaterThan(f)) {
395	3	r.push(f.clone())
396	3	t = t.sub(f)
397		}
398		}
399	2	r.push(t)
400	2	return r
401		}
402
403		/**
404		* Egyptian fraction as a calc string.
405		*/
406		egyptianFractionString(): string {
407	2	return this.egyptianFraction().join(' + ')
408		}
409
410		}
411
412		/**
413		* Find a Rat approximation of the floating point number.
414		*/
415	4	export const FloatToRat = (n: number): Rat => {
416
417		// Handle special values: 0/0, 1/0, -1/0
418	16	if (isNaN(n)) return new Rat(0, 0)
419	15	if (n===Infinity) return new Rat(1, 0)
420	10	if (n===-Infinity) return new Rat(-1, 0)
421
422		// Shortcut for numbers close to an integer or 1/integer
423	9	if (Math.abs(n%1) < EPSILON) return new Rat(Math.round(n))
424	6	if (Math.abs(1/n%1) < EPSILON) return new Rat(1, Math.round(1/n))
425
426		// Traverse the Stern–Brocot tree until a good approximation is found
427		// If negative, search for the positive value and negate the result
428	4	const negative = n < 1
429	4	const r = rationalApproximation(Math.abs(n))
430	4	return negative ? r.neg() : r
431		}
432
433		/**
434		* Parse the string for a numeric value and return it as a Rat.
435		*/
436	4	export const StringToRat = (s: string): Rat => {
437
438		// Handle special values: 0/0, 1/0, -1/0
439	5	if (s==='NaN') return new Rat(0, 0)
440	4	if (s==='Infinity') return new Rat(1, 0)
441	3	if (s==='-Infinity') return new Rat(-1, 0)
442
443	2	const [n, d] = s.split('/', 2)
444	2	if (d === undefined) {
445	1	return FloatToRat(Number(n))
446		}
447	1	return new Rat(BigInt(n), BigInt(d))
448
449		}
450
451		/**
452		* Pi, an approximation of the ratio between a circle's circumference and it's diameter.
453		*/
454	4	export const π = new Rat(3141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587n, 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000n)
455
456		export default Rat
457

acerix / cnum

Push — main ( 12d9ec...5a557a )

Rat.egyptianFraction A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like