Continued fraction/Arithmetic/G(matrix ng, continued fraction n1, continued fraction n2): Difference between revisions
Continued fraction/Arithmetic/G(matrix ng, continued fraction n1, continued fraction n2) (view source)
Revision as of 17:20, 20 November 2023
, 5 months ago→{{header|Wren}}: Changed to Wren S/H
m (→{{header|Wren}}: Changed to Wren S/H) |
|||
| (8 intermediate revisions by 3 users not shown) | |||
Line 1:
{{
This task performs the basic mathematical functions on 2 continued fractions. This requires the full version of matrix NG:
: <math>\begin{bmatrix}
Line 1,823:
===Using multiple precision numbers===
{{trans|Standard ML}}
{{libheader|ats2-xprelude}}
{{libheader|GMP}}
For this program you need [https://sourceforge.net/p/chemoelectric/ats2-xprelude ats2-xprelude].
Line 6,750 ⟶ 6,752:
sqrt(2) * sqrt(2) => [2]
sqrt(2) / sqrt(2) => [1]
</pre>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.List;
public final class ContinuedFractionArithmeticG2 {
public static void main(String[] aArgs) {
test("[3; 7] + [0; 2]", new NG( new NG8(0, 1, 1, 0, 0, 0, 0, 1), new R2cf(1, 2), new R2cf(22, 7) ),
new NG( new NG4(2, 1, 0, 2), new R2cf(22, 7) ));
test("[1; 5, 2] * [3; 7]", new NG( new NG8(1, 0, 0, 0, 0, 0, 0, 1), new R2cf(13, 11), new R2cf(22, 7) ),
new R2cf(286, 77) );
test("[1; 5, 2] - [3; 7]", new NG( new NG8(0, 1, -1, 0, 0, 0, 0, 1), new R2cf(13, 11), new R2cf(22, 7) ),
new R2cf(-151, 77) );
test("Divide [] by [3; 7]",
new NG( new NG8(0, 1, 0, 0, 0, 0, 1, 0), new R2cf(22 * 22, 7 * 7), new R2cf(22,7)) );
test("([0; 3, 2] + [1; 5, 2]) * ([0; 3, 2] - [1; 5, 2])",
new NG( new NG8(1, 0, 0, 0, 0, 0, 0, 1),
new NG( new NG8(0, 1, 1, 0, 0, 0, 0, 1),
new R2cf(2, 7), new R2cf(13, 11)),
new NG( new NG8(0, 1, -1, 0, 0, 0, 0, 1), new R2cf(2, 7), new R2cf(13, 11) ) ),
new R2cf(-7797, 5929) );
}
private static void test(String aDescription, ContinuedFraction... aFractions) {
System.out.println("Testing: " + aDescription);
for ( ContinuedFraction fraction : aFractions ) {
while ( fraction.hasMoreTerms() ) {
System.out.print(fraction.nextTerm() + " ");
}
System.out.println();
}
System.out.println();
}
private static abstract class MatrixNG {
protected abstract void consumeTerm();
protected abstract void consumeTerm(int aN);
protected abstract boolean needsTerm();
protected int configuration = 0;
protected int currentTerm = 0;
protected boolean hasTerm = false;
}
private static class NG4 extends MatrixNG {
public NG4(int aA1, int aA, int aB1, int aB) {
a1 = aA1; a = aA; b1 = aB1; b = aB;
}
public void consumeTerm() {
a = a1;
b = b1;
}
public void consumeTerm(int aN) {
int temp = a; a = a1; a1 = temp + a1 * aN;
temp = b; b = b1; b1 = temp + b1 * aN;
}
public boolean needsTerm() {
if ( b1 == 0 && b == 0 ) {
return false;
}
if ( b1 == 0 || b == 0 ) {
return true;
}
currentTerm = a / b;
if ( currentTerm == a1 / b1 ) {
int temp = a; a = b; b = temp - b * currentTerm;
temp = a1; a1 = b1; b1 = temp - b1 * currentTerm;
hasTerm = true;
return false;
}
return true;
}
private int a1, a, b1, b;
}
private static class NG8 extends MatrixNG {
public NG8(int aA12, int aA1, int aA2, int aA, int aB12, int aB1, int aB2, int aB) {
a12 = aA12; a1 = aA1; a2 = aA2; a = aA; b12 = aB12; b1 = aB1; b2 = aB2; b = aB;
}
public void consumeTerm() {
if ( configuration == 0 ) {
a = a1; a2 = a12;
b = b1; b2 = b12;
} else {
a = a2; a1 = a12;
b = b2; b1 = b12;
}
}
public void consumeTerm(int aN) {
if ( configuration == 0 ) {
int temp = a; a = a1; a1 = temp + a1 * aN;
temp = a2; a2 = a12; a12 = temp + a12 * aN;
temp = b; b = b1; b1 = temp + b1 * aN;
temp = b2; b2 = b12; b12 = temp + b12 * aN;
} else {
int temp = a; a = a2; a2 = temp + a2 * aN;
temp = a1; a1 = a12; a12 = temp + a12 * aN;
temp = b; b = b2; b2 = temp + b2 * aN;
temp = b1; b1 = b12; b12 = temp + b12 * aN;
}
}
public boolean needsTerm() {
if ( b1 == 0 && b == 0 && b2 == 0 && b12 == 0 ) {
return false;
}
if ( b == 0 ) {
configuration = ( b2 == 0 ) ? 0 : 1;
return true;
}
ab = (double) a / b;
if ( b2 == 0 ) {
configuration = 1;
return true;
}
a2b2 = (double) a2 / b2;
if ( b1 == 0 ) {
configuration = 0;
return true;
}
a1b1 = (double) a1 / b1;
if ( b12 == 0 ) {
configuration = setConfiguration();
return true;
}
a12b12 = (double) a12 / b12;
currentTerm = (int) ab;
if ( currentTerm == (int) a1b1 && currentTerm == (int) a2b2 && currentTerm == (int) a12b12 ) {
int temp = a; a = b; b = temp - b * currentTerm;
temp = a1; a1 = b1; b1 = temp - b1 * currentTerm;
temp = a2; a2 = b2; b2 = temp - b2 * currentTerm;
temp = a12; a12 = b12; b12 = temp - b12 * currentTerm;
hasTerm = true;
return false;
}
configuration = setConfiguration();
return true;
}
private int setConfiguration() {
return ( Math.abs(a1b1 - ab) > Math.abs(a2b2 - ab) ) ? 0 : 1;
}
private int a12, a1, a2, a, b12, b1, b2, b;
private double ab, a1b1, a2b2, a12b12;
}
private static interface ContinuedFraction {
public boolean hasMoreTerms();
public int nextTerm();
}
private static class R2cf implements ContinuedFraction {
public R2cf(int aN1, int aN2) {
n1 = aN1; n2 = aN2;
}
public boolean hasMoreTerms() {
return Math.abs(n2) > 0;
}
public int nextTerm() {
final int term = n1 / n2;
final int temp = n2;
n2 = n1 - term * n2;
n1 = temp;
return term;
}
private int n1, n2;
}
private static class NG implements ContinuedFraction {
public NG(NG4 aNG, ContinuedFraction aCF) {
matrixNG = aNG;
cf.add(aCF);
}
public NG(NG8 aNG, ContinuedFraction aCF1, ContinuedFraction aCF2) {
matrixNG = aNG;
cf.add(aCF1); cf.add(aCF2);
}
public boolean hasMoreTerms() {
while ( matrixNG.needsTerm() ) {
if ( cf.get(matrixNG.configuration).hasMoreTerms() ) {
matrixNG.consumeTerm(cf.get(matrixNG.configuration).nextTerm());
} else {
matrixNG.consumeTerm();
}
}
return matrixNG.hasTerm;
}
public int nextTerm() {
matrixNG.hasTerm = false;
return matrixNG.currentTerm;
}
private MatrixNG matrixNG;
private List<ContinuedFraction> cf = new ArrayList<ContinuedFraction>();
}
}
</syntaxhighlight>
{{ out }}
<pre>
Testing: [3; 7] + [0; 2]
3 1 1 1 4
3 1 1 1 4
Testing: [1; 5, 2] * [3; 7]
3 1 2 2
3 1 2 2
Testing: [1; 5, 2] - [3; 7]
-1 -1 -24 -1 -2
-1 -1 -24 -1 -2
Testing: Divide [] by [3; 7]
3 7
Testing: ([0; 3, 2] + [1; 5, 2]) * ([0; 3, 2] - [1; 5, 2])
-1 -3 -5 -1 -2 -1 -26 -3
-1 -3 -5 -1 -2 -1 -26 -3
</pre>
Line 8,733 ⟶ 8,993:
sqrt2 / sqrt2 => [1]
</pre>
=={{header|Owl Lisp}}==
{{trans|Mercury}}
{{works with|Owl Lisp|0.2.1}}
<syntaxhighlight lang="scheme">
;;--------------------------------------------------------------------
;;
;; A continued fraction will be represented as an infinite lazy list
;; of terms, where a term is either an integer or the symbol 'infinity
;;
;;--------------------------------------------------------------------
(define (cf2maxterms-string maxterms cf)
(let repeat ((p cf)
(i 0)
(s "["))
(let ((term (lcar p))
(rest (lcdr p)))
(if (eq? term 'infinity)
(string-append s "]")
(if (>= i maxterms)
(string-append s ",...]")
(let ((separator (case i
((0) "")
((1) ";")
(else ",")))
(term-str (number->string term)))
(repeat rest (+ i 1)
(string-append s separator term-str))))))))
(define (cf2string cf)
(cf2maxterms-string 20 cf))
;;--------------------------------------------------------------------
(define (repeated-term-cf term)
(lunfold (lambda (x) (values x x))
term
(lambda (x) #false)))
(define cf-end (repeated-term-cf 'infinity))
(define (i2cf term) (pair term cf-end))
(define (r2cf fraction)
;; The entire finite-length continued fraction is constructed in
;; reverse order. The list is then rebuilt in the correct order, and
;; given an infinite number of 'infinity terms as its tail.
(let repeat ((n (numerator fraction))
(d (denominator fraction))
(revlst #null))
(if (zero? d)
(lappend (reverse revlst) cf-end)
(let-values (((q r) (truncate/ n d)))
(repeat d r (cons q revlst))))))
(define (->cf x)
(cond ((integer? x) (i2cf x))
((rational? x) (r2cf x))
(else x)))
;;--------------------------------------------------------------------
(define (maybe-divide a b)
(if (zero? b)
(values #false #false)
(truncate/ a b)))
(define integer-exceeds-processing-threshold?
(let ((threshold+1 (expt 2 512)))
(lambda (i) (>= (abs i) threshold+1))))
(define (any-exceed-processing-threshold? lst)
(any integer-exceeds-processing-threshold? lst))
(define integer-exceeds-infinitizing-threshold?
(let ((threshold+1 (expt 2 64)))
(lambda (i) (>= (abs i) threshold+1))))
(define (ng8-values ng)
(values (list-ref ng 0)
(list-ref ng 1)
(list-ref ng 2)
(list-ref ng 3)
(list-ref ng 4)
(list-ref ng 5)
(list-ref ng 6)
(list-ref ng 7)))
(define (absorb-x-term ng x y)
(let-values (((a12 a1 a2 a b12 b1 b2 b) (ng8-values ng)))
(define (no-more-x)
(values (list a12 a1 a12 a1 b12 b1 b12 b1) cf-end y))
(let ((term (lcar x)))
(if (eq? term 'infinity)
(no-more-x)
(let ((new-ng (list (+ a2 (* a12 term))
(+ a (* a1 term)) a12 a1
(+ b2 (* b12 term))
(+ b (* b1 term)) b12 b1)))
(cond ((any-exceed-processing-threshold? new-ng)
;; Pretend we have reached the end of x.
(no-more-x))
(else (values new-ng (lcdr x) y))))))))
(define (absorb-y-term ng x y)
(let-values (((a12 a1 a2 a b12 b1 b2 b) (ng8-values ng)))
(define (no-more-y)
(values (list a12 a12 a2 a2 b12 b12 b2 b2) x cf-end))
(let ((term (lcar y)))
(if (eq? term 'infinity)
(no-more-y)
(let ((new-ng (list (+ a1 (* a12 term)) a12
(+ a (* a2 term)) a2
(+ b1 (* b12 term)) b12
(+ b (* b2 term)) b2)))
(cond ((any-exceed-processing-threshold? new-ng)
;; Pretend we have reached the end of y.
(no-more-y))
(else (values new-ng x (lcdr y)))))))))
(define (apply-ng8 ng x y)
(let repeat ((ng ng)
(x (->cf x))
(y (->cf y)))
(let-values (((a12 a1 a2 a b12 b1 b2 b) (ng8-values ng)))
(cond ((every zero? (list b12 b1 b2 b)) cf-end)
((every zero? (list b2 b))
(let-values (((ng x y) (absorb-x-term ng x y)))
(repeat ng x y)))
((any zero? (list b2 b))
(let-values (((ng x y) (absorb-y-term ng x y)))
(repeat ng x y)))
((zero? b1)
(let-values (((ng x y) (absorb-x-term ng x y)))
(repeat ng x y)))
(else
(let-values (((q12 r12) (maybe-divide a12 b12))
((q1 r1) (maybe-divide a1 b1))
((q2 r2) (maybe-divide a2 b2))
((q r) (maybe-divide a b)))
(cond
((and (not (zero? b12))
(= q q12) (= q q1) (= q q2))
;; Output a term.
(if (integer-exceeds-infinitizing-threshold? q)
cf-end ; Pretend the term is infinite.
(let ((new-ng (list b12 b1 b2 b r12 r1 r2 r)))
(pair q (repeat new-ng x y)))))
(else
;; Put a1, a2, and a over a common denominator
;; and compare some magnitudes.
(let ((n1 (* a1 b2 b))
(n2 (* a2 b1 b))
(n (* a b1 b2)))
(let ((absorb-term
(if (> (abs (- n1 n)) (abs (- n2 n)))
absorb-x-term
absorb-y-term)))
(let-values (((ng x y) (absorb-term ng x y)))
(repeat ng x y))))))))))))
;;--------------------------------------------------------------------
(define (make-ng8-operation ng) (lambda (x y) (apply-ng8 ng x y)))
(define cf+ (make-ng8-operation '(0 1 1 0 0 0 0 1)))
(define cf- (make-ng8-operation '(0 1 -1 0 0 0 0 1)))
(define cf* (make-ng8-operation '(1 0 0 0 0 0 0 1)))
(define cf/ (make-ng8-operation '(0 1 0 0 0 0 1 0)))
;;--------------------------------------------------------------------
(define golden-ratio (repeated-term-cf 1))
(define silver-ratio (repeated-term-cf 2))
(define sqrt2 (pair 1 silver-ratio))
(define sqrt5 (pair 2 (repeated-term-cf 4)))
;;--------------------------------------------------------------------
(define (show expression cf note)
(let* ((cf (cf2string cf))
(expr-len (string-length expression))
(expr-pad-len (max 0 (- 18 expr-len)))
(expr-pad (make-string expr-pad-len #\space)))
(display expr-pad)
(display expression)
(display " => ")
(display cf)
(unless (string=? note "")
(let* ((cf-len (string-length cf))
(cf-pad-len (max 0 (- 48 cf-len)))
(cf-pad (make-string cf-pad-len #\space)))
(display cf-pad)
(display note)))
(newline)))
(show "13/11 + 1/2" (cf+ 13/11 1/2) "(cf+ 13/11 1/2)")
(show "22/7 + 1/2" (cf+ 22/7 1/2) "(cf+ 22/7 1/2)")
(show "22/7 * 1/2" (cf* 22/7 1/2) "(cf* 22/7 1/2)")
(show "golden ratio" golden-ratio "(repeated-term-cf 1)")
(show "silver ratio" silver-ratio "(repeated-term-cf 2)")
(show "sqrt(2)" sqrt2 "(pair 1 silver-ratio)")
(show "sqrt(2)" (cf- silver-ratio 1) "(cf- silver-ratio 1)")
(show "sqrt(5)" sqrt5 "(pair 2 (repeated-term-cf 4)")
(show "sqrt(5)" (cf- (cf* 2 golden-ratio) 1)
"(cf- (cf* 2 golden-ratio) 1)")
(show "sqrt(2) + sqrt(2)" (cf+ sqrt2 sqrt2) "(cf+ sqrt2 sqrt2)")
(show "sqrt(2) - sqrt(2)" (cf- sqrt2 sqrt2) "(cf- sqrt2 sqrt2)")
(show "sqrt(2) * sqrt(2)" (cf* sqrt2 sqrt2) "(cf* sqrt2 sqrt2)")
(show "sqrt(2) / sqrt(2)" (cf/ sqrt2 sqrt2) "(cf/ sqrt2 sqrt2)")
(show "(1 + 1/sqrt(2))/2" (cf/ (cf+ 1 (cf/ 1 sqrt2)) 2)
"(cf/ (cf+ 1 (cf/ 1 sqrt2)) 2)")
(show "(1 + 1/sqrt(2))/2" (apply-ng8 '(0 1 0 0 0 0 2 0)
silver-ratio sqrt2)
"(apply-ng8 '(0 1 0 0 0 0 2 0) sqrt2 sqrt2)")
(show "(1 + 1/sqrt(2))/2" (apply-ng8 '(1 0 0 1 0 0 0 8)
silver-ratio silver-ratio)
"(apply-ng8 '(1 0 0 1 0 0 0 8) silver-ratio silver-ratio)")
;;--------------------------------------------------------------------
</syntaxhighlight>
{{out}}
<pre>$ ol continued-fraction-task-Owl.scm
13/11 + 1/2 => [1;1,2,7] (cf+ 13/11 1/2)
22/7 + 1/2 => [3;1,1,1,4] (cf+ 22/7 1/2)
22/7 * 1/2 => [1;1,1,3] (cf* 22/7 1/2)
golden ratio => [1;1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,...] (repeated-term-cf 1)
silver ratio => [2;2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...] (repeated-term-cf 2)
sqrt(2) => [1;2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...] (pair 1 silver-ratio)
sqrt(2) => [1;2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,...] (cf- silver-ratio 1)
sqrt(5) => [2;4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,...] (pair 2 (repeated-term-cf 4)
sqrt(5) => [2;4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,...] (cf- (cf* 2 golden-ratio) 1)
sqrt(2) + sqrt(2) => [2;1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...] (cf+ sqrt2 sqrt2)
sqrt(2) - sqrt(2) => [0] (cf- sqrt2 sqrt2)
sqrt(2) * sqrt(2) => [2] (cf* sqrt2 sqrt2)
sqrt(2) / sqrt(2) => [1] (cf/ sqrt2 sqrt2)
(1 + 1/sqrt(2))/2 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...] (cf/ (cf+ 1 (cf/ 1 sqrt2)) 2)
(1 + 1/sqrt(2))/2 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...] (apply-ng8 '(0 1 0 0 0 0 2 0) sqrt2 sqrt2)
(1 + 1/sqrt(2))/2 => [0;1,5,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,4,1,...] (apply-ng8 '(1 0 0 1 0 0 0 8) silver-ratio silver-ratio)</pre>
=={{header|Phix}}==
Line 10,383 ⟶ 10,885:
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="
construct new() {
_cfn = 0
| |||