Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #81532

Re: Challenge: optimizing isqrt

Show all headers | View raw

On 11/25/2014 02:31 PM, Serhiy Storchaka wrote:
> п'ятниця, 21-лис-2014 08:15:57 ви написали:
>> 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 reflection,
>> 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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Challenge: optimizing isqrt Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-11-01 12:29 +1100
  Re: Challenge: optimizing isqrt Chris Angelico <rosuav@gmail.com> - 2014-11-01 13:12 +1100
  Re: Challenge: optimizing isqrt Christian Gollwitzer <auriocus@gmx.de> - 2014-11-01 09:02 +0100
    Re: Challenge: optimizing isqrt Christian Gollwitzer <auriocus@gmx.de> - 2014-11-01 09:09 +0100
    Re: Challenge: optimizing isqrt Chris Angelico <rosuav@gmail.com> - 2014-11-01 19:13 +1100
      Re: Challenge: optimizing isqrt Christian Gollwitzer <auriocus@gmx.de> - 2014-11-01 09:25 +0100
        Re: Challenge: optimizing isqrt Chris Angelico <rosuav@gmail.com> - 2014-11-01 19:33 +1100
          Re: Challenge: optimizing isqrt Christian Gollwitzer <auriocus@gmx.de> - 2014-11-01 09:38 +0100
            Re: Challenge: optimizing isqrt Chris Angelico <rosuav@gmail.com> - 2014-11-01 19:45 +1100
  Re: Challenge: optimizing isqrt Akira Li <4kir4.1i@gmail.com> - 2014-11-01 12:12 +0300
  Re: Challenge: optimizing isqrt Serhiy Storchaka <storchaka@gmail.com> - 2014-11-20 20:00 +0200
  Re: Challenge: optimizing isqrt Stephen Tucker <stephen_tucker@sil.org> - 2014-11-21 08:15 +0000
  Re: Challenge: optimizing isqrt Dave Angel <davea@davea.name> - 2014-11-23 10:43 -0500
  Re: Challenge: optimizing isqrt Serhiy Storchaka <storchaka@gmail.com> - 2014-11-25 21:31 +0200
  Re: Challenge: optimizing isqrt Dave Angel <davea@davea.name> - 2014-11-25 19:46 -0500
  Re: Challenge: optimizing isqrt Stephen Tucker <stephen_tucker@sil.org> - 2014-11-26 07:57 +0000
    Re: Challenge: optimizing isqrt Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-11-26 21:25 +1100
  Re: Challenge: optimizing isqrt Serhiy Storchaka <storchaka@gmail.com> - 2014-11-26 18:24 +0200

csiph-web