Class for decimal representation of unit fractions.

unit_fraction.py

"""

Created: 15/03/2022
By: Paul Aljabar

Class for decimal representation of unit fractions.

"""

###############################################################################

import sys, argparse

###############################################################################

def usage():
    desc = ('Class for unit fractions. Run as an executable script to test,'
            ' otherwise import from another script.')
    parser = argparse.ArgumentParser(description=desc)
    parser.add_argument('-start', type=int, help='Start value.', default=2)
    parser.add_argument('-end', type=int, help='End value.', default=30)
    args = parser.parse_args()
    return args

###############################################################################

def main():
    args = usage()
    start_val = args.start
    end_val = args.end

    test_UnitFractionDecimal(start=start_val, end=end_val)

    return 0

###############################################################################

def test_UnitFractionDecimal(start=2, end=30):
    print(f'Running from {start} to {end} inclusive.')
    print('')

    print('\nInteger and List representation:')
    for k in range(start,1+end):
        u = UnitFractionDecimal(k)
        print(k)
        print(u)
        print('\n\n')

    print('_' * 80)

    print('\nPretty print unit fraction and (period)')
    for k in range(start,1+end):
        u = UnitFractionDecimal(k)
        period = len(u.recurring_part)
        print(f'n = {k} ({period})')
        u.pretty_print()
        print('\n\n')

    print('_' * 80)

    print('\nFloating point values (1/d) and float value from unit fraction representation.')
    for k in range(start,1+end):
        u = UnitFractionDecimal(k)
        print(1/k, float(u))

###############################################################################

class UnitFractionDecimal(object):
    """

    Any rational number when written as a decimal has a fixed part and a repeating part

    E.g.    7/12 = 0.583333333333333....
                      _
    or     7/12 = 0.583  more compactly

    This class is for UNIT fractions of form 1/d in base 10.


    """

    def __init__(self, d):
        """
        1/d as a decimal.
        """

        assert d > 1
        self.d = d

        # The result of dividing out 2 and 5 completely from d.
        # d = 2^a 5^b d_strip

        # Initialise:
        self.d_strip = d
        index_2 = 0
        index_5 = 0

        while self.d_strip % 2 == 0:
            self.d_strip //= 2
            index_2 += 1

        while self.d_strip % 5 == 0:
            self.d_strip //= 5
            index_5 += 1

        # Get the recurring part of the stripped value.
        recurring_part = self.get_recurring_part_stripped()

        if not recurring_part:
            # Decimal terminates. Recurring part is empty.
            assert self.d_strip == 1
            self.fixed_part = [int(n) for n in str(1/d).replace('0.', '')]
            self.recurring_part = []
            return

        # There is a recurring part

        # Adjust the recurring part of d_strip's representation by dividing by 2^a 5^b.
        # E.g., for 1/30 we strip out 2,5 to get d_strip = 3
        # Initially, we have f=[] r=[3] where f is the fixed part and r is the recurring part.
        # Divide by 2 to get f=[1] r=[6] ( 1/6 = 0.166666...)
        # Divide by 5 to get f=[0] r=[3] ( 1/30 = 0.0333333...)
        self.recurring_part = recurring_part

        # Alongside, build up the fixed part, initialised to empty list.
        self.fixed_part = []

        for _ in range(index_2):
            self.divide_by_2()

        for _ in range(index_5):
            self.divide_by_5()

        return

    def divide_by_2(self):
        # Get proposals for new fixed and recurring parts.
        rec_new = self.div_list_by_2(self.recurring_part)
        fix_new = self.div_list_by_2(self.fixed_part)

        fix_new, rec_new = self.resolve_carry(fix_new, rec_new)
        fix_new, rec_new = self.merge_fixed_rec(fix_new, rec_new)

        self.fixed_part = fix_new
        self.recurring_part = rec_new

        return


    def divide_by_5(self):
        # Get proposals for new fixed and recurring parts.
        rec_new = self.div_list_by_5(self.recurring_part)
        fix_new = self.div_list_by_5(self.fixed_part)


        fix_new, rec_new = self.resolve_carry(fix_new, rec_new)
        fix_new, rec_new = self.merge_fixed_rec(fix_new, rec_new)

        self.fixed_part = fix_new
        self.recurring_part = rec_new

        return

    def resolve_carry(self, fix_new, rec_new):
        """
        Given proposals for new fixed and recurring parts upon division
        by 2 or 5, resolve any carrying and additions at the same place value.
        The processing depends on which of the new fixed and recurring
        parts is an 'extension' of the existing fixed and recurring parts.

        Four different cases:

        Case 1. Fixed and recurring stay at the same length:
            __           __
        0.0834 / 2 = 0.0417
            Fixed: [0 8] -> [0 4]
            Recurring: [3 4] -> [1 7]
        Neither the fixed nor the recurring gets extended, we can just join them up for the result.

        Case 2. Fixed only extends:
            ___
        0.17835 / 5
        Fixed: [1 7] -> [0 3 4] the last element in the new fixed has a smaller place value corresponding to the first
                                in the recurring.
        Recurring: [8 3 5] -> [1 6 7]  (new is same length as old)
        Writing the sum out fully would look like:
        0.034
            167
               167
                  167...
        0.03567167167...
        So the fixed part needs to 'pull in the first element of the recurring part and the recurring part needs to
        'cycle' ([1 6 7] -> [6 7 1]).
                  ___
        i.e. 0.035671

        Case 3: Only recurring part extends:
            ___
        0.28371 / 2  (recurring part has period 3)

            Fixed: [2 8] -> [1 4]
            Recur: [3 7 1] -> [1 8 5 5] (Length is period plus one)

        The period must stay the same
        Written as (kind of vertical) sum, the result is:
            0.14
                1855
                   1855
                      1855...
            0.141856856856...
        So, the leading element of the extended recurring part is appended to the fixed part.
        And, the leading element is 'carried' in and added to the remaining recurring part:
            [1 4] -> [1 4 1]
            [1 8 5 5] -> [8 5 6]

        Case 4: Both the fixed and recurring parts extend.

            ___
        0.28871 / 5
        Period is 3.

        Direct division of fixed and recurring by 5 gives:
            Fixed: [2 8] -> [0 5 6]
            Recur: [8 7 1] -> [1 7 4 2]
        Each list extends by 1.

        Written as (kind of vertical) sum, the result is:
            0.056
                1742
                   1742
                      1742...
            0.057743743743...
        So the leading element of the recurring part is 'carried' in an added to the fixed part:
              [0 5 6]
            + [    1] -> [0 5 7]
        And, the tail of the recurring part becomes the new recurring part after carrying in and adding the head:
              [7 4 2]
            + [    1] -> [7 4 3]
        So we end up with
        fixed: [0 5 7]
        recurring: [7 4 3]
                  ___
        I.e. 0.057743

        """

        assert len(rec_new) > 0

        fix_extended = len(fix_new) > len(self.fixed_part)
        rec_extended = len(rec_new) > len(self.recurring_part)

        if fix_extended:
            assert len(fix_new) == 1 + len(self.fixed_part)
        if rec_extended:
            assert len(rec_new) == 1 + len(self.recurring_part)

        if not (fix_extended or rec_extended):
            return fix_new, rec_new

        if fix_extended and (not rec_extended):
            # Last element of proposed fixed part has same place value as first element of recurring part.

            c = rec_new[0]
            fix_new, c = self.add_carry(fix_new, c)
            assert c == 0

            # If recursive part is longer than one, cycle so it starts at second position.
            if len(rec_new) > 1:
                rec_new = rec_new[1:] + rec_new[:1]

        if rec_extended and (not fix_extended):

            carry, rec_new = rec_new[0], rec_new[1:]

            fix_new = fix_new + [carry]

            c = carry
            rec_new, c = self.add_carry(rec_new, c)
            assert c == 0
            assert len(rec_new) == len(self.recurring_part)

        if fix_extended and rec_extended:
            carry, rec_new = rec_new[0], rec_new[1:]

            c = carry
            fix_new, c = self.add_carry(fix_new, c)
            assert c == 0

            c = carry
            rec_new, c = self.add_carry(rec_new, c)
            assert c == 0
            assert len(rec_new) == len(self.recurring_part)

        return fix_new, rec_new

    def merge_fixed_rec(self, fixed, rec):
        if len(fixed) == 0:
            return fixed, rec

        # Check if the last entry in fixed, when concatenated with the first
        # p-1 entries of the recurring part can form a cycle of the recurring part.
        # E.g. fixed [0 3] recurring [4 7 3] can be re-written as fixed [0] recurring [3 4 7].

        end_f = fixed[-1]
        period = len(self.recurring_part)
        cycles_rec = [rec[k:]+rec[:k] for k in range(period)]

        while [end_f] + rec[:-1] in cycles_rec:
            # Take the last element of the fixed part.
            fixed = fixed[:-1]
            # Make the recurring part start with element taken from the end of the fixed part.
            rec = [end_f] + rec[:-1]

            if not fixed:
                # We've emptied out the fixed part.
                break

            # Update to see if we can continue.
            end_f = fixed[-1]
            cycles_rec = [rec[k:]+rec[:k] for k in range(period)]


        return fixed, rec



    @staticmethod
    def add_carry(digit_list, carry):
        n_digits = len(digit_list)

        if n_digits == 0:
            return [carry], 0

        for k in reversed(range(n_digits)):
            v = digit_list[k] + carry
            digit_list[k] = v % 10
            carry = v // 10
        return digit_list, carry

    @staticmethod
    def div_list_by_2(digit_list):
        """
        Divide by 10 and multiply by 5
        """

        if not digit_list:
            return []

        rem = 0
        output = []
        for d in digit_list:
            v = rem * 10 + d
            output.append(v // 2)
            rem = v % 2
        if rem > 0:
            output.append(5)

        return output


    @staticmethod
    def div_list_by_5(digit_list):
        """
        Divide by 10 and multiply by 2
        """

        if not digit_list:
            return []

        rem = 0
        output = []
        for d in digit_list:
            val = 10* rem + d
            output.append(val // 5)
            rem = val % 5
        if rem > 0:
            output.append(2 * rem)

        return output

    def __str__(self):
        f = '0.' + ''.join(map(str, self.fixed_part))
        r = ''.join(map(str, self.recurring_part))
        s = ' ' * len(f) + '_'*len(r)
        return f'{s}\n{f}{r}'


    def __float__(self):
        len_fix = len(self.fixed_part)
        period = len(self.recurring_part)
        f = self.digit_list_to_integer(self.fixed_part)

        val = f

        if period > 0:
            r = self.digit_list_to_integer(self.recurring_part)
            val = f + r / (10**period - 1)

        val /= 10**len_fix
        return val

    @staticmethod
    def digit_list_to_integer(digit_list):
        val = 0
        for d in digit_list:
            val = 10*val + d
        return val

    def get_recurring_part_stripped(self):

        L = self.len_recurring_stripped()
        A = [(10**k % self.d_strip) for k in range(L)]
        digits_1 = [ 10*a//self.d_strip for a in A]
        return digits_1


    def len_recurring_stripped(self):
        """
        This function assumes that neither 2 nor 5 is a factor of d.
        (for speed)
        """

        assert self.d_strip % 2 > 0
        assert self.d_strip % 5 > 0

        if self.d_strip == 1:
            return 0

        L = 1
        pow_ten = 10
        while pow_ten % self.d_strip > 1:
            L += 1
            pow_ten *= 10

        return L

    def __repr__(self):
        return self.fixed_part.__repr__() + ' ' + self.recurring_part.__repr__()

    def pretty_print(self):
        print(self.__str__())
        return

###############################################################################

if __name__ == '__main__':
    sys.exit(main())