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}