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