001/*
002 * $Id$
003 */
004
005package edu.jas.arith;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import org.apache.logging.log4j.LogManager;
012import org.apache.logging.log4j.Logger;
013
014
015/**
016 * Arithmetic utilities.
017 * @author Heinz Kredel
018 */
019
020public class ArithUtil {
021
022
023    private static final Logger logger = LogManager.getLogger(ArithUtil.class);
024
025
026    private static final boolean debug = logger.isDebugEnabled();
027
028
029    /**
030     * Continued fraction.
031     * @param A rational number.
032     * @return continued fraction for A.
033     */
034    public static List<BigInteger> continuedFraction(BigRational A) {
035        List<BigInteger> cf = new ArrayList<BigInteger>();
036        if (A == null) {
037            return cf;
038        }
039        if (A.isZERO() || A.isONE()) {
040            cf.add(new BigInteger(A.num));
041            return cf;
042        }
043        BigRational x = A;
044        BigInteger q = new BigInteger(x.floor());
045        cf.add(q);
046        BigRational xd = x.subtract(new BigRational(q));
047        while (!xd.isZERO()) {
048            x = xd.inverse();
049            q = new BigInteger(x.floor());
050            cf.add(q);
051            xd = x.subtract(new BigRational(q));
052        }
053        if (debug) {
054            logger.info("cf = {}", cf);
055        }
056        return cf;
057    }
058
059
060    /**
061     * Continued fraction approximation.
062     * @param A continued fraction.
063     * @return ratonal number approximation for A.
064     */
065    public static BigRational continuedFractionApprox(List<BigInteger> A) {
066        BigRational ab = BigRational.ZERO;
067        if (A == null || A.isEmpty()) {
068            return ab;
069        }
070        BigInteger a2, a1, b2, b1, a, b;
071        a2 = BigInteger.ZERO;
072        a1 = BigInteger.ONE;
073        b2 = BigInteger.ONE;
074        b1 = BigInteger.ZERO;
075        for (BigInteger q : A) {
076            a = q.multiply(a1).sum(a2);
077            b = q.multiply(b1).sum(b2);
078            //System.out.println("A/B = " + new BigRational(a,b));
079            a2 = a1;
080            a1 = a;
081            b2 = b1;
082            b1 = b;
083        }
084        ab = new BigRational(a1, b1);
085        return ab;
086    }
087
088}