// Egypt.java
// Andrew Davison, ad@coe.psu.ac.th, April 2023


/* The user supplies a numerator and denominator of a fraction,
   and this is converted into a list of Egyptian fractions using
   Fibonacci's greedy algorithm, which is then summed
   to see if there's been any loss in accuracy.

   Egyptian Fractions
   http://en.wikipedia.org/wiki/Egyptian_fraction
and
   https://www.ics.uci.edu/~eppstein/numth/egypt/

   The ancient Egyptians represented fractions such as 3/5 as a 
   sum of distinct unit fractions, that is, fractions whose 
   numerators are one, e.g. 1/2, 1/10. Note that the
   sum 1/5 + 1/5 + 1/5 would not be acceptable because 
   the unit fractions aren't distinct.
   
   Fibonacci's greedy algorithm expands 
   the fraction x/y by repeatedly performing the replacement:

   x/y =   1 /( / y/x \ )   +
           (-y mod x ) / (y *( / y/x \ ))
 
   http://en.wikipedia.org/wiki/Greedy_algorithm_for_Egyptian_fractions


   Online calculators for double checking results:
      *  https://goodcalculators.com/egyptian-fraction-calculator/
      *  https://planetcalc.com/8465/

   Usage:
     > compile Egypt.java
     > run Egypt <numerator> <denominator>
   e.g.
     > run Egypt 7 13
     > run Egypt 3 7
     > run Egypt 9 11
     > run Egypt 8 11

     > run Egypt 5 121    // takes a while before it gives up!
                          // so this result lacks accuracy
     It's trying to generate:
         5/121 = 1/25 + 1/757 + 1/763309 + 1/873960180913 + 
                 1/1527612795642093418846225
     but a better answer is:
         5/121 = 1/25 + 1/759 + 1/208725

     > run Egypt 7 13
     Fraction to decompose: 7 / 13
     Using 1 / 2
     Using 1 / 26
     Fractions list: [1 / 2, 1 / 26]
     List sum: 7 / 13
     Absolute diff from original fraction: 0
*/


import java.util.*;
import java.math.*;

import org.apache.commons.numbers.fraction.BigFraction;


public class Egypt 
{
  private static final int MAX_DENOM = 100000000;


  public static void main(String[] args) 
  {
    if (args.length != 2) {
      System.out.println("Usage: java Egypt <numerator> <denominator>");
      return;
    }
    int n = Math.abs(Nut.parseInt(args[0]));
    int d = Math.abs(Nut.parseInt(args[1]));
    BigFraction f = BigFraction.of(n, d);    
    System.out.println("Fraction to decompose: " + f);

    // Make sure fraction is between 0 and 1
    if (f.compareTo(BigFraction.ZERO) <= 0) {
      System.out.println("BigFraction is 0 or negative");
      return;
    }
    if (f.compareTo(BigFraction.ONE) >= 0) {
      System.out.println("BigFraction is 1 or more");
      return;
    }

    ArrayList<BigFraction> fracs = greedyFracs(f);
    System.out.println("Fractions list: " + fracs);

    BigFraction sum = sumList(fracs);
    System.out.println("List sum: " +  sum);

    BigFraction diff = f.subtract(sum).abs();
    System.out.println("Absolute diff from original fraction: " + diff );
  }  // end of main()



  private static ArrayList<BigFraction> greedyFracs(BigFraction f) 
  {
    BigFraction rem = f.add(BigFraction.ZERO);
    ArrayList<BigFraction> vals = new ArrayList<BigFraction>(); 

    int denom = 2;  // first candidate tested will be 1/2
    boolean isDone = false;
    while (!isDone) {
      if (denom == MAX_DENOM) {
      // if (denom == Integer.MAX_VALUE) {
        System.out.println("Denominator reached max: " + MAX_DENOM +
                  "; giving up search");
        break;
      }
      if (vals.size() > 10) {
        System.out.println("List is too big; giving up search");
        break;
      }

      BigFraction candidate = BigFraction.of(1, denom);   

      // If the candidate is less than the current remainder,
      // add it to the vals list and subtract it from rem
      if (candidate.compareTo(rem) <= 0) {
        vals.add(candidate);
        System.out.println("Using " + candidate);
        rem = rem.subtract(candidate);
      }

      // If the remainder is 0, we're finished
      if (rem.equals(BigFraction.ZERO))
        isDone = true;
      else {
        // If the remainder's numerator is 1, 
        // add it to the list and we're finished
        if (rem.getNumerator().equals(BigInteger.ONE)) {
          vals.add(rem);
          System.out.println("Using " + rem);
          isDone = true;
        }
        else
          denom++;
      }
    }
    return vals;
  }  // end of greedyFracs()


  private static BigFraction sumList(ArrayList<BigFraction> vals)
  {
    BigFraction sum = BigFraction.ZERO;
    for (BigFraction val : vals)
      sum = sum.add(val);
    return sum;
  }  // end of sumList()

}  // end of Egypt class