Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!xlned.com!feeder5.xlned.com!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <521828e7$0$29986$c3e8da3$5496439d@news.astraweb.com>
References: <521828e7$0$29986$c3e8da3$5496439d@news.astraweb.com>
Date: Sun, 25 Aug 2013 07:59:15 +1000
Subject: Re: Fast conversion of numbers to numerator/denominator pairs
From: Tim Delaney <timothy.c.delaney@gmail.com>
To: "Steven D'Aprano" <steve+comp.lang.python@pearwood.info>
Content-Type: multipart/alternative; boundary=047d7b5d33d452421404e4b8a292
Cc: Python-List <python-list@python.org>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.202.1377381558.19984.python-list@python.org>
Lines: 79
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:52952

--047d7b5d33d452421404e4b8a292
Content-Type: text/plain; charset=UTF-8

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

--047d7b5d33d452421404e4b8a292
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">On 24 August 2013 13:30, Steven D&#39;Aprano <span dir=3D"=
ltr">&lt;<a href=3D"mailto:steve+comp.lang.python@pearwood.info" target=3D"=
_blank">steve+comp.lang.python@pearwood.info</a>&gt;</span> wrote:<br><div =
class=3D"gmail_extra">
<div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margi=
n:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204=
);border-left-style:solid;padding-left:1ex"><br>
def convert(d):<br>
=C2=A0 =C2=A0 sign, digits, exp =3D d.as_tuple()<br>
=C2=A0 =C2=A0 num =3D int(&#39;&#39;.join([str(digit) for digit in digits])=
)<br>
=C2=A0 =C2=A0 if sign: num =3D -num<br>
=C2=A0 =C2=A0 return num, 10**-exp<br>
<br>which is faster, but not fast enough. Any suggestions?<br></blockquote>=
<div><br></div><div>Straightforward multiply and add takes about 60% of the=
 time for a single digit on my machine compared to the above, and 55% for 1=
9 digits (so reasonably consistent). It&#39;s about 10x slower than fractio=
ns.</div>
<div><br></div><div><div>def convert_muladd(d, _trans=3D_trans, bytes=3Dbyt=
es):</div><div>=C2=A0 =C2=A0 sign, digits, exp =3D d.as_tuple()</div><div>=
=C2=A0 =C2=A0 num =3D 0</div><div><br></div><div>=C2=A0 =C2=A0 for digit in=
 digits:</div><div>=C2=A0 =C2=A0 =C2=A0 =C2=A0 num *=3D 10</div>
<div>=C2=A0 =C2=A0 =C2=A0 =C2=A0 num +=3D digit</div><div><br></div><div>=
=C2=A0 =C2=A0 if sign:</div><div>=C2=A0 =C2=A0 =C2=A0 =C2=A0 num =3D -num</=
div><div><br></div><div>=C2=A0 =C2=A0 return num, 10**-exp</div></div><div>=
<br></div><div>Breakdown of the above (for 19 digits):</div><div>
<br></div><div>d.as_tuple() takes about 35% of the time.</div><div><br></di=
v><div>The multiply and add takes about 55% of the time.</div><div><br></di=
v><div>The exponentiation takes about 10% of the time.</div><div><br></div>
<div>Tim Delaney</div></div></div></div>

--047d7b5d33d452421404e4b8a292--