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

Groups > comp.lang.python > #88788 > unrolled thread

find all multiplicands and multipliers for a number

Back to article view | Back to comp.lang.python

Contents

  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

Page 1 of 3  [1] 2 3  Next page →

#88788 — find all multiplicands and multipliers for a number

def m_and_m(dividend):
    rlist = []
    dm = divmod
    end = (dividend // 2) + 1
    for divisor in range(1, end):
        q, r = dm(dividend, divisor)
        if r is 0:
            rlist.append((divisor, q))
    return rlist

print(m_and_m(999))
---
output: [(1, 999), (3, 333), (9, 111), (27, 37), (37, 27), (111, 9), (333, 3)]
---

How do we describe this function? 
Does it have an established name?
What would you call it?
Does 'Rosetta Code' have it or something that uses it?
Can it be written to be more efficient?
What is the most efficient way to exclude the superfluous inverse tuples?
Can it be written for decimal numbers as input and/or output?

Thank you!

[toc] | [next] | [standalone]

#88789

On 04/10/2015 09:06 PM, Dave Angel wrote:
> On 04/10/2015 07:37 PM, ravas wrote:
>> def m_and_m(dividend):
>>      rlist = []
>>      dm = divmod
>>      end = (dividend // 2) + 1
>>      for divisor in range(1, end):
>>          q, r = dm(dividend, divisor)
>>          if r is 0:
>>              rlist.append((divisor, q))
>>      return rlist
>>
>> print(m_and_m(999))
>> ---
>> output: [(1, 999), (3, 333), (9, 111), (27, 37), (37, 27), (111, 9),
>> (333, 3)]
>> ---
>>
>> How do we describe this function?
>> Does it have an established name?
>> What would you call it?
>> Does 'Rosetta Code' have it or something that uses it?
>> Can it be written to be more efficient?
>> What is the most efficient way to exclude the superfluous inverse tuples?
>> Can it be written for decimal numbers as input and/or output?
>>
>> Thank you!
>>
>
> I'd call those factors of the original number.  For completeness, I'd
> include (999,1) at the end.
>
> If it were my problem, I'd be looking for only prime factors.  Then if
> someone wanted all the factors, they could derive them from the primes,
> by multiplying all possible combinations.
>
> The program can be sped up most obviously by stopping as soon as you get
> a tuple where divisor > q.  At that point, you can just repeat all the
> items, reversing divisor and q for each item.  Of course, now I notice
> you want to eliminate them.  So just break out of the loop when divisor
>  > q.
>
> You can gain some more speed by calculating the square root of the
> dividend, and stopping when you get there.
>
> But the real place to get improvement is to only divide by primes,
> rather than every possible integer.  And once you've done the division,
> let q be the next value for dividend.  So you'll get a list like
>
> [3, 3, 3, 37]
>
> for the value 999
>
> See:
> http://rosettacode.org/wiki/Factors_of_an_integer#Python
>
>
And

http://rosettacode.org/wiki/Prime_decomposition#Python

There the function that you should grok is  decompose()

-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#88790

On 04/10/2015 07:37 PM, ravas wrote:
> def m_and_m(dividend):
>      rlist = []
>      dm = divmod
>      end = (dividend // 2) + 1
>      for divisor in range(1, end):
>          q, r = dm(dividend, divisor)
>          if r is 0:
>              rlist.append((divisor, q))
>      return rlist
>
> print(m_and_m(999))
> ---
> output: [(1, 999), (3, 333), (9, 111), (27, 37), (37, 27), (111, 9), (333, 3)]
> ---
>
> How do we describe this function?
> Does it have an established name?
> What would you call it?
> Does 'Rosetta Code' have it or something that uses it?
> Can it be written to be more efficient?
> What is the most efficient way to exclude the superfluous inverse tuples?
> Can it be written for decimal numbers as input and/or output?
>
> Thank you!
>

I'd call those factors of the original number.  For completeness, I'd 
include (999,1) at the end.

If it were my problem, I'd be looking for only prime factors.  Then if 
someone wanted all the factors, they could derive them from the primes, 
by multiplying all possible combinations.

The program can be sped up most obviously by stopping as soon as you get 
a tuple where divisor > q.  At that point, you can just repeat all the 
items, reversing divisor and q for each item.  Of course, now I notice 
you want to eliminate them.  So just break out of the loop when divisor > q.

You can gain some more speed by calculating the square root of the 
dividend, and stopping when you get there.

But the real place to get improvement is to only divide by primes, 
rather than every possible integer.  And once you've done the division, 
let q be the next value for dividend.  So you'll get a list like

[3, 3, 3, 37]

for the value 999

See:
http://rosettacode.org/wiki/Factors_of_an_integer#Python


-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#88795

On Sat, 11 Apr 2015 11:06 am, Dave Angel wrote:

> But the real place to get improvement is to only divide by primes,
> rather than every possible integer.  And once you've done the division,
> let q be the next value for dividend.  So you'll get a list like
> 
> [3, 3, 3, 37]
> 
> for the value 999


Prime factorization is a *hard* problem. If it wasn't, most of modern
technology that relies on encryption (like https, ssh, internet banking
etc.) would be trivially broken.

But for what it is worth, my pyprimes library can return the prime
factorization of numbers:

py> import pyprimes.factors
py> pyprimes.factors.factorise(1234567890)
[2, 3, 3, 5, 3607, 3803]
py> pyprimes.factors.factorise(9753124680)
[2, 2, 2, 3, 3, 3, 5, 13, 191, 3637L]

It may be a bit slow for very large numbers. On my computer, this takes 20
seconds:

py> pyprimes.factors.factorise(2**111+1)
[3, 3, 1777, 3331, 17539, 25781083, 107775231312019L]


but that is the nature of factorising large numbers.


http://code.google.com/p/pyprimes/source/browse/



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#88802

[Multipart message — attachments visible in raw view] — view raw

Dario Alpern has written a program that uses the Elliptic Curve Method
(ECM) for factorising a number. ECM is one of the _very_ fast methods for
finding the prime factors of a number. He has even offered the code for his
program. You could have a go at using or converting his code to do what you
are wanting to do. The URL for this is

http://www.alpertron.com.ar/ECM.HTM

This program found the prime factors of  2^111+1  in less than 1 second on
my computer. (And that is the string I gave it.)

What has been said by previous contributors about the difficulty of
factorising numbers is all true. However, there are some relatively fast
algorithms out there. Try searching for

Number Field Sieve
Quadratic Number Field Sieve

and see where they take you.



On Sat, Apr 11, 2015 at 3:04 AM, Steven D'Aprano <
steve+comp.lang.python@pearwood.info> wrote:

> On Sat, 11 Apr 2015 11:06 am, Dave Angel wrote:
>
> > But the real place to get improvement is to only divide by primes,
> > rather than every possible integer.  And once you've done the division,
> > let q be the next value for dividend.  So you'll get a list like
> >
> > [3, 3, 3, 37]
> >
> > for the value 999
>
>
> Prime factorization is a *hard* problem. If it wasn't, most of modern
> technology that relies on encryption (like https, ssh, internet banking
> etc.) would be trivially broken.
>
> But for what it is worth, my pyprimes library can return the prime
> factorization of numbers:
>
> py> import pyprimes.factors
> py> pyprimes.factors.factorise(1234567890)
> [2, 3, 3, 5, 3607, 3803]
> py> pyprimes.factors.factorise(9753124680)
> [2, 2, 2, 3, 3, 3, 5, 13, 191, 3637L]
>
> It may be a bit slow for very large numbers. On my computer, this takes 20
> seconds:
>
> py> pyprimes.factors.factorise(2**111+1)
> [3, 3, 1777, 3331, 17539, 25781083, 107775231312019L]
>
>
> but that is the nature of factorising large numbers.
>
>
> http://code.google.com/p/pyprimes/source/browse/
>
>
>
> --
> Steven
>
> --
> https://mail.python.org/mailman/listinfo/python-list
>

[toc] | [prev] | [next] | [standalone]

#88804

Steven D'Aprano <steve+comp.lang.python@pearwood.info> writes:
> It may be a bit slow for very large numbers. On my computer, this takes 20
> seconds:
> py> pyprimes.factors.factorise(2**111+1)
> [3, 3, 1777, 3331, 17539, 25781083, 107775231312019L]

This takes about 4 seconds on a Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz
laptop (64 bit linux):

import itertools, time

def candidates():
    yield 2
    yield 3
    for i in itertools.count(5,6):
        yield i
        yield i+2

def fac(n):
    for c in candidates():
        if c*c > n:
            yield n
            break
        while n%c == 0:
            yield c
            n /= c

t0 = time.time()
print list(fac(2**111+1))
print time.time() - t0

[toc] | [prev] | [next] | [standalone]

#88807

Paul Rubin <no.email@nospam.invalid>:

> This takes about 4 seconds on a Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz
> laptop (64 bit linux):

Converted to Python3:
========================================================================
#!/usr/bin/env python3

import itertools, time

def candidates():
    yield 2
    yield 3
    for i in itertools.count(5,6):
        yield i
        yield i+2

def fac(n):
    for c in candidates():
        if c*c > n:
            yield n
            break
        while n%c == 0:
            yield c
            n //= c

t0 = time.time()
print(list(fac(2**111+1)))
print(time.time() - t0)
========================================================================

This is slightly faster:

========================================================================
#!/usr/bin/env python3

import time

def fac(n):
    for c in range(n):
        if c*c > n:
            yield n
            break
        while n%c == 0:
            yield c
            n //= c

t0 = time.time()
print(list(fac(2**111+1)))
print(time.time() - t0)
========================================================================


Marko

[toc] | [prev] | [next] | [standalone]

#88831

Marko Rauhamaa <marko@pacujo.net> writes:
> This is slightly faster:...
> def fac(n):
>     for c in range(n):
>         if c*c > n: ...

That's interesting and says something bad about generators in Python 3.
It's doing 3 times as many trial divisions as the version I posted, and
it's still faster?

xrange in Python 2 doesn't work with bignums, but using 
itertools.count(3,2) I get about 5.5 seconds and with itertools.count(3)
I get 11 seconds.

I wrote the same algorithm in Haskell and it's about 0.85 seconds,
probably due to native compilation and faster bignums.  A naive
implementation of Pollard's rho algorithm in Haskell is basically
instantaneous on that number.  I might try coding Pollard's method or
Brent's improvement in Python.

[toc] | [prev] | [next] | [standalone]

#88834

Paul Rubin <no.email@nospam.invalid>:

> Marko Rauhamaa <marko@pacujo.net> writes:
>> This is slightly faster:...
>> def fac(n):
>>     for c in range(n):
>>         if c*c > n: ...
>
> That's interesting and says something bad about generators in Python
> 3. It's doing 3 times as many trial divisions as the version I posted,
> and it's still faster?

I think it mostly says divisions are not so evil as you think they might
be. Also, I wouldn't bother optimizing Python's performance too much.
Python is very wasteful wrt space and speed -- and for good reasons.
Either Python does it for you or it doesn't. If it doesn't, write that
part in C.

Myself, I write in bash what I can. What I can't, I write in Python.
What I can't write in Python, I write in C.


Marko

PS Note that you're being "wasteful" by multiplying c*c over and over
again instead of calculating the square root of n a handful of times.
But since multiplication isn't all that expensive, the square root
optimization doesn't affect execution time measurably.

[toc] | [prev] | [next] | [standalone]

#88835

Marko Rauhamaa <marko@pacujo.net> writes:
> I think it mostly says divisions are not so evil as you think they might
> be.

They are bignum divisions which are much more expensive than machine
divisions.  And it's not just the divisions, it's also the number of
iterations through the whole loop.  And the Python 2 vs Python 3
difference is still unexplained.

> 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.

[toc] | [prev] | [next] | [standalone]

#88841

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

[toc] | [prev] | [next] | [standalone]

#88849

On 4/11/2015 5:10 PM, Chris Angelico wrote:
> 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.

In 3.0, the 2.x int class and intobject.c were removed and the long 
class was renamed int, while longobject.c remained, with code relevant 
to the int class removed. I believe longobject effectively represents 
ints in base 2**15 or 2**30 (or 31?) for 32 and 64 bit machines, so that 
products of 'digits' fit in a single machine word.  (I am not sure if 
the increased size for 64 bit machines was implemented or not.)

 > Performance doesn't seem to change in Py3 as
 > the numbers get bigger:

I suspect the effect is more dramatic with multiplication.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#88850

On Sun, Apr 12, 2015 at 9:58 AM, Terry Reedy <tjreedy@udel.edu> wrote:
> I believe longobject effectively represents ints in base 2**15 or 2**30 (or
> 31?) for 32 and 64 bit machines, so that products of 'digits' fit in a
> single machine word.  (I am not sure if the increased size for 64 bit
> machines was implemented or not.)
>
>> Performance doesn't seem to change in Py3 as
>> the numbers get bigger:
>
> I suspect the effect is more dramatic with multiplication.

Sorry, sloppy language. Of course larger numbers will be a bit slower,
but there's no stark change at the edge of the machine word. The
performance loss from going from one limb to two will be comparable to
the loss from going from five to six, where it's already well past
machine integer. In Py2, there's a significant difference between
"int" performance and "long" performance (regardless of the actual
size of integer involved), but Py3 is more consistent.

It's a missed optimization at worst, but the upshot is that a Python
programmer doesn't need to think about integer sizes at all.

ChrisA

[toc] | [prev] | [next] | [standalone]

#88847

Am Samstag, 11. April 2015 09:14:50 UTC+2 schrieb Marko Rauhamaa:
> Paul Rubin <no.email@nospam.invalid>:
> 
> > This takes about 4 seconds on a Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz
> > laptop (64 bit linux):
> 
> Converted to Python3:
> ========================================================================
> #!/usr/bin/env python3
> 
> import itertools, time
> 
> def candidates():
>     yield 2
>     yield 3
>     for i in itertools.count(5,6):
>         yield i
>         yield i+2
> 
> def fac(n):
>     for c in candidates():
>         if c*c > n:
>             yield n
>             break
>         while n%c == 0:
>             yield c
>             n //= c
> 
> t0 = time.time()
> print(list(fac(2**111+1)))
> print(time.time() - t0)
> ========================================================================
> 
> This is slightly faster:
> 
> ========================================================================
> #!/usr/bin/env python3
> 
> import time
> 
> def fac(n):
>     for c in range(n):
>         if c*c > n:
>             yield n
>             break
>         while n%c == 0:
>             yield c
>             n //= c
> 
> t0 = time.time()
> print(list(fac(2**111+1)))
> print(time.time() - t0)
> ========================================================================
> 

I get other results on 3.2.3:

n % 0 raises ZeroDivisionError.
After fixing that by using range(2, n) it takes about three times as long as the original version, which is what I'd expect.

[toc] | [prev] | [next] | [standalone]

#88862

wolfram.hinderer@googlemail.com:

> I get other results on 3.2.3:
>
> n % 0 raises ZeroDivisionError.
> After fixing that by using range(2, n) it takes about three times as
> long as the original version, which is what I'd expect.

You're right. I got wrong results because I ran a wrong command!

The range(2, n) version is 3 times slower than the candidates() version.

And in fact, the sqrt optimization now makes the original version 20%
faster:

========================================================================
#!/usr/bin/env python3

import itertools, time, math

def candidates():
    yield 2
    yield 3
    for i in itertools.count(5,6):
        yield i
        yield i+2

def fac(n):
    bound = int(math.sqrt(n))
    for c in candidates():
        if c > bound:
            yield n
            break
        if n%c == 0:
            yield c
            n //= c
            while n%c == 0:
                yield c
                n //= c
            bound = int(math.sqrt(n))

t0 = time.time()
print(list(fac(2**111+1)))
print(time.time() - t0)
========================================================================


Marko

[toc] | [prev] | [next] | [standalone]

#88865 — Primes [was Re: find all multiplicands and multipliers for a number]

On Sun, 12 Apr 2015 05:17 pm, Marko Rauhamaa wrote:

> The range(2, n) version is 3 times slower than the candidates() version.
> 
> And in fact, the sqrt optimization now makes the original version 20%
> faster:


MY pyprimes module includes a series of progressively better (or, in the
opposite direction, progressively worse) prime number generators. The doc
string for the pyprimes.awful module says:

"""
This is a collection of awful and naive prime-related functions, supplied
for educational purposes, as toys, curios, or as terrible warnings on
what **not** to do.

None of these methods have acceptable performance in practice; they are
barely tolerable even for the first 100 primes.
"""

It starts off with an adaptation of the very first prime generator I ever
wrote, in RPL on a HP calculator oh so many years ago. It was more or less
a naive implementation of the mathematical definition: for each candidate
prime n, I test it against *every* potential divisor starting with 2 and
ending with n-1. Yes, I actually did write that for real.

Not surprisingly, it starts off horribly slow, and gets ever slower as the
primes get further apart. Over the first 1000 primes, it is five times
slower than the second worst performer, and about 1430 times slower than
the best performer.

Starting with that as the base:

- stopping once you hit a factor gives you a factor of 5 speed up;
- skipping even numbers (apart from 2) gives you an additional 
  factor of 2 speed up;
- stopping at the square root of n instead of going all the way to 
  n-1 gives you an additional speed up of 16 times;

- dividing only by primes rather than all odd numbers *slows* the
  function down by about 5%, at least for generating the first 
  1000 primes.

Dividing only by primes doesn't pay off until you get to about fifty
thousand primes or so.

So that's a good example of how some optimizations don't pay off until you
get to sufficiently large inputs. Even so, none of those four "awful" trial
division generators perform well enough to use in production. For that, you
have to start using a sieve algorithm.



On my computer, I get these results for generating the first 1000 primes:


[steve@ando src]$ python2.7 pyprimes/speed.py
Calculating speeds for first 1000 primes...
Done!
Total elapsed time: 5.6 seconds

Generator                             Elapsed    Speed
                                      (sec)      (primes/sec)
==============================================================
pyprimes.awful.primes0                4.14         241.8
pyprimes.awful.primes1                0.79        1271.8
pyprimes.awful.primes2                0.41        2445.5
pyprimes.awful.turner                 0.18        5495.9
pyprimes.probabilistic.primes         0.03       30840.5
pyprimes.awful.primes4                0.03       38853.1
pyprimes.awful.primes3                0.02       40940.0
pyprimes.sieves.sieve                 0.01      133742.7
pyprimes.sieves.cookbook              0.01      194028.0
pyprimes.sieves.wheel                 0.00      206483.7
pyprimes.sieves.croft                 0.00      344359.9
==============================================================




Here are the results for the four sieves, taken over the first million
primes.



Calculating speeds for first 1000000 primes...
Done!
Total elapsed time: 167.2 seconds

Generator                             Elapsed    Speed
                                      (sec)      (primes/sec)
==============================================================
pyprimes.sieves.wheel                 122.50        8163.4
pyprimes.sieves.sieve                 17.09       58509.9
pyprimes.sieves.cookbook              16.52       60520.6
pyprimes.sieves.croft                 10.48       95445.0
==============================================================


The Croft Spiral algorithm averages 95 thousand primes per second over the
first million primes, significantly better than the next best algorithm.
I'm not sure why the wheel algorithm starts off so promising and then falls
so badly behind the other three.


http://code.google.com/p/pyprimes/source/browse/



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#88900

Marko Rauhamaa <marko@pacujo.net> writes:
> And in fact, the sqrt optimization now makes the original version 20%
> faster: ...
>     bound = int(math.sqrt(n))

That could conceivably fail because of floating point roundoff or
overflow, e.g. fac(3**1000).  A fancier approach to finding the integer
square root might be worthwhile though.

[toc] | [prev] | [next] | [standalone]

#88904

On 04/12/2015 09:56 PM, Paul Rubin wrote:
> Marko Rauhamaa <marko@pacujo.net> writes:
>> And in fact, the sqrt optimization now makes the original version 20%
>> faster: ...
>>      bound = int(math.sqrt(n))
>
> That could conceivably fail because of floating point roundoff or
> overflow, e.g. fac(3**1000).  A fancier approach to finding the integer
> square root might be worthwhile though.
>

If I were trying to get a bound for stopping the divide operation, on a 
value too large to do exact real representation, I'd try doing just a 
few iterations of Newton's method.  Even if you don't converge it to get 
an exact value, you can arrange that you have a number that's for sure 
no less than the square root.  And you can get pretty close in just a 
few times around.

-- 
DaveA

[toc] | [prev] | [next] | [standalone]

#88907

Dave Angel <davea@davea.name> writes:
> If I were trying to get a bound for stopping the divide operation, on
> a value too large to do exact real representation, I'd try doing just
> a few iterations of Newton's method.

Python ninja trick: math.log works on bignums too large to be
represented as floats ;-)

[toc] | [prev] | [next] | [standalone]

#88908

On 04/12/2015 11:30 PM, Paul Rubin wrote:
> Dave Angel <davea@davea.name> writes:
>> If I were trying to get a bound for stopping the divide operation, on
>> a value too large to do exact real representation, I'd try doing just
>> a few iterations of Newton's method.
>
> Python ninja trick: math.log works on bignums too large to be
> represented as floats ;-)
>

But doesn't math.pow return a float?   Af first crack I figured it was 
because I had supplied math.e as the first argument.  But I have the 
same problem with  (python 3.4)


x = 2596148429267413814265248164610047
print( math.pow(2, math.log2(x)) )
2.596148429267414e+33

Or were you saying bignums bigger than a float can represent at all?  Like:

 >>> x = 2**11111 -1
 >>> len(str(x))
3345
 >>> math.log2(x)
11111.0
 >>> math.pow(2, math.log2(x)//2)
Traceback (most recent call last):
   File "<stdin>", line 1, in <module>
OverflowError: math range error


-- 
DaveA

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.lang.python

csiph-web