Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #52938

Re: Fast conversion of numbers to numerator/denominator pairs

Show key headers only | View raw

Steven D'Aprano wrote:

> I have a need to convert arbitrary non-complex numbers into numerator/
> denominator pairs. Numbers could be ints, floats, Fractions or Decimals.
> For example:
> 
> 2 => (2, 1)
> 0.25 => (1, 4)
> Fraction(2, 3) => (2, 3)
> Decimal("0.5") => (1, 2)
> 
> 
> The first three cases are easy and fast:
> 
> # ints and Fractions
> number.numerator, number.denominator
> 
> # floats are a little slower
> number.as_integer_ratio()
> 
> 
> But Decimals are unfortunately slower. MUCH slower, about 40 times slower
> than Fractions in Python 3.3:
> 
> tmp = Fraction.from_decimal(number)
> (tmp.numerator, tmp.denominator)
> 
> 
> This ends up being the bottleneck in my code: once you include the
> scaffolding code to select the right conversion method, processing a
> large list of Decimals is about fifty times slower than large lists of
> floats or fractions.
> 
> Is there a fast way to convert a Decimal into a pair of numbers numerator/
> denominator? It *must* be exact, but it doesn't have to be simplest form.
> For example, Decimal("0.5") => (5, 10) would be okay, although (1, 2)
> would be preferred.
> 
> 
> I've tried this function:
> 
> def convert(d):
>     sign, digits, exp = d.as_tuple()
>     num = int(''.join([str(digit) for digit in digits]))
>     if sign: num = -num
>     return num, 10**-exp
> 
> 
> which is faster, but not fast enough. Any suggestions?

Maybe these micro-optimisations will be sufficient:

_trans = bytes.maketrans(bytes(range(10)), b"0123456789")

def convert(d):
    sign, digits, exp = d.as_tuple()
    num = int(bytes(digits).translate(_trans))

    if sign:
        num = -num
    return num, 10**-exp

You can get the "simplest form" with co-prime numerator and denominator by 
dividing by fractions.gcd(), but that will of course slow down things.

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Fast conversion of numbers to numerator/denominator pairs Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-08-24 03:30 +0000
  Re: Fast conversion of numbers to numerator/denominator pairs Ian Kelly <ian.g.kelly@gmail.com> - 2013-08-24 01:37 -0600
  Re: Fast conversion of numbers to numerator/denominator pairs Ian Kelly <ian.g.kelly@gmail.com> - 2013-08-24 01:50 -0600
  Re: Fast conversion of numbers to numerator/denominator pairs Peter Otten <__peter__@web.de> - 2013-08-24 14:52 +0200
  Re: Fast conversion of numbers to numerator/denominator pairs Tim Delaney <timothy.c.delaney@gmail.com> - 2013-08-25 07:59 +1000
  Re: Fast conversion of numbers to numerator/denominator pairs Tim Delaney <timothy.c.delaney@gmail.com> - 2013-08-25 08:05 +1000

csiph-web