Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!eternal-september.org!feeder.eternal-september.org!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!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.001 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'else:': 0.03; 'algorithm': 0.04; 'inspired': 0.05; 'root': 0.05; 'lines,': 0.07; 'sys': 0.07; 'calculating': 0.09; 'cc:addr:python-list': 0.11; 'def': 0.12; '>>': 0.16; '6:00': 0.16; 'interest,': 0.16; 'math,': 0.16; 'true:': 0.16; 'valueerror': 0.16; 'wrote:': 0.18; '<': 0.19; 'thu,': 0.19; 'import': 0.22; 'email addr:gmail.com>': 0.22; 'cc:addr:python.org': 0.22; 'integer': 0.24; 'stephen': 0.24; 'looks': 0.24; 'cc:2**0': 0.24; 'cc:no real name:2**0': 0.24; 'header:In-Reply-To:1': 0.27; 'raise': 0.29; 'message- id:@mail.gmail.com': 0.30; 'url:mailman': 0.30; "d'aprano": 0.31; 'steven': 0.31; 'url:python': 0.33; 'received:209.85': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'url:listinfo': 0.36; 'url:org': 0.36; 'positive': 0.37; 'received:209': 0.37; 'nov': 0.38; 'pm,': 0.38; 'url:mail': 0.40; 'matter': 0.61; 'to:addr:gmail.com': 0.65; 'here': 0.66; '20,': 0.68; 'optimized': 0.68; 'square': 0.74; 'ideas.': 0.84 X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=/H1LmsGxfVdJOPUSqrcCzaF4mLXjfQULusZ1bG7HodY=; b=UIgpHVRENAvZ53q96fMJRhNKCbQ7TU+zH3UzGdeQwU5YtWWxcHwnB7A//lZkAIFCle Z8Hn9XMGSCUdlGgu/it9y8C2VEUxilr6VGZ2WfQmXBmIslmcUraqR+ImZYAHnjB8PVOd UC7cPg6khpuxBuN9pQPhgXGt7iWoCbBDoNWB6yZ8IqfrxXC+88zCiJ2TrmwEdsd5s0PL D9EdMSfMhoWXZbw8BOqQ28DK85PmN8AeslF2a3apxYgobPPj/uUAs0bICDbemhVXVlJa GeyBadNJCQwc0bYWiL5afAVYcJeLRjQeVrEM6Q4f8PXNA/25heWpf43OBnNH+pnMWDKI rVCQ== X-Gm-Message-State: ALoCoQk9W5upO0RF0ma/eCftmqjzIV0n0UQmNcdbhY9l5vdPPN2fFc6y1fGrCwC5wzrortMk7l+3 MIME-Version: 1.0 X-Received: by 10.182.50.168 with SMTP id d8mr2119087obo.2.1416557757940; Fri, 21 Nov 2014 00:15:57 -0800 (PST) In-Reply-To: References: <54543787$0$13005$c3e8da3$5496439d@news.astraweb.com> Date: Fri, 21 Nov 2014 08:15:57 +0000 Subject: Re: Challenge: optimizing isqrt From: Stephen Tucker To: Serhiy Storchaka Content-Type: multipart/alternative; boundary=047d7b5d5c84f761a705085a0d8d X-Mailman-Approved-At: Sun, 23 Nov 2014 10:04:29 +0100 Cc: python-list@python.org 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: 121 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1416733470 news.xs4all.nl 2977 [2001:888:2000:d::a6]:47614 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:81349 --047d7b5d5c84f761a705085a0d8d Content-Type: text/plain; charset=UTF-8 Serhiy, This looks very good indeed. As a matter of interest, is there any particular reason you have used 2*b instead of b+b? Might b+b be faster than b*2? Also, in various lines, you use //2. Would >>1 be quicker? On reflection, perhaps you have had to use //2 because >>1 cannot be used in those situations. Stephen Tucker. On Thu, Nov 20, 2014 at 6:00 PM, Serhiy Storchaka wrote: > On 01.11.14 03:29, Steven D'Aprano wrote: > >> There is an algorithm for calculating the integer square root of any >> positive integer using only integer operations: >> > > Here is my optimized implementation inspired by Christian's ideas. > > import math, sys > > C1 = sys.float_info.radix ** sys.float_info.mant_dig > C2 = int(sys.float_info.max) > C3 = C2.bit_length() - 2 > > def isqrt(n): > if n < 0: > raise ValueError > if n == 0: > return 0 > if n <= C1: > return int(math.sqrt(n)) > if n <= C2: > x = int(math.sqrt(n)) > else: > b = (n.bit_length() - C3) // 2 > x = int(math.sqrt(n >> (2 * b))) << b > y = (x + n // x) // 2 > if y == x: > return x > while True: > x = y > y = (x + n // x) // 2 > if y >= x: > return x > > > -- > https://mail.python.org/mailman/listinfo/python-list > --047d7b5d5c84f761a705085a0d8d Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Serhiy,

This looks very good i= ndeed. As a matter of interest, is there any particular reason you have use= d 2*b instead of b+b? Might b+b be faster than b*2?

Also, in v= arious lines, you use //2. Would >>1 be quicker? On reflection, perha= ps you have had to use //2 because >>1 cannot be used in those situat= ions.

Stephen Tucker.




On Thu, Nov 20, 2014 at 6= :00 PM, Serhiy Storchaka <storchaka@gmail.com> wrote:
<= blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px= #ccc solid;padding-left:1ex">On 01.11.14 03:29, Steven D'Aprano wrote:=
There is an algorithm for calculating the integer square root of any
positive integer using only integer operations:

Here is my optimized implementation inspired by Christian's ideas.

import math, sys

C1 =3D sys.float_info.radix ** sys.float_info.mant_dig
C2 =3D int(sys.float_info.max)
C3 =3D C2.bit_length() - 2

def isqrt(n):
=C2=A0 =C2=A0 if n < 0:
=C2=A0 =C2=A0 =C2=A0 =C2=A0 raise ValueError
=C2=A0 =C2=A0 if n =3D=3D 0:
=C2=A0 =C2=A0 =C2=A0 =C2=A0 return 0
=C2=A0 =C2=A0 if n <=3D C1:
=C2=A0 =C2=A0 =C2=A0 =C2=A0 return int(math.sqrt(n))
=C2=A0 =C2=A0 if n <=3D C2:
=C2=A0 =C2=A0 =C2=A0 =C2=A0 x =3D int(math.sqrt(n))
=C2=A0 =C2=A0 else:
=C2=A0 =C2=A0 =C2=A0 =C2=A0 b =3D (n.bit_length() - C3) // 2
=C2=A0 =C2=A0 =C2=A0 =C2=A0 x =3D int(math.sqrt(n >> (2 * b))) <&l= t; b
=C2=A0 =C2=A0 y =3D (x + n // x) // 2
=C2=A0 =C2=A0 if y =3D=3D x:
=C2=A0 =C2=A0 =C2=A0 =C2=A0 return x
=C2=A0 =C2=A0 while True:
=C2=A0 =C2=A0 =C2=A0 =C2=A0 x =3D y
=C2=A0 =C2=A0 =C2=A0 =C2=A0 y =3D (x + n // x) // 2
=C2=A0 =C2=A0 =C2=A0 =C2=A0 if y >=3D x:
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 return x


--
https://mail.python.org/mailman/listinfo/python-list

--047d7b5d5c84f761a705085a0d8d--