originally contributed by sjoerd mullender significantly modified by jeffrey yasskin jyasskin at gmail com fraction infiniteprecision rational numbers from decimal import decimal import functools import math import numbers import operator import re import sys all fraction constants related to the hash implementation hashx is based on the reduction of x modulo the prime pyhashmodulus pyhashmodulus sys hashinfo modulus value to be used for rationals that reduce to infinity modulo pyhashmodulus pyhashinf sys hashinfo inf functools lrucachemaxsize 1 14 def hashalgorithmnumerator denominator to make sure that the hash of a fraction agrees with the hash of a numerically equal integer float or decimal instance we follow the rules for numeric hashes outlined in the documentation see library docs builtin types try dinv powdenominator 1 pyhashmodulus except valueerror valueerror means there is no modular inverse hash pyhashinf else the general algorithm now specifies that the absolute value of the hash is n dinv p where n is self numerator and p is pyhashmodulus that s optimized here in two ways first for a nonnegative int i hashi i p but the int hash implementation doesn t need to divide and is faster than doing p explicitly so we do hashn dinv instead second n is unbounded so its product with dinv may be arbitrarily expensive to compute the final answer is the same if we use the bounded n p instead which can again be done with an int hash call if 0 i p hashi i so this nested hash call wastes a bit of time making a redundant copy when n p but can save an arbitrarily large amount of computation for large n hash hashhashabsnumerator dinv result hash if numerator 0 else hash return 2 if result 1 else result rationalformat re compiler as optional whitespace at the start psign an optional sign then d d lookahead for digit or digit pnumddd numerator possibly empty followed by ss pdenomdd an optional denominator or pdecimalddd an optional fractional part e pexp dd and optional exponent sz and optional whitespace to finish helpers for formatting round a rational number to the nearest multiple of a given power of 10 rounds the rational number nd to the nearest integer multiple of 10exponent rounding to the nearest even integer multiple in the case of a tie returns a pair sign bool significand int representing the rounded value 1sign significand 10exponent if nonegzero is true then the returned sign will always be false when the significand is zero otherwise the sign reflects the sign of the input d must be positive but n and d need not be relatively prime the divmod quotient is correct for roundtiestowardspositiveinfinity in the case of a tie we zero out the least significant bit of q round a rational number to a given number of significant figures rounds the rational number nd to the given number of significant figures using the roundtiestoeven rule and returns a triple sign bool significand int exponent int representing the rounded value 1sign significand 10exponent in the special case where n 0 returns a significand of zero and an exponent of 1 figures for compatibility with formatting otherwise the returned significand satisfies 10figures 1 significand 10figures d must be positive but n and d need not be relatively prime figures must be positive special case for n 0 find integer m satisfying 10m 1 absnd 10m if absnd is a power of 10 either of the two possible values for m is fine round to a multiple of 10m figures the significand we get satisfies 10figures 1 significand 10figures adjust in the case where significand 10figures to ensure that 10figures 1 significand 10figures pattern for matching floatstyle format specifications supports e e f f g g and presentation types a 0 that s not followed by another digit is parsed as a minimum width rather than a zeropad flag re dotall re verbose fullmatch class fractionnumbers rational slots numerator denominator we re immutable so use new not init def newcls numerator0 denominatornone self superfraction cls newcls if denominator is none if typenumerator is int self numerator numerator self denominator 1 return self elif isinstancenumerator numbers rational self numerator numerator numerator self denominator numerator denominator return self elif isinstancenumerator float decimal exact conversion self numerator self denominator numerator asintegerratio return self elif isinstancenumerator str handle construction from strings m rationalformat matchnumerator if m is none raise valueerror invalid literal for fraction r numerator numerator intm group num or 0 denom m group denom if denom denominator intdenom else denominator 1 decimal m group decimal if decimal decimal decimal replace scale 10lendecimal numerator numerator scale intdecimal denominator scale exp m group exp if exp exp intexp if exp 0 numerator 10exp else denominator 10exp if m group sign numerator numerator else raise typeerrorargument should be a string or a rational instance elif typenumerator is int is typedenominator pass very normal case elif isinstancenumerator numbers rational and isinstancedenominator numbers rational numerator denominator numerator numerator denominator denominator denominator numerator numerator denominator else raise typeerrorboth arguments should be rational instances if denominator 0 raise zerodivisionerror fractions 0 numerator g math gcdnumerator denominator if denominator 0 g g numerator g denominator g self numerator numerator self denominator denominator return self classmethod def fromfloatcls f if isinstancef numbers integral return clsf elif not isinstancef float raise typeerrors fromfloat only takes floats not r s cls name f typef name return cls fromcoprimeintsf asintegerratio classmethod def fromdecimalcls dec convert a pair of ints to a rational number for internal use the ratio of integers should be in lowest terms and the denominator should be positive return true if the fraction is an integer return self denominator 1 def asintegerratioself return self numerator self denominator def limitdenominatorself maxdenominator1000000 algorithm notes for any real number x define a best upper approximation to x to be a rational number pq such that 1 pq x and 2 if pq rs x then s q for any rational rs define best lower approximation similarly then it can be proved that a rational number is a best upper or lower approximation to x if and only if it is a convergent or semiconvergent of the unique shortest continued fraction associated to x to find a best rational approximation with denominator m we find the best upper and lower approximations with denominator m and take whichever of these is closer to x in the event of a tie the bound with smaller denominator is chosen if both denominators are equal which can happen only when maxdenominator 1 and self is midway between two integers the lower boundi e the floor of self is taken if maxdenominator 1 raise valueerrormaxdenominator should be at least 1 if self denominator maxdenominator return fractionself p0 q0 p1 q1 0 1 1 0 n d self numerator self denominator while true a nd q2 q0aq1 if q2 maxdenominator break p0 q0 p1 q1 p1 q1 p0ap1 q2 n d d nad k maxdenominatorq0q1 determine which of the candidates p0kp1q0kq1 and p1q1 is closer to self the distance between them is 1q1q0kq1 while the distance from p1q1 to self is dq1self denominator so we need to compare 2q0kq1 with self denominatord if 2dq0kq1 self denominator return fraction fromcoprimeintsp1 q1 else return fraction fromcoprimeintsp0kp1 q0kq1 property def numeratora return a numerator property def denominatora return a denominator def reprself strself if self denominator 1 return strself numerator else return ss self numerator self denominator def formatself formatspec backwards compatiblility with existing formatting validate and parse the format specifier avoid the temptation to guess round to get the digits we need figure out where to place the point and decide whether to use scientific notation pointpos is the relative to the end of the digit string that is it s the number of digits that should follow the point get the suffix the part following the digits if any string of output digits padded sufficiently with zeros on the left so that we ll have at least one digit before the decimal point before padding the output has the form fsignleadingtrailing where leading includes thousands separators if necessary and trailing includes the decimal separator where appropriate do zero padding if required when adding thousands separators they ll be added to the zeropadded portion too so we need to compensate insert thousands separators if required we now have a sign and a body pad with fill character if necessary and return generates forward and reverse operators given a purelyrational operator and a function from the operator module use this like op rop operatorfallbacksjustrationalop operator op in general we want to implement the arithmetic operations so that mixedmode operations either call an implementation whose knew about the types of both arguments or convert both to the nearest built in type and do the operation there in fraction that means that we define add and radd as def addself other both types have numeratorsdenominator attributes so do the operation directly if isinstanceother int fraction return fractionself numerator other denominator other numerator self denominator self denominator other denominator float and complex don t have those operations but we know about those types so special case them elif isinstanceother float return floatself other elif isinstanceother complex return complexself other let the other type take over return notimplemented def raddself other radd handles more types than add because there s nothing left to fall back to if isinstanceother numbers rational return fractionself numerator other denominator other numerator self denominator self denominator other denominator elif isinstanceother real return floatother floatself elif isinstanceother complex return complexother complexself return notimplemented there are 5 different cases for a mixedtype addition on fraction i ll refer to all of the above code that doesn t refer to fraction float or complex as boilerplate r will be an instance of fraction which is a subtype of rational r fraction rational and b b complex the first three involve r b 1 if b fraction int float or complex we handle that specially and all is well 2 if fraction falls back to the boilerplate code and it were to return a value from add we d miss the possibility that b defines a more intelligent radd so the boilerplate should return notimplemented from add in particular we don t handle rational here even though we could get an exact answer in case the other type wants to do something special 3 if b fraction python tries b radd before fraction add this is ok because it was implemented with knowledge of fraction so it can handle those instances before delegating to real or complex the next two situations describe b r we assume that b didn t know about fraction in its implementation and that it uses similar boilerplate code 4 if b rational then radd converts both to the builtin rational type hey look that s us and proceeds 5 otherwise radd tries to find the nearest common base abc and fall back to its builtin type since this class doesn t subclass a concrete type there s no implementation to fall back to so we need to try as hard as possible to return an actual value or the user will get a typeerror includes ints rational arithmetic algorithms knuth taocp volume 2 4 5 1 assume input fractions a and b are normalized 1 consider additionsubtraction let g gcdda db then na nb nadb nbda a b da db dadb nadbg nbdag t dadbg d now if g 1 we re working with smaller integers note that t dag and dbg are pairwise coprime indeed dag and dbg share no common factors they were removed and da is coprime with na since input fractions are normalized hence dag and na are coprime by symmetry dbg and nb are coprime too then gcdt dag gcdnadbg dag 1 gcdt dbg gcdnbdag dbg 1 above allows us optimize reduction of the result to lowest terms indeed g2 gcdt d gcdt dagdbgg gcdt g tg2 tg2 a b dagdbggg2 dagdbg2 is a normalized fraction this is useful because the unnormalized denominator d could be much larger than g we should specialcase g 1 and g2 1 since 60 8 of randomlychosen integers are coprime https en wikipedia orgwikicoprimeintegersprobabilityofcoprimality note that g2 1 always for fractions obtained from floats here g is a power of 2 and the unnormalized numerator t is an odd integer 2 consider multiplication let g1 gcdna db and g2 gcdnb da then nanb nanb nag1nbg2 ab dadb dbda dbg1dag2 note that after divisions we re multiplying smaller integers also the resulting fraction is normalized because each of two factors in the numerator is coprime to each of the two factors in the denominator indeed pick nag1 it s coprime with dag2 because input fractions are normalized it s also coprime with dbg1 because common factors are removed by g1 gcdna db as for additionsubtraction we should specialcase g1 1 and g2 1 for same reason that happens also for multiplying rationals obtained from floats a b na da a numerator a denominator nb db b numerator b denominator g math gcdda db if g 1 return fraction fromcoprimeintsna db da nb da db s da g t na db g nb s g2 math gcdt g if g2 1 return fraction fromcoprimeintst s db return fraction fromcoprimeintst g2 s db g2 add radd operatorfallbacksadd operator add def suba b a b na da a numerator a denominator nb db b numerator b denominator g1 math gcdna db if g1 1 na g1 db g1 g2 math gcdnb da if g2 1 nb g2 da g2 return fraction fromcoprimeintsna nb db da mul rmul operatorfallbacksmul operator mul def diva b same as mul with inversed b a b return a numerator b denominator a denominator b numerator floordiv rfloordiv operatorfallbacksfloordiv operator floordiv def divmoda b a b da db a denominator b denominator return fractiona numerator db b numerator da da db mod rmod operatorfallbacksmod operator mod def powa b if isinstanceb numbers rational if b denominator 1 power b numerator if power 0 return fraction fromcoprimeintsa numerator power a denominator power elif a numerator 0 return fraction fromcoprimeintsa denominator power a numerator power elif a numerator 0 raise zerodivisionerror fractions 0 a denominator power else return fraction fromcoprimeintsa denominator power a numerator power else a fractional power will generally produce an irrational number return floata floatb else return floata b def rpowb a if a is an int keep it that way if possible a coerces a subclass instance to fraction return fraction fromcoprimeintsa numerator a denominator def nega absa return fraction fromcoprimeintsabsa numerator a denominator def inta indexoperator index math trunca if a numerator 0 return a numerator a denominator else return a numerator a denominator def floora math ceila the negations cleverly convince floordiv to return the ceiling return a numerator a denominator def roundself ndigitsnone if ndigits is none d self denominator floor remainder divmodself numerator d if remainder 2 d return floor elif remainder 2 d return floor 1 deal with the half case elif floor 2 0 return floor else return floor 1 shift 10absndigits see operatorfallbacks forward to check that the results of these operations will always be fraction and therefore have round if ndigits 0 return fractionroundself shift shift else return fractionroundself shift shift def hashself a b if typeb is int return a numerator b and a denominator 1 if isinstanceb numbers rational return a numerator b numerator and a denominator b denominator if isinstanceb numbers complex and b imag 0 b b real if isinstanceb float if math isnanb or math isinfb comparisons with an infinity or nan should behave in the same way for any finite a so treat a as zero return 0 0 b else return a a fromfloatb else since a doesn t know how to compare with b let s give b a chance to compare itself with a return notimplemented def richcmpself other op convert other to a rational instance where reasonable if isinstanceother numbers rational return opself numerator other denominator self denominator other numerator if isinstanceother float if math isnanother or math isinfother return op0 0 other else return opself self fromfloatother else return notimplemented def lta b a b return a richcmpb operator gt def lea b a b return a richcmpb operator ge def boola bpo39274 use bool because a numerator 0 can return an object which is not a bool support for pickling copy and deepcopy originally contributed by sjoerd mullender significantly modified by jeffrey yasskin jyasskin at gmail com fraction infinite precision rational numbers constants related to the hash implementation hash x is based on the reduction of x modulo the prime _pyhash_modulus value to be used for rationals that reduce to infinity modulo _pyhash_modulus to make sure that the hash of a fraction agrees with the hash of a numerically equal integer float or decimal instance we follow the rules for numeric hashes outlined in the documentation see library docs built in types valueerror means there is no modular inverse the general algorithm now specifies that the absolute value of the hash is n dinv p where n is self _numerator and p is _pyhash_modulus that s optimized here in two ways first for a non negative int i hash i i p but the int hash implementation doesn t need to divide and is faster than doing p explicitly so we do hash n dinv instead second n is unbounded so its product with dinv may be arbitrarily expensive to compute the final answer is the same if we use the bounded n p instead which can again be done with an int hash call if 0 i p hash i i so this nested hash call wastes a bit of time making a redundant copy when n p but can save an arbitrarily large amount of computation for large n a s optional whitespace at the start p sign an optional sign then d d lookahead for digit or digit p num d d _ d numerator possibly empty followed by s s p denom d _ d an optional denominator or p decimal d d _ d an optional fractional part e p exp d _ d and optional exponent s z and optional whitespace to finish helpers for formatting round a rational number to the nearest multiple of a given power of 10 rounds the rational number n d to the nearest integer multiple of 10 exponent rounding to the nearest even integer multiple in the case of a tie returns a pair sign bool significand int representing the rounded value 1 sign significand 10 exponent if no_neg_zero is true then the returned sign will always be false when the significand is zero otherwise the sign reflects the sign of the input d must be positive but n and d need not be relatively prime the divmod quotient is correct for round ties towards positive infinity in the case of a tie we zero out the least significant bit of q round a rational number to a given number of significant figures rounds the rational number n d to the given number of significant figures using the round ties to even rule and returns a triple sign bool significand int exponent int representing the rounded value 1 sign significand 10 exponent in the special case where n 0 returns a significand of zero and an exponent of 1 figures for compatibility with formatting otherwise the returned significand satisfies 10 figures 1 significand 10 figures d must be positive but n and d need not be relatively prime figures must be positive special case for n 0 find integer m satisfying 10 m 1 abs n d 10 m if abs n d is a power of 10 either of the two possible values for m is fine round to a multiple of 10 m figures the significand we get satisfies 10 figures 1 significand 10 figures adjust in the case where significand 10 figures to ensure that 10 figures 1 significand 10 figures pattern for matching float style format specifications supports e e f f g g and presentation types p fill p align p sign p no_neg_zero z p alt a 0 that s not followed by another digit is parsed as a minimum width rather than a zeropad flag p zeropad 0 0 9 p minimumwidth 0 1 9 0 9 p thousands_sep _ p precision 0 1 9 0 9 p presentation_type eeffgg this class implements rational numbers in the two argument form of the constructor fraction 8 6 will produce a rational number equivalent to 4 3 both arguments must be rational the numerator defaults to 0 and the denominator defaults to 1 so that fraction 3 3 and fraction 0 fractions can also be constructed from numeric strings similar to those accepted by the float constructor for example 2 3 or 1e10 strings of the form 123 456 float and decimal instances other rational instances including integers we re immutable so use __new__ not __init__ constructs a rational takes a string like 3 2 or 1 5 another rational instance a numerator denominator pair or a float examples fraction 10 8 fraction 5 4 fraction fraction 1 7 5 fraction 1 35 fraction fraction 1 7 fraction 2 3 fraction 3 14 fraction 314 fraction 314 1 fraction 35 4 fraction 35 4 fraction 3 1415 conversion from numeric string fraction 6283 2000 fraction 47e 2 string may include a decimal exponent fraction 47 100 fraction 1 47 direct construction from float exact conversion fraction 6620291452234629 4503599627370496 fraction 2 25 fraction 9 4 fraction decimal 1 47 fraction 147 100 exact conversion handle construction from strings very normal case converts a finite float to a rational number exactly beware that fraction from_float 0 3 fraction 3 10 converts a finite decimal instance to a rational number exactly convert a pair of ints to a rational number for internal use the ratio of integers should be in lowest terms and the denominator should be positive return true if the fraction is an integer return a pair of integers whose ratio is equal to the original fraction the ratio is in lowest terms and has a positive denominator closest fraction to self with denominator at most max_denominator fraction 3 141592653589793 limit_denominator 10 fraction 22 7 fraction 3 141592653589793 limit_denominator 100 fraction 311 99 fraction 4321 8765 limit_denominator 10000 fraction 4321 8765 algorithm notes for any real number x define a best upper approximation to x to be a rational number p q such that 1 p q x and 2 if p q r s x then s q for any rational r s define best lower approximation similarly then it can be proved that a rational number is a best upper or lower approximation to x if and only if it is a convergent or semiconvergent of the unique shortest continued fraction associated to x to find a best rational approximation with denominator m we find the best upper and lower approximations with denominator m and take whichever of these is closer to x in the event of a tie the bound with smaller denominator is chosen if both denominators are equal which can happen only when max_denominator 1 and self is midway between two integers the lower bound i e the floor of self is taken determine which of the candidates p0 k p1 q0 k q1 and p1 q1 is closer to self the distance between them is 1 q1 q0 k q1 while the distance from p1 q1 to self is d q1 self _denominator so we need to compare 2 q0 k q1 with self _denominator d repr self str self format this fraction according to the given format specification backwards compatiblility with existing formatting validate and parse the format specifier avoid the temptation to guess round to get the digits we need figure out where to place the point and decide whether to use scientific notation point_pos is the relative to the _end_ of the digit string that is it s the number of digits that should follow the point presentation_type in eegg get the suffix the part following the digits if any string of output digits padded sufficiently with zeros on the left so that we ll have at least one digit before the decimal point before padding the output has the form f sign leading trailing where leading includes thousands separators if necessary and trailing includes the decimal separator where appropriate do zero padding if required when adding thousands separators they ll be added to the zero padded portion too so we need to compensate insert thousands separators if required we now have a sign and a body pad with fill character if necessary and return align generates forward and reverse operators given a purely rational operator and a function from the operator module use this like __op__ __rop__ _operator_fallbacks just_rational_op operator op in general we want to implement the arithmetic operations so that mixed mode operations either call an implementation whose knew about the types of both arguments or convert both to the nearest built in type and do the operation there in fraction that means that we define __add__ and __radd__ as def __add__ self other both types have numerators denominator attributes so do the operation directly if isinstance other int fraction return fraction self numerator other denominator other numerator self denominator self denominator other denominator float and complex don t have those operations but we know about those types so special case them elif isinstance other float return float self other elif isinstance other complex return complex self other let the other type take over return notimplemented def __radd__ self other radd handles more types than add because there s nothing left to fall back to if isinstance other numbers rational return fraction self numerator other denominator other numerator self denominator self denominator other denominator elif isinstance other real return float other float self elif isinstance other complex return complex other complex self return notimplemented there are 5 different cases for a mixed type addition on fraction i ll refer to all of the above code that doesn t refer to fraction float or complex as boilerplate r will be an instance of fraction which is a subtype of rational r fraction rational and b b complex the first three involve r b 1 if b fraction int float or complex we handle that specially and all is well 2 if fraction falls back to the boilerplate code and it were to return a value from __add__ we d miss the possibility that b defines a more intelligent __radd__ so the boilerplate should return notimplemented from __add__ in particular we don t handle rational here even though we could get an exact answer in case the other type wants to do something special 3 if b fraction python tries b __radd__ before fraction __add__ this is ok because it was implemented with knowledge of fraction so it can handle those instances before delegating to real or complex the next two situations describe b r we assume that b didn t know about fraction in its implementation and that it uses similar boilerplate code 4 if b rational then __radd_ converts both to the builtin rational type hey look that s us and proceeds 5 otherwise __radd__ tries to find the nearest common base abc and fall back to its builtin type since this class doesn t subclass a concrete type there s no implementation to fall back to so we need to try as hard as possible to return an actual value or the user will get a typeerror includes ints rational arithmetic algorithms knuth taocp volume 2 4 5 1 assume input fractions a and b are normalized 1 consider addition subtraction let g gcd da db then na nb na db nb da a b da db da db na db g nb da g t da db g d now if g 1 we re working with smaller integers note that t da g and db g are pairwise coprime indeed da g and db g share no common factors they were removed and da is coprime with na since input fractions are normalized hence da g and na are coprime by symmetry db g and nb are coprime too then gcd t da g gcd na db g da g 1 gcd t db g gcd nb da g db g 1 above allows us optimize reduction of the result to lowest terms indeed g2 gcd t d gcd t da g db g g gcd t g t g2 t g2 a b da g db g g g2 da g db g2 is a normalized fraction this is useful because the unnormalized denominator d could be much larger than g we should special case g 1 and g2 1 since 60 8 of randomly chosen integers are coprime https en wikipedia org wiki coprime_integers probability_of_coprimality note that g2 1 always for fractions obtained from floats here g is a power of 2 and the unnormalized numerator t is an odd integer 2 consider multiplication let g1 gcd na db and g2 gcd nb da then na nb na nb na g1 nb g2 a b da db db da db g1 da g2 note that after divisions we re multiplying smaller integers also the resulting fraction is normalized because each of two factors in the numerator is coprime to each of the two factors in the denominator indeed pick na g1 it s coprime with da g2 because input fractions are normalized it s also coprime with db g1 because common factors are removed by g1 gcd na db as for addition subtraction we should special case g1 1 and g2 1 for same reason that happens also for multiplying rationals obtained from floats a b a b a b a b same as _mul with inversed b a b a b a b a b a b if b is not an integer the result will be a float or complex since roots are generally irrational if b is an integer the result will be rational a fractional power will generally produce an irrational number a b if a is an int keep it that way if possible a coerces a subclass instance to fraction a abs a int a math trunc a math floor a math ceil a the negations cleverly convince floordiv to return the ceiling round self ndigits rounds half toward even deal with the half case see _operator_fallbacks forward to check that the results of these operations will always be fraction and therefore have round hash self a b comparisons with an infinity or nan should behave in the same way for any finite a so treat a as zero since a doesn t know how to compare with b let s give b a chance to compare itself with a helper for comparison operators for internal use only implement comparison between a rational instance self and either another rational instance or a float other if other is not a rational instance or a float return notimplemented op should be one of the six standard comparison operators convert other to a rational instance where reasonable a b a b a b a b a 0 bpo 39274 use bool because a _numerator 0 can return an object which is not a bool support for pickling copy and deepcopy i m immutable therefore i am my own clone my components are also immutable
from decimal import Decimal
import functools
import math
import numbers
import operator
import re
import sys

__all__ = ['Fraction']




_PyHASH_MODULUS = sys.hash_info.modulus


_PyHASH_INF = sys.hash_info.inf

@functools.lru_cache(maxsize = 1 << 14)
def _hash_algorithm(numerator, denominator):

    
    
    
    

    try:
        dinv = pow(denominator, -1, _PyHASH_MODULUS)
    except ValueError:
        
        hash_ = _PyHASH_INF
    else:
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        hash_ = hash(hash(abs(numerator)) * dinv)
    result = hash_ if numerator >= 0 else -hash_
    return -2 if result == -1 else result

_RATIONAL_FORMAT = re.compile(r, re.VERBOSE | re.IGNORECASE)




def _round_to_exponent(n, d, exponent, no_neg_zero=False):
    
    if exponent >= 0:
        d *= 10**exponent
    else:
        n *= 10**-exponent

    
    
    q, r = divmod(n + (d >> 1), d)
    if r == 0 and d & 1 == 0:
        q &= -2

    sign = q < 0 if no_neg_zero else n < 0
    return sign, abs(q)


def _round_to_figures(n, d, figures):
    
    
    if n == 0:
        return False, 0, 1 - figures

    
    
    str_n, str_d = str(abs(n)), str(d)
    m = len(str_n) - len(str_d) + (str_d <= str_n)

    
    
    exponent = m - figures
    sign, significand = _round_to_exponent(n, d, exponent)

    
    
    if len(str(significand)) == figures + 1:
        significand //= 10
        exponent += 1

    return sign, significand, exponent




_FLOAT_FORMAT_SPECIFICATION_MATCHER = re.compile(r, re.DOTALL | re.VERBOSE).fullmatch


class Fraction(numbers.Rational):
    

    __slots__ = ('_numerator', '_denominator')

    
    def __new__(cls, numerator=0, denominator=None):
        
        self = super(Fraction, cls).__new__(cls)

        if denominator is None:
            if type(numerator) is int:
                self._numerator = numerator
                self._denominator = 1
                return self

            elif isinstance(numerator, numbers.Rational):
                self._numerator = numerator.numerator
                self._denominator = numerator.denominator
                return self

            elif isinstance(numerator, (float, Decimal)):
                
                self._numerator, self._denominator = numerator.as_integer_ratio()
                return self

            elif isinstance(numerator, str):
                
                m = _RATIONAL_FORMAT.match(numerator)
                if m is None:
                    raise ValueError('Invalid literal for Fraction: %r' %
                                     numerator)
                numerator = int(m.group('num') or '0')
                denom = m.group('denom')
                if denom:
                    denominator = int(denom)
                else:
                    denominator = 1
                    decimal = m.group('decimal')
                    if decimal:
                        decimal = decimal.replace('_', '')
                        scale = 10**len(decimal)
                        numerator = numerator * scale + int(decimal)
                        denominator *= scale
                    exp = m.group('exp')
                    if exp:
                        exp = int(exp)
                        if exp >= 0:
                            numerator *= 10**exp
                        else:
                            denominator *= 10**-exp
                if m.group('sign') == '-':
                    numerator = -numerator

            else:
                raise TypeError("argument should be a string "
                                "or a Rational instance")

        elif type(numerator) is int is type(denominator):
            pass 

        elif (isinstance(numerator, numbers.Rational) and
            isinstance(denominator, numbers.Rational)):
            numerator, denominator = (
                numerator.numerator * denominator.denominator,
                denominator.numerator * numerator.denominator
                )
        else:
            raise TypeError("both arguments should be "
                            "Rational instances")

        if denominator == 0:
            raise ZeroDivisionError('Fraction(%s, 0)' % numerator)
        g = math.gcd(numerator, denominator)
        if denominator < 0:
            g = -g
        numerator //= g
        denominator //= g
        self._numerator = numerator
        self._denominator = denominator
        return self

    @classmethod
    def from_float(cls, f):
        
        if isinstance(f, numbers.Integral):
            return cls(f)
        elif not isinstance(f, float):
            raise TypeError("%s.from_float() only takes floats, not %r (%s)" %
                            (cls.__name__, f, type(f).__name__))
        return cls._from_coprime_ints(*f.as_integer_ratio())

    @classmethod
    def from_decimal(cls, dec):
        
        from decimal import Decimal
        if isinstance(dec, numbers.Integral):
            dec = Decimal(int(dec))
        elif not isinstance(dec, Decimal):
            raise TypeError(
                "%s.from_decimal() only takes Decimals, not %r (%s)" %
                (cls.__name__, dec, type(dec).__name__))
        return cls._from_coprime_ints(*dec.as_integer_ratio())

    @classmethod
    def _from_coprime_ints(cls, numerator, denominator, /):
        
        obj = super(Fraction, cls).__new__(cls)
        obj._numerator = numerator
        obj._denominator = denominator
        return obj

    def is_integer(self):
        
        return self._denominator == 1

    def as_integer_ratio(self):
        
        return (self._numerator, self._denominator)

    def limit_denominator(self, max_denominator=1000000):

        if max_denominator < 1:
            raise ValueError("max_denominator should be at least 1")
        if self._denominator <= max_denominator:
            return Fraction(self)

        p0, q0, p1, q1 = 0, 1, 1, 0
        n, d = self._numerator, self._denominator
        while True:
            a = n//d
            q2 = q0+a*q1
            if q2 > max_denominator:
                break
            p0, q0, p1, q1 = p1, q1, p0+a*p1, q2
            n, d = d, n-a*d
        k = (max_denominator-q0)//q1
        
        if 2*d*(q0+k*q1) <= self._denominator:
            return Fraction._from_coprime_ints(p1, q1)
        else:
            return Fraction._from_coprime_ints(p0+k*p1, q0+k*q1)

    @property
    def numerator(a):
        return a._numerator

    @property
    def denominator(a):
        return a._denominator

    def __repr__(self):
        
        return '%s(%s, %s)' % (self.__class__.__name__,
                               self._numerator, self._denominator)

    def __str__(self):
        
        if self._denominator == 1:
            return str(self._numerator)
        else:
            return '%s/%s' % (self._numerator, self._denominator)

    def __format__(self, format_spec, /):
        

        
        if not format_spec:
            return str(self)

        
        match = _FLOAT_FORMAT_SPECIFICATION_MATCHER(format_spec)
        if match is None:
            raise ValueError(
                f"Invalid format specifier {format_spec!r} "
                f"for object of type {type(self).__name__!r}"
            )
        elif match["align"] is not None and match["zeropad"] is not None:
            
            raise ValueError(
                f"Invalid format specifier {format_spec!r} "
                f"for object of type {type(self).__name__!r}; "
                "can't use explicit alignment when zero-padding"
            )
        fill = match["fill"] or " "
        align = match["align"] or ">"
        pos_sign = "" if match["sign"] == "-" else match["sign"]
        no_neg_zero = bool(match["no_neg_zero"])
        alternate_form = bool(match["alt"])
        zeropad = bool(match["zeropad"])
        minimumwidth = int(match["minimumwidth"] or "0")
        thousands_sep = match["thousands_sep"]
        precision = int(match["precision"] or "6")
        presentation_type = match["presentation_type"]
        trim_zeros = presentation_type in "gG" and not alternate_form
        trim_point = not alternate_form
        exponent_indicator = "E" if presentation_type in "EFG" else "e"

        if presentation_type in "fF%":
            exponent = -precision
            if presentation_type == "%":
                exponent -= 2
            negative, significand = _round_to_exponent(
                self._numerator, self._denominator, exponent, no_neg_zero)
            scientific = False
            point_pos = precision
        else:  
            figures = (
                max(precision, 1)
                if presentation_type in "gG"
                else precision + 1
            )
            negative, significand, exponent = _round_to_figures(
                self._numerator, self._denominator, figures)
            scientific = (
                presentation_type in "eE"
                or exponent > 0
                or exponent + figures <= -4
            )
            point_pos = figures - 1 if scientific else -exponent

        
        if presentation_type == "%":
            suffix = "%"
        elif scientific:
            suffix = f"{exponent_indicator}{exponent + point_pos:+03d}"
        else:
            suffix = ""
        
        digits = f"{significand:0{point_pos + 1}d}"

        sign = "-" if negative else pos_sign
        leading = digits[: len(digits) - point_pos]
        frac_part = digits[len(digits) - point_pos :]
        if trim_zeros:
            frac_part = frac_part.rstrip("0")
        separator = "" if trim_point and not frac_part else "."
        trailing = separator + frac_part + suffix

        
        if zeropad:
            min_leading = minimumwidth - len(sign) - len(trailing)
            
            
            leading = leading.zfill(
                3 * min_leading // 4 + 1 if thousands_sep else min_leading
            )

        
        if thousands_sep:
            first_pos = 1 + (len(leading) - 1) % 3
            leading = leading[:first_pos] + "".join(
                thousands_sep + leading[pos : pos + 3]
                for pos in range(first_pos, len(leading), 3)
            )

        
        
        body = leading + trailing
        padding = fill * (minimumwidth - len(sign) - len(body))
        if align == ">":
            return padding + sign + body
        elif align == "<":
            return sign + body + padding
        elif align == "^":
            half = len(padding) // 2
            return padding[:half] + sign + body + padding[half:]
        else:  
            return sign + padding + body

    def _operator_fallbacks(monomorphic_operator, fallback_operator):
        
        def forward(a, b):
            if isinstance(b, Fraction):
                return monomorphic_operator(a, b)
            elif isinstance(b, int):
                return monomorphic_operator(a, Fraction(b))
            elif isinstance(b, float):
                return fallback_operator(float(a), b)
            elif isinstance(b, complex):
                return fallback_operator(complex(a), b)
            else:
                return NotImplemented
        forward.__name__ = '__' + fallback_operator.__name__ + '__'
        forward.__doc__ = monomorphic_operator.__doc__

        def reverse(b, a):
            if isinstance(a, numbers.Rational):
                
                return monomorphic_operator(Fraction(a), b)
            elif isinstance(a, numbers.Real):
                return fallback_operator(float(a), float(b))
            elif isinstance(a, numbers.Complex):
                return fallback_operator(complex(a), complex(b))
            else:
                return NotImplemented
        reverse.__name__ = '__r' + fallback_operator.__name__ + '__'
        reverse.__doc__ = monomorphic_operator.__doc__

        return forward, reverse

    def _add(a, b):
        
        na, da = a._numerator, a._denominator
        nb, db = b._numerator, b._denominator
        g = math.gcd(da, db)
        if g == 1:
            return Fraction._from_coprime_ints(na * db + da * nb, da * db)
        s = da // g
        t = na * (db // g) + nb * s
        g2 = math.gcd(t, g)
        if g2 == 1:
            return Fraction._from_coprime_ints(t, s * db)
        return Fraction._from_coprime_ints(t // g2, s * (db // g2))

    __add__, __radd__ = _operator_fallbacks(_add, operator.add)

    def _sub(a, b):
        
        na, da = a._numerator, a._denominator
        nb, db = b._numerator, b._denominator
        g = math.gcd(da, db)
        if g == 1:
            return Fraction._from_coprime_ints(na * db - da * nb, da * db)
        s = da // g
        t = na * (db // g) - nb * s
        g2 = math.gcd(t, g)
        if g2 == 1:
            return Fraction._from_coprime_ints(t, s * db)
        return Fraction._from_coprime_ints(t // g2, s * (db // g2))

    __sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub)

    def _mul(a, b):
        
        na, da = a._numerator, a._denominator
        nb, db = b._numerator, b._denominator
        g1 = math.gcd(na, db)
        if g1 > 1:
            na //= g1
            db //= g1
        g2 = math.gcd(nb, da)
        if g2 > 1:
            nb //= g2
            da //= g2
        return Fraction._from_coprime_ints(na * nb, db * da)

    __mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul)

    def _div(a, b):
        
        
        nb, db = b._numerator, b._denominator
        if nb == 0:
            raise ZeroDivisionError('Fraction(%s, 0)' % db)
        na, da = a._numerator, a._denominator
        g1 = math.gcd(na, nb)
        if g1 > 1:
            na //= g1
            nb //= g1
        g2 = math.gcd(db, da)
        if g2 > 1:
            da //= g2
            db //= g2
        n, d = na * db, nb * da
        if d < 0:
            n, d = -n, -d
        return Fraction._from_coprime_ints(n, d)

    __truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv)

    def _floordiv(a, b):
        
        return (a.numerator * b.denominator) // (a.denominator * b.numerator)

    __floordiv__, __rfloordiv__ = _operator_fallbacks(_floordiv, operator.floordiv)

    def _divmod(a, b):
        
        da, db = a.denominator, b.denominator
        div, n_mod = divmod(a.numerator * db, da * b.numerator)
        return div, Fraction(n_mod, da * db)

    __divmod__, __rdivmod__ = _operator_fallbacks(_divmod, divmod)

    def _mod(a, b):
        
        da, db = a.denominator, b.denominator
        return Fraction((a.numerator * db) % (b.numerator * da), da * db)

    __mod__, __rmod__ = _operator_fallbacks(_mod, operator.mod)

    def __pow__(a, b):
        
        if isinstance(b, numbers.Rational):
            if b.denominator == 1:
                power = b.numerator
                if power >= 0:
                    return Fraction._from_coprime_ints(a._numerator ** power,
                                                       a._denominator ** power)
                elif a._numerator > 0:
                    return Fraction._from_coprime_ints(a._denominator ** -power,
                                                       a._numerator ** -power)
                elif a._numerator == 0:
                    raise ZeroDivisionError('Fraction(%s, 0)' %
                                            a._denominator ** -power)
                else:
                    return Fraction._from_coprime_ints((-a._denominator) ** -power,
                                                       (-a._numerator) ** -power)
            else:
                
                
                return float(a) ** float(b)
        else:
            return float(a) ** b

    def __rpow__(b, a):
        
        if b._denominator == 1 and b._numerator >= 0:
            
            return a ** b._numerator

        if isinstance(a, numbers.Rational):
            return Fraction(a.numerator, a.denominator) ** b

        if b._denominator == 1:
            return a ** b._numerator

        return a ** float(b)

    def __pos__(a):
        
        return Fraction._from_coprime_ints(a._numerator, a._denominator)

    def __neg__(a):
        
        return Fraction._from_coprime_ints(-a._numerator, a._denominator)

    def __abs__(a):
        
        return Fraction._from_coprime_ints(abs(a._numerator), a._denominator)

    def __int__(a, _index=operator.index):
        
        if a._numerator < 0:
            return _index(-(-a._numerator // a._denominator))
        else:
            return _index(a._numerator // a._denominator)

    def __trunc__(a):
        
        if a._numerator < 0:
            return -(-a._numerator // a._denominator)
        else:
            return a._numerator // a._denominator

    def __floor__(a):
        
        return a._numerator // a._denominator

    def __ceil__(a):
        
        
        return -(-a._numerator // a._denominator)

    def __round__(self, ndigits=None):
        
        if ndigits is None:
            d = self._denominator
            floor, remainder = divmod(self._numerator, d)
            if remainder * 2 < d:
                return floor
            elif remainder * 2 > d:
                return floor + 1
            
            elif floor % 2 == 0:
                return floor
            else:
                return floor + 1
        shift = 10**abs(ndigits)
        
        
        
        if ndigits > 0:
            return Fraction(round(self * shift), shift)
        else:
            return Fraction(round(self / shift) * shift)

    def __hash__(self):
        
        return _hash_algorithm(self._numerator, self._denominator)

    def __eq__(a, b):
        
        if type(b) is int:
            return a._numerator == b and a._denominator == 1
        if isinstance(b, numbers.Rational):
            return (a._numerator == b.numerator and
                    a._denominator == b.denominator)
        if isinstance(b, numbers.Complex) and b.imag == 0:
            b = b.real
        if isinstance(b, float):
            if math.isnan(b) or math.isinf(b):
                
                
                return 0.0 == b
            else:
                return a == a.from_float(b)
        else:
            
            
            return NotImplemented

    def _richcmp(self, other, op):
        
        
        if isinstance(other, numbers.Rational):
            return op(self._numerator * other.denominator,
                      self._denominator * other.numerator)
        if isinstance(other, float):
            if math.isnan(other) or math.isinf(other):
                return op(0.0, other)
            else:
                return op(self, self.from_float(other))
        else:
            return NotImplemented

    def __lt__(a, b):
        
        return a._richcmp(b, operator.lt)

    def __gt__(a, b):
        
        return a._richcmp(b, operator.gt)

    def __le__(a, b):
        
        return a._richcmp(b, operator.le)

    def __ge__(a, b):
        
        return a._richcmp(b, operator.ge)

    def __bool__(a):
        
        
        
        return bool(a._numerator)

    

    def __reduce__(self):
        return (self.__class__, (self._numerator, self._denominator))

    def __copy__(self):
        if type(self) == Fraction:
            return self     
        return self.__class__(self._numerator, self._denominator)

    def __deepcopy__(self, memo):
        if type(self) == Fraction:
            return self     
        return self.__class__(self._numerator, self._denominator)