Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.016 X-Spam-Evidence: '*H*': 0.97; '*S*': 0.00; 'mrab': 0.05; 'float': 0.07; 'constructor': 0.09; 'observation': 0.09; 'def': 0.12; '>>': 0.16; 'algorithm.': 0.16; 'numpy': 0.16; 'true:': 0.16; 'wrote:': 0.18; 'all,': 0.19; 'bit': 0.19; '>>>': 0.22; 'email addr:gmail.com>': 0.22; '>>>': 0.24; 'fraction': 0.24; '>': 0.26; 'header:In-Reply-To:1': 0.27; 'message-id:@mail.gmail.com': 0.30; "i'm": 0.30; 'guess': 0.33; 'but': 0.35; 'received:google.com': 0.35; 'being': 0.38; '8bit%:86': 0.38; 'to:addr:python-list': 0.38; 'pm,': 0.38; 'to:addr:python.org': 0.39; 'break': 0.61; 'more': 0.64; 'jul': 0.74; 'iterative': 0.84; 'subject:results': 0.91; '2013': 0.98 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=u1W1VJp73/vbRpqUnx6xEenum1jaMnMEtOJau4iEIeI=; b=gP8IkEudvkjOABELy7IsnETeZotGVv6BjaGTx5/CQyqVYM0+E1GDkVaGTK8Y3ssvKE YrxyPLntljhbLEl0lz3hQ8bB6b3GWaCuf6ZqYG04gV9lNb71l+vEV7baBpCyRuZwTE4N 9NBDgnF7T8VbzDUX41qJPViG4DU8RYMpvk8VlQyhAyb2szIjLdfeT+mjRqdVASPxsOph pVK1WAv5H13sl5ye5wYIakyqk7WYTQziRJeRu8Dqjw7JQdJU8Sr1wl8VPllVVB17U+D+ qnAri9HzouscqzbaG/opyTdETRFlq6ISEHcKf139SA+jBw7bCSzJz+dl045wAiAH4s9+ Nx0w== MIME-Version: 1.0 X-Received: by 10.68.28.232 with SMTP id e8mr70572535pbh.94.1375130121941; Mon, 29 Jul 2013 13:35:21 -0700 (PDT) In-Reply-To: References: <51f68d9c$0$30000$c3e8da3$5496439d@news.astraweb.com> <51F693B4.9000201@mrabarnett.plus.com> Date: Mon, 29 Jul 2013 14:35:21 -0600 Subject: Re: Unexpected results comparing float to Fraction From: Ian Kelly To: Python Content-Type: multipart/alternative; boundary=bcaec520eacd703b2404e2ac6eeb X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 92 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1375130131 news.xs4all.nl 15971 [2001:888:2000:d::a6]:41093 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:51493 --bcaec520eacd703b2404e2ac6eeb Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On Jul 29, 2013 1:37 PM, "Serhiy Storchaka" wrote: > > 29.07.13 19:09, MRAB =D0=BD=D0=B0=D0=BF=D0=B8=D1=81=D0=B0=D0=B2(=D0=BB=D0= =B0): > >> I'm surprised that Fraction(1/3) !=3D Fraction(1, 3); after all, floats >> are approximate anyway, and the float value 1/3 is more likely to be >> Fraction(1, 3) than Fraction(6004799503160661, 18014398509481984). > > > >>> def approximate_fraction(f): > prev_numer, numer =3D 0, 1 > prev_denom, denom =3D 1, 0 > r =3D f > while True: > i =3D math.floor(r) > prev_numer, numer =3D numer, i * numer + prev_numer > prev_denom, denom =3D denom, i * denom + prev_denom > if i =3D=3D r or numer / denom =3D=3D f: > break > r =3D 1 / (r - i) > > return Fraction(numer, denom) > > >>> approximate_fraction(1/3) > Fraction(1, 3) > >>> approximate_fraction(1e-17) > Fraction(1, 100000000000000000) > >>> approximate_fraction(math.pi) > Fraction(245850922, 78256779) > > I guess the Fraction constructor is more faster than this function. You might be able to speed it up a bit with numpy and the observation that the update is a matrix multiplication. But I don't think that you can get away from it being an iterative algorithm. --bcaec520eacd703b2404e2ac6eeb Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable


On Jul 29, 2013 1:37 PM, "Serhiy Storchaka" <storchaka@gmail.com> wrote:
>
> 29.07.13 19:09, MRAB =D0=BD=D0=B0=D0=BF=D0=B8=D1=81=D0=B0=D0=B2(=D0=BB= =D0=B0):
>
>> I'm surprised that Fraction(1/3) !=3D Fraction(1, 3); after al= l, floats
>> are approximate anyway, and the float value 1/3 is more likely to = be
>> Fraction(1, 3) than Fraction(6004799503160661, 18014398509481984).=
>
>
> >>> def approximate_fraction(f):
> =C2=A0 =C2=A0 prev_numer, numer =3D 0, 1
> =C2=A0 =C2=A0 prev_denom, denom =3D 1, 0
> =C2=A0 =C2=A0 r =3D f
> =C2=A0 =C2=A0 while True:
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 i =3D math.floor(r)
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 prev_numer, numer =3D numer, i * numer + p= rev_numer
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 prev_denom, denom =3D denom, i * denom + p= rev_denom
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 if i =3D=3D r or numer / denom =3D=3D f: > =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 break
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 r =3D 1 / (r - i)
>
> =C2=A0 =C2=A0 return Fraction(numer, denom)
>
> >>> approximate_fraction(1/3)
> Fraction(1, 3)
> >>> approximate_fraction(1e-17)
> Fraction(1, 100000000000000000)
> >>> approximate_fraction(math.pi)
> Fraction(245850922, 78256779)
>
> I guess the Fraction constructor is more faster than this function.

You might be able to speed it up a bit with numpy and the ob= servation that the update is a matrix multiplication. But I don't think= that you can get away from it being an iterative algorithm.

--bcaec520eacd703b2404e2ac6eeb--