Fast conversion of numbers to numerator/denominator pairs

[Steven D'Aprano]

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?

 

[Ian Kelly]

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

 

[Ian Kelly]

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.

 

[Peter Otten]

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.

 

[Tim Delaney]

On 24 August 2013 13:30, Steven D'Aprano <

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

 

[Tim Delaney]

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