<?php
/*
CLASS FractionListObj
    A fraction list object is instantiated with three pieces of data:  
    a numerator range, a denominator, and a number base.

PROPERTIES
    public:
        $base: number base (defaults to 10).
        $fraction: list of fraction objects (FractionObj).


METHODS
        
    PUBLIC __construct:  Object constructor.  Builds list of fraction objects.


    PRIVATE parse:  parses the numerator range and returns an array.  This is
    expected to be either one integer or else a starting and stopping integer.

*/
class FractionListObj {
    public $base, $fraction;

    public function __construct($num, $denom, $base)
    {
        list($num1, $num2) = $this->parse($num);
        if ($num2 >= $denom) { $num2 = $denom - 1; }
        $this->base = strlen($base) == 0 ? 10 : $base;
        if ($this->base != 10) {
            $num1 = base_convert($num1, $this->base, 10);
            $num2 = base_convert($num2, $this->base, 10);
            $denom = base_convert($denom, $this->base, 10);
        }

        for ($i = $num1; $i <= $num2; $i++) {
            $this->fraction[$i] = new FractionObj($i, $denom, $base);
        }
    }


    private function parse($n) {
        $nrange = array(); 
        if (preg_match("/^([0-9a-zA-Z]+)\s*-\s*([0-9a-zA-Z]+)$/", $n, $matches)) {
            $nrange[] = $matches[1]; 
            $nrange[] = $matches[2]; 
        }
        else {
            $nrange[] = $n;
            $nrange[] = $n;
        }
        return $nrange;
    }
}


/*
CLASS FractionObj
    A fraction object is instantiated with three pieces of data:  a numerator,
    a denominator, and a number base.

PROPERTIES
    private:
        $prime: array of prime numbers.

    public:
        $num: numerator.
        $denom: denominator.
        $reduced_num: reduced numerator.
        $reduced_denom: reduced denominator.
        $base: number base.
        $fraction: fraction description.
        $section_list: list of sections in a decimal expansion.  Sections are:
            non-repeating, initial repeating portion, repeating portion complement. 
        $decimal: decimal expansion.
        $decimal_places: number of decimal places in expansion.
        $repeating: number of repeating decimals in expansion.

    For example, if the fraction is 1/6 (base 10):
        $num: 1
        $denom: 6
        $reduced_num: 1
        $reduced_denom: 6
        $base: 10
        $fraction: 1 / 6
        $decimal_places: 2
        $repeating: 1
        $decimal: .16
        $section_list: ('1', '6', '');

    If the fraction is 3/6 (base 10):
        $num: 3
        $denom: 6
        $reduced_num: 1
        $reduced_denom: 2
        $base: 10
        $fraction: 3 / 6 (1 / 2) 
        $decimal_places: 1
        $repeating: 0
        $decimal: .5
        $section_list: ('5', '', '');

    If the fraction is 1/7 (base 10):
        $num: 1
        $denom: 7
        $reduced_num: 1
        $reduced_denom: 7
        $base: 10
        $fraction: 1 / 7
        $decimal_places: 6
        $repeating: 6
        $decimal: .142857
        $section_list: ('', '142', '857');

METHODS
        
    PUBLIC __construct:  Object constructor.  Sets the public properties
    directly, or else calls the methods that sets them.


    PRIVATE calc_decimal:  Calculate the decimal expansion for the specified 
    numerator, denominator, and base.  Calculation is performed using long-
    division, rather than relying on the computer's internal precision.  In 
    this way, the calculation can be performed to far more decimal places than 
    otherwise possible.


    PRIVATE count_non_repeating.  Calculate and return the number of decimal 
    places that do not repeat, or -1 if the fraction resolves.  The number of 
    non-repeating decimal places is calculated by comparing the denominator's 
    prime factors with those of the number base.


    PRIVATE function get_gcf:  Calculate and return the greatest common factor 
    of two integers.

*/
class FractionObj {
    public $num, $denom, $reduced_num, $reduced_denom, $base, $fraction, $section_list, $decimal, $decimal_length, $repeating;
    private $primes = array(
        -1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
    );


    public function __construct($num, $denom, $base)
    {
        $this->num = $num;
        $this->denom = $denom;
        $gcf = $this->get_gcf($num, $denom);  // GCF of numerator and denominator, for ensuring a reduced fraction.
        $this->reduced_num = $num / $gcf;
        $this->reduced_denom = $denom / $gcf;
        $this->base = $base;
        if ($this->reduced_denom < $this->denom) {
            $this->fraction = "$this->num / $this->denom ($this->reduced_num / $this->reduced_denom)";
        }
        else {
            $this->fraction = "$this->reduced_num / $this->reduced_denom";
        }
        // calc_decimal sets three additional properties:  decimal_length, repeating, and decimal.
        $this->calc_decimal();
    }


    private function calc_decimal() {
        // (Due to the complexity of the process, this method is copiously commented; hopefully this will clarify rather than obfuscate.)

        // ----- BEGIN INITIALIZATION -----
        // $section_list is a list of the decimal expansion's sections; to be imploded at the end of the calc_decimal method.  
        // The possible sections are:
        //   non-repeating portion,
        //   initial repeating portion,
        //   repeating portion complement. 
        // Examples:
        //   1/2 = .5.  Non-repeating portion: 5; no repeating portions.
        //   1/6 = .1666...  Non-repeating portion: 1; initial repeating portion: 6; no repeating portion complement.
        //   1/7 = .142857...  No non-repeating potion; initial repeating portion: 142; repeating potion complement: 857.
        $section_list = array('', '', '');
        $section_ndx = 0;

        // Call the count_non_repeating method to determine the number of non-repeating digits in the decimal expansion.
        // If the fraction resolves (i.e., has no repeating portion), the count_non_repeating method returns -1.
        $non_repeating = $this->count_non_repeating();
        // If a decimal expansion repeats, non_repeating_tally is used to detect the position at which the repetition begins.
        // If there is no repetition, non_repeating_tally is set to one less than the denominator, which is a position at or beyond the decimal expansion's maximum possible length.
        // Examples:  1/3 = .33333...  The whole thing repeats, so non_repeating_tally is 0.
        //            1/4 = .25  The fraction resolves.  non_repeating_tally is one 3.
        //            1/6 = .1666...  Only the 6's repeat, so non_repeating_tally is 1.
        $non_repeating_tally = $non_repeating == -1 ? $this->reduced_denom - 1 : $non_repeating;
        // The remainder_flag array contains one element for every possible remainder of a division involving the denominator.  This means the number of elements is one less than the denominator.
        $remainder_flag_list = array_fill(1, $this->reduced_denom - 1, false);
        $repeating_decimal_flag = $non_repeating != -1;
        $start_repeat = 0;
        $step_digit = 0;
        $step_remainder = $this->reduced_num;
        $decimal_length = 0;
        $linelength = 54;
        // ----- END INITIALIZATION -----

        // ----- BEGIN LONG DIVISION -----
        // Continue the process as long as both of two conditions are true:
        //   a) there is a remainder,
        //   b) the current remainder ($step_remainder) has not yet been encountered.
        while ($step_remainder != 0 && !$remainder_flag_list[$step_remainder]) {
            // Mark the current remainder in the remainder flag list.
            // While a decimal expansion can easily contain multiple instances of a certain digit, each possible remainder can occur only once.
            // This means that if the process encounters a given remainder for a second time, it's begun to repeat itself; ergo, the process is finished.
            $remainder_flag_list[$step_remainder] = true;
            // This is where you add a zero to the number you're dividing and then see how many times the divisor goes into it.
            // The number of times is called "step_digit" because, of course, this is the digit that results from this step of the process.
            // The step_digits are concatenated at each step, so that the final string is the decimal expansion.
            $step_digit = floor($step_remainder * $this->base / $this->reduced_denom);
            // Check for the end of the non-repeating portion of the decimal.
            if ($decimal_length == $non_repeating_tally) {
                $section_ndx++;
                $start_repeat = $step_remainder;  // Store this digit; it'll be used to determine when/if the complement begins.
            }
            // Append the current digit to the decimal expansion.  Perform base conversion if not in base 10.
            $section_list[$section_ndx] .= ($this->base != 10 ? base_convert($step_digit, 10, $this->base) : $step_digit);
            // This is where you find the remainder in the current step of the division.
            // Example:  for 1/4, the first step would entail multiplying the 1 by 10 and determining how many times 4 divides the result.  Since 4 goes into 10 twice,
            //           the "step_digit" value is 2.  Since 10 - 8 is 2, the "step_remainder" value is 2.
            $step_remainder = $step_remainder * $this->base - $step_digit * $this->reduced_denom;
            // Here's where we detect the repeating portion's complement.  
            // If in the course of calculating the decimal expansion one encounters two remainders whose sum is the denominator, 
            // then repeating portion can be split into two halves, and the sum of the two halves will be one less than an integer power of the number base.
            // For instance, in base 10, 1/7 = .142857...  The first remainder is 1 (the numerator), and the third remainder is 6.  The two halves, 142 and 857,
            // add up to 999, which is 10^3 - 1. 
            if ($step_remainder + $start_repeat == $this->reduced_denom) {
                $section_ndx++;
            }
            $decimal_length++;
            // This just checks to see if the decimal expansion has more digits than we want to display on a single line.  If so, an HTML line break is included.
            // ...and we're not going to do this here.  The br, if needed, should be inserted by whatever outputs the thing.
            /*
            if (is_int($decimal_length / $linelength)) {
                $section_list[$section_ndx] .= '<br />';
            }
            */
        }
        // ----- END LONG DIVISION -----

        // If the fraction evaluates to a repeating decimal, calculate the number of digits that repeat; otherwise, set it to 'None'.
        $repeating = $repeating_decimal_flag ? $decimal_length - $non_repeating_tally : 'None';

        // Decorate the sections (optional)
//        $section_list[0] = '<span class="non_repeating">' . $section_list[0] . '</span>';
//        $section_list[1] = '<span class="initial_repeat">' . $section_list[1] . '</span>';
//        $section_list[2] = '<span class="complement_repeat">' . $section_list[2] . '</span>';

        // Set properties determined by this method.
        $this->decimal_length = $decimal_length;
        $this->repeating = $repeating;
        $this->section_list = $section_list;
        $this->decimal = '.' . implode($section_list);
    }


    private function count_non_repeating() {
        $base_factor_tally = 0;
        $base_tmp = $this->base;
        $denom_tmp = $this->reduced_denom;
        $max_non_repeat_tally = 0;
        $non_repeat_tally = 0;
        $prime_ndx = 1;
        $retval = 0;

        // Loop through the prime number list, starting with 2 and continuing through the largest prime factor of the number base.
        while ($this->primes[$prime_ndx] <= $base_tmp) {
            // $non_repeat_tally must be initialized to 0 for each prime number in the cycle, so that the maximum tally can be determined.
            $non_repeat_tally = 0;
            $base_factor_tally = 0;
            // First, tally the occurrences of the present prime number in the base's set of factors.
            while (is_int($base_tmp / $this->primes[$prime_ndx])) {
                $base_tmp /= $this->primes[$prime_ndx];
                $base_factor_tally++;
            }      
            // If the present prime is indeed a factor of the base, process this block.
            if ($base_factor_tally > 0) {
                // This block will determine the number of non-repeating decimal places generated for the current prime number.  The maximum value from this will be returned.
                $prime_power = pow($this->primes[$prime_ndx], $base_factor_tally);
                // First, divide out all complete sets of the present prime number from the denominator, and tally the number of divisions.
                while (is_int($denom_tmp / $prime_power)) {
                    $denom_tmp /= $prime_power;
                    $non_repeat_tally++;
                }
                // Second, check for any remaining instances of the prime number.  If there are any, increment the tally, and divide out all that remain.
                if (is_int($denom_tmp / $this->primes[$prime_ndx])) {
                    $non_repeat_tally++;
                    while (is_int($denom_tmp / $this->primes[$prime_ndx])) {
                        $denom_tmp /= $this->primes[$prime_ndx];
                    }
                }
                // Keep the $max_non_repeat_tally up-to-date.
                $max_non_repeat_tally = max($non_repeat_tally, $max_non_repeat_tally);
            }
            $prime_ndx++;
        }
        // If $denom_tmp is equal to 1 at this point, the denominator's prime factors are all included in the set of factors for the base, which means the decimal resolves.
        // If the denominator has no factors in common with the base, then there are no non-repeating digits.
        $retval = $denom_tmp == 1 ? -1 : $max_non_repeat_tally;
        return $retval;
    }


    private function get_gcf($int1, $int2) {
        $ints = array($int1, $int2);

        $finished = false;
        while (!$finished) {
            $ints = array(max($ints), min($ints));
            if (is_int($ints[0] / $ints[1])) {
                $finished = true;
            } else {
                $ints[0] = $ints[0] - $ints[1];
            }
        }
        return $ints[1];
    }


}
?>