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

Groups > comp.lang.python > #52925 > unrolled thread

Fast conversion of numbers to numerator/denominator pairs

Back to article view | Back to comp.lang.python

Contents

  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

#52925 — Fast conversion of numbers to numerator/denominator pairs

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?


-- 
Steven

[toc] | [next] | [standalone]

#52930

On Fri, Aug 23, 2013 at 9:30 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> 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?

I time this function at about 33% faster than your version for a
six-digit decimal, and almost 50% faster for a 12-digit decimal.  My
guess would be because it's not calling str() on every individual
digit.

def convert(d):
    exp = d.as_tuple().exponent
    num = int(d.scaleb(-exp))
    return num, 10**-exp

[toc] | [prev] | [next] | [standalone]

#52931

On Sat, Aug 24, 2013 at 1:37 AM, Ian Kelly <ian.g.kelly@gmail.com> wrote:
>
> I time this function at about 33% faster than your version for a
> six-digit decimal, and almost 50% faster for a 12-digit decimal.  My
> guess would be because it's not calling str() on every individual
> digit.
>
> def convert(d):
>     exp = d.as_tuple().exponent
>     num = int(d.scaleb(-exp))
>     return num, 10**-exp

Although, you would need to be careful with handling the decimal
context for the scaleb operation to make sure the result is exact.

[toc] | [prev] | [next] | [standalone]

#52938

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.

[toc] | [prev] | [next] | [standalone]

#52952

[Multipart message — attachments visible in raw view] — view raw

On 24 August 2013 13:30, Steven D'Aprano <
steve+comp.lang.python@pearwood.info> wrote:

>
> 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?
>

Straightforward multiply and add takes about 60% of the time for a single
digit on my machine compared to the above, and 55% for 19 digits (so
reasonably consistent). It's about 10x slower than fractions.

def convert_muladd(d, _trans=_trans, bytes=bytes):
    sign, digits, exp = d.as_tuple()
    num = 0

    for digit in digits:
        num *= 10
        num += digit

    if sign:
        num = -num

    return num, 10**-exp

Breakdown of the above (for 19 digits):

d.as_tuple() takes about 35% of the time.

The multiply and add takes about 55% of the time.

The exponentiation takes about 10% of the time.

Tim Delaney

[toc] | [prev] | [next] | [standalone]

#52953

[Multipart message — attachments visible in raw view] — view raw

On 25 August 2013 07:59, Tim Delaney <timothy.c.delaney@gmail.com> wrote:

> Breakdown of the above (for 19 digits):
>
> d.as_tuple() takes about 35% of the time.
>
> The multiply and add takes about 55% of the time.
>
> The exponentiation takes about 10% of the time.
>

Bah - sent before complete.

Since the multiply and add takes such a significant proportion of the time,
compiling the above with Cython should gain you a big win as well. Or find
some other way to turn that loop into native code.

Tim Delaney

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web