Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.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.121 X-Spam-Level: * X-Spam-Evidence: '*H*': 0.76; '*S*': 0.00; 'argument': 0.05; 'lines,': 0.07; 'assuming': 0.09; 'cc:addr:python-list': 0.11; 'received:209.85.218': 0.14; '(about': 0.16; 'interest,': 0.16; 'processor,': 0.16; 'thanks,': 0.17; 'wrote:': 0.18; 'wed,': 0.18; 'slightly': 0.19; 'seems': 0.21; '>>>': 0.22; 'cc:addr:python.org': 0.22; "aren't": 0.24; 'earlier': 0.24; 'looks': 0.24; 'cc:2**0': 0.24; 'cc:no real name:2**0': 0.24; 'post': 0.26; 'supported': 0.26; 'header:In-Reply-To:1': 0.27; 'function': 0.29; 'am,': 0.29; 'bigger': 0.30; 'message- id:@mail.gmail.com': 0.30; 'url:mailman': 0.30; 'too.': 0.31; '20%': 0.31; 'faster,': 0.31; 'oversight': 0.31; 'another': 0.32; 'url:python': 0.33; 'table': 0.34; 'could': 0.34; 'received:209.85': 0.35; 'one,': 0.35; 'test': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'version': 0.36; 'really': 0.36; 'skip:\xd0 10': 0.36; 'url:listinfo': 0.36; 'shows': 0.36; 'url:org': 0.36; 'two': 0.37; 'received:209': 0.37; 'performance': 0.37; 'skip:& 10': 0.38; 'nov': 0.38; 'pm,': 0.38; 'previous': 0.38; 'skip:& 20': 0.39; 'url:mail': 0.40; 'skip:u 10': 0.60; 'dave': 0.60; 'hope': 0.61; 'new': 0.61; 'matter': 0.61; 'kind': 0.63; 'face': 0.64; 'become': 0.64; 'total': 0.65; 'worth': 0.66; 'here': 0.66; '26,': 0.68; '8bit%:94': 0.72; '10%': 0.74; '8bit%:43': 0.74; '2.7.': 0.84; 'faster.': 0.84; 'improvement': 0.84; 'measurable': 0.84; 'angel': 0.91; 'whereas': 0.91 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=MebtSutHVzWng8uAWIhdWAbyhireJwGsowmn608tu2g=; b=R2ZCmhPCfgTcNera6rJSb+il3YY3NHJZU1PdmKRFCHkL9zLh29Fg9O/cGjCSOCDPXy zxQkST26lNyqfjmWeEip5vNaUXQtUWq+erPhq67twb9LsXOOwsC1fjv5c+B4hv/82HGp gt/1KCi9rmAu+lPHLjwWjCMBkC65zEkzi8LMVHsqyqyKFbJVnk3O5JUUy7GgEPWTljY3 GzvWvTb+APUZR0qN4dVwySrPryzZsYCINEQiI6wiMsq4u/k1/lhABW3PVBKoUmqUYjW/ ruIWI5SQKbd79WUOgOyThGza0bEUR0IDl8LpdcTCl18DSccZB+JVHRib1Zt+wu7qDbMr Qipg== X-Gm-Message-State: ALoCoQnwTNgiWotVnk7foi6D539WfegHz0kFyPH7iZZ4aUpBmfd7GYBoTtSyTYR3OtNUv1WyDVaX MIME-Version: 1.0 X-Received: by 10.202.199.196 with SMTP id x187mr18278734oif.61.1416988668984; Tue, 25 Nov 2014 23:57:48 -0800 (PST) In-Reply-To: <547522DD.1020201@davea.name> References: <54543787$0$13005$c3e8da3$5496439d@news.astraweb.com> <547522DD.1020201@davea.name> Date: Wed, 26 Nov 2014 07:57:48 +0000 Subject: Re: Challenge: optimizing isqrt From: Stephen Tucker To: Dave Angel Content-Type: multipart/alternative; boundary=001a11c17dee44233f0508be6289 X-Mailman-Approved-At: Wed, 26 Nov 2014 09:31:18 +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: 131 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1416990679 news.xs4all.nl 2966 [2001:888:2000:d::a6]:59261 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:81553 --001a11c17dee44233f0508be6289 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Another _possible_ performance improvement that is staring us in the face is that 2*b could be replaced with b<<1. Given that b+b (an earlier suggestion of mine) involves two table look-ups for b, whereas b<<1 only involves one, it seems that the scope here for improvement is significant. By the way, I hope this post is not "top-posted" as my previous one was. Apologies for that - I am new to this kind of thing. On Wed, Nov 26, 2014 at 12:46 AM, Dave Angel wrote: > On 11/25/2014 02:31 PM, Serhiy Storchaka wrote: > >> =D0=BF'=D1=8F=D1=82=D0=BD=D0=B8=D1=86=D1=8F, 21-=D0=BB=D0=B8=D1=81-2014 = 08:15:57 =D0=B2=D0=B8 =D0=BD=D0=B0=D0=BF=D0=B8=D1=81=D0=B0=D0=BB=D0=B8: >> >>> 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? >>> >> >> Yes, it is slightly faster, but the effect is indiscernible in total >> time. But >> there is not harm to use b+b. >> >> Also, in various lines, you use //2. Would >>1 be quicker? On reflectio= n, >>> perhaps you have had to use //2 because >>1 cannot be used in those >>> situations. >>> >> >> I thought this effect would be insignificant too. But actually it is >> measurable >> (about 10% for some input). Thanks, this optimization is worth to be >> applied. >> >> > Unfortunately, for many values, the version of the function with >>1 is > slower. It's only when the argument is bigger than 10**40 that it's as > much as 1% faster. But it's true that for really large values, it's > quicker. > > A quick test shows that 3.3 is about 20% faster for both these functions > than 2.7. > > My oversight earlier was assuming a native type. Once you get into > "longs" which aren't supported by the processor, the shift will likely > become much faster than divide. > > > -- > DaveA > -- > https://mail.python.org/mailman/listinfo/python-list > --001a11c17dee44233f0508be6289 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Another _possible_ performance improvement that is st= aring us in the face is that 2*b could be replaced with b<<1. Given t= hat b+b (an earlier suggestion of mine) involves two table look-ups for b, = whereas b<<1 only involves one, it seems that the scope here for impr= ovement is significant.

By the way, I hope this post is not &q= uot;top-posted" as my previous one was. Apologies for that - I am new = to this kind of thing.



On Wed, Nov 26, 2014 at 12:46 AM, Dave An= gel <davea@davea.name> wrote:
On 11/25/2014 02:31 PM, Serhiy S= torchaka wrote:
=D0=BF'=D1=8F=D1=82=D0=BD=D0=B8=D1=86=D1=8F, 21-=D0=BB=D0=B8=D1=81-2014= 08:15:57 =D0=B2=D0=B8 =D0=BD=D0=B0=D0=BF=D0=B8=D1=81=D0=B0=D0=BB=D0=B8:
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?

Yes, it is slightly faster, but the effect is indiscernible in total
time. But
there is not harm to use b+b.

Also, in various lines, you use //2. Would >>1 be quicker? On reflect= ion,
perhaps you have had to use //2 because >>1 cannot be used in those situations.

I thought this effect would be insignificant too. But actually it is
measurable
(about 10% for some input). Thanks, this optimization is worth to be
applied.


Unfortunately, for many values, the version of the function with >>1 = is slower.=C2=A0 It's only when the argument is bigger than 10**40 that= it's as much as 1% faster.=C2=A0 But it's true that for really lar= ge values, it's quicker.

A quick test shows that 3.3 is about 20% faster for both these functions th= an 2.7.

My oversight earlier was assuming a native type.=C2=A0 Once you get into &q= uot;longs" which aren't supported by the processor, the shift will= likely become much faster than divide.


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

--001a11c17dee44233f0508be6289--