Re: find all multiplicands and multipliers for a number

References	(3 earlier) <87egnrb3il.fsf@jester.gateway.sonic.net> <87619387c0.fsf@elektro.pacujo.net> <87y4lya9eo.fsf@jester.gateway.sonic.net> <87zj6e7erv.fsf@elektro.pacujo.net> <87pp7aa6x0.fsf@jester.gateway.sonic.net>
Date	2015-04-12 07:10 +1000
Subject	Re: find all multiplicands and multipliers for a number
From	Chris Angelico <rosuav@gmail.com>
Newsgroups	comp.lang.python
Message-ID	<mailman.232.1428786656.12925.python-list@python.org> (permalink)

Show all headers | View raw

On Sun, Apr 12, 2015 at 3:52 AM, Paul Rubin <no.email@nospam.invalid> wrote:
>> PS Note that you're being "wasteful" by multiplying c*c over and over
>
> Yeah this is a reasonable point, though most of the c's should fit in a
> machine word, at least in my 64-bit system.  I think Python still
> separates ints and longs in the implementation.

I don't think it does. Performance doesn't seem to change in Py3 as
the numbers get bigger:

rosuav@sikorsky:~$ cat perftest.py
def naive_sum(top,base=0):
    i=0
    while i<top:
        i+=1
        base+=i
    return base

# Correctness test
print("Sum of numbers from 1 to 10 is: %d"%naive_sum(10))
print("Sum of numbers from 1 to 20 is: %d"%(naive_sum(20,1000)-1000))

import timeit
for base in (0, 10, 60, 100, 200):
    print("Base: 2**%d"%base)
    # Simpler than doing the whole iteration-judging thing ourselves
    timeit.main([
        "-s","from __main__ import naive_sum",
        "naive_sum(1000,%d)"%(2**base)
    ])

rosuav@sikorsky:~$ python2 perftest.py
Sum of numbers from 1 to 10 is: 55
Sum of numbers from 1 to 20 is: 210
Base: 2**0
10000 loops, best of 3: 89.6 usec per loop
Base: 2**10
10000 loops, best of 3: 89.9 usec per loop
Base: 2**60
10000 loops, best of 3: 92.3 usec per loop
Base: 2**100
10000 loops, best of 3: 145 usec per loop
Base: 2**200
10000 loops, best of 3: 153 usec per loop

Python 2.7: Clear difference in timing once all the numbers we're
using are above 2**64.

rosuav@sikorsky:~$ python3 perftest.py
Sum of numbers from 1 to 10 is: 55
Sum of numbers from 1 to 20 is: 210
Base: 2**0
10000 loops, best of 3: 145 usec per loop
Base: 2**10
10000 loops, best of 3: 144 usec per loop
Base: 2**60
10000 loops, best of 3: 155 usec per loop
Base: 2**100
10000 loops, best of 3: 151 usec per loop
Base: 2**200
10000 loops, best of 3: 156 usec per loop

Python 3.5: Much more consistent timing. Similarly, sticking an
explicit "L" suffix onto the number gives Py2 consistent timings:

rosuav@sikorsky:~$ python perftest.py
Sum of numbers from 1 to 10 is: 55
Sum of numbers from 1 to 20 is: 210
Base: 2**0
10000 loops, best of 3: 130 usec per loop
Base: 2**10
10000 loops, best of 3: 129 usec per loop
Base: 2**60
10000 loops, best of 3: 138 usec per loop
Base: 2**100
10000 loops, best of 3: 139 usec per loop
Base: 2**200
10000 loops, best of 3: 140 usec per loop

So it's the data type, not the size of the numbers, that makes the difference.

rosuav@sikorsky:~$ pike perftest.pike
Sum of numbers from 1 to 10 is: 55
Sum of numbers from 1 to 20 is: 210
Base: 2**0
100000 loops, best of 3: 18.3 usec per loop
Base: 2**10
100000 loops, best of 3: 18.5 usec per loop
Base: 2**60
100000 loops, best of 3: 18.5 usec per loop
Base: 2**100
10000 loops, best of 3: 398 usec per loop
Base: 2**200
10000 loops, best of 3: 406 usec per loop

Like Python 3, Pike has a single "int" type which stores
arbitrary-precision integers. Like Python 2, it has an optimization
for small ones. (One you can't defeat by using "2L".) Interestingly,
once you defeat Pike's optimizer, it's actually quite a lot slower
than Py3 at repeated bignum arithmetic.

Conclusion: Python 3 has one single integer type with consistent
performance across the board. "Machine word" is a meaningless concept
to Py3.

ChrisA

Thread

find all multiplicands and multipliers for a number ravas <ravas@outlook.com> - 2015-04-10 16:37 -0700
  Re: find all multiplicands and multipliers for a number Dave Angel <d@davea.name> - 2015-04-10 21:16 -0400
  Re: find all multiplicands and multipliers for a number Dave Angel <davea@davea.name> - 2015-04-10 21:06 -0400
    Re: find all multiplicands and multipliers for a number Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-11 12:04 +1000
      Re: find all multiplicands and multipliers for a number Stephen Tucker <stephen_tucker@sil.org> - 2015-04-11 06:11 +0100
      Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-10 23:08 -0700
        Re: find all multiplicands and multipliers for a number Marko Rauhamaa <marko@pacujo.net> - 2015-04-11 10:14 +0300
          Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-11 09:59 -0700
            Re: find all multiplicands and multipliers for a number Marko Rauhamaa <marko@pacujo.net> - 2015-04-11 20:31 +0300
              Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-11 10:52 -0700
                Re: find all multiplicands and multipliers for a number Chris Angelico <rosuav@gmail.com> - 2015-04-12 07:10 +1000
                Re: find all multiplicands and multipliers for a number Terry Reedy <tjreedy@udel.edu> - 2015-04-11 19:58 -0400
                Re: find all multiplicands and multipliers for a number Chris Angelico <rosuav@gmail.com> - 2015-04-12 10:16 +1000
          Re: find all multiplicands and multipliers for a number wolfram.hinderer@googlemail.com - 2015-04-11 16:17 -0700
            Re: find all multiplicands and multipliers for a number Marko Rauhamaa <marko@pacujo.net> - 2015-04-12 10:17 +0300
              Primes [was Re: find all multiplicands and multipliers for a number] Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-12 20:48 +1000
              Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-12 18:56 -0700
                Re: find all multiplicands and multipliers for a number Dave Angel <davea@davea.name> - 2015-04-12 22:35 -0400
                Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-12 20:30 -0700
                Re: find all multiplicands and multipliers for a number Dave Angel <davea@davea.name> - 2015-04-13 00:35 -0400
                Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-12 22:25 -0700
                Re: find all multiplicands and multipliers for a number Dave Angel <davea@davea.name> - 2015-04-13 01:43 -0400
                Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-12 22:57 -0700
                Re: find all multiplicands and multipliers for a number Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-13 17:21 +1000
                Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-13 19:42 -0700
                Re: find all multiplicands and multipliers for a number Chris Angelico <rosuav@gmail.com> - 2015-04-14 12:47 +1000
                Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-13 19:54 -0700
                Re: find all multiplicands and multipliers for a number Rustom Mody <rustompmody@gmail.com> - 2015-04-14 03:35 -0700
                Re: find all multiplicands and multipliers for a number Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-14 23:30 +1000
                Re: find all multiplicands and multipliers for a number Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-14 23:40 +1000
                Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-14 19:37 -0700
                Re: find all multiplicands and multipliers for a number Ian Kelly <ian.g.kelly@gmail.com> - 2015-04-15 09:59 -0600
                Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-15 09:21 -0700
                Re: find all multiplicands and multipliers for a number Chris Kaynor <ckaynor@zindagigames.com> - 2015-04-15 09:46 -0700
                Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-15 10:37 -0700
                Searching the archives Gil Dawson <Gil@GilDawson.com> - 2015-04-15 11:47 -0700
                Installing Python Gil Dawson <Gil@GilDawson.com> - 2015-04-15 12:09 -0700
                Re: Searching the archives Tim Golden <mail@timgolden.me.uk> - 2015-04-15 20:16 +0100
                Re: Installing Python Ned Deily <nad@acm.org> - 2015-04-15 13:32 -0700
                Re: find all multiplicands and multipliers for a number Rustom Mody <rustompmody@gmail.com> - 2015-04-15 21:17 -0700
        Re: find all multiplicands and multipliers for a number Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-11 17:35 +1000
          Re: find all multiplicands and multipliers for a number jonas.thornvall@gmail.com - 2015-04-11 01:47 -0700
          Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-11 09:31 -0700
            Re: find all multiplicands and multipliers for a number Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-12 12:22 +1000
              Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-11 21:24 -0700
                Re: find all multiplicands and multipliers for a number Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-12 14:29 +1000
          Re: find all multiplicands and multipliers for a number Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2015-04-11 12:41 -0400
            Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-11 10:02 -0700
        Re: find all multiplicands and multipliers for a number Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2015-04-11 12:37 -0400
      Re: find all multiplicands and multipliers for a number Brian Gladman <blindanagram@nowhere.net> - 2015-04-12 10:34 +0100
        Re: find all multiplicands and multipliers for a number Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-04-13 00:29 +1000
          Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-12 10:20 -0700
            Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-12 10:23 -0700
            Re: find all multiplicands and multipliers for a number Brian Gladman <blindanagram@nowhere.net> - 2015-04-12 20:15 +0100
              Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-12 12:45 -0700
          Re: find all multiplicands and multipliers for a number Brian Gladman <blindanagram@nowhere.net> - 2015-04-12 20:07 +0100
  Re: find all multiplicands and multipliers for a number Paul Rubin <no.email@nospam.invalid> - 2015-04-10 18:28 -0700
  Re: find all multiplicands and multipliers for a number Dave Farrance <DaveFarrance@OMiTTHiSyahooANDTHiS.co.uk> - 2015-04-11 10:03 +0100
  Re: find all multiplicands and multipliers for a number ravas <ravas@outlook.com> - 2015-04-11 10:11 -0700

csiph-web