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 3 of 3 — ← Prev page 1 2 [3]

#88808

On Sat, 11 Apr 2015 04:08 pm, Paul Rubin wrote:

> 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):

Nice for some who have fast machines, but on my old jalopy, your code takes
110 seconds, more than five times slower than mine. It also returns the
wrong result:

[3, 3, 3, 3, 7, 19, 73, 87211, 262657, 1.4411518807585587e+17]

Oops, you have a float in there, how did that happen?

We can tell your code gives the wrong result. It claims that 7 is a factor
of 2**111+1:

py> n = 2**111 + 1
py> itertools.islice(fac(n), 0, 5)
<itertools.islice object at 0xb7c8f914>
py> list(itertools.islice(fac(n), 0, 5))
[3, 3, 3, 3, 7]


but that can't be right:

py> n % 7
2L

Seven in not a factor of 2**111 + 1.

The reason your code gives wrong results is that you perform true division /
rather than integer division // which means that you with n a float, which
loses precision:

py> (n/9) % 3  # nine is a factor
0.0
py> (n//9) % 3  # exact, without rounding
1L



-- 
Steven

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

#88810

Den lördag 11 april 2015 kl. 09:35:22 UTC+2 skrev Steven D'Aprano:
> On Sat, 11 Apr 2015 04:08 pm, Paul Rubin wrote:
> 
> > 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):
> 
> Nice for some who have fast machines, but on my old jalopy, your code takes
> 110 seconds, more than five times slower than mine. It also returns the
> wrong result:
> 
> [3, 3, 3, 3, 7, 19, 73, 87211, 262657, 1.4411518807585587e+17]
> 
> Oops, you have a float in there, how did that happen?
> 
> We can tell your code gives the wrong result. It claims that 7 is a factor
> of 2**111+1:
> 
> py> n = 2**111 + 1
> py> itertools.islice(fac(n), 0, 5)
> <itertools.islice object at 0xb7c8f914>
> py> list(itertools.islice(fac(n), 0, 5))
> [3, 3, 3, 3, 7]
> 
> 
> but that can't be right:
> 
> py> n % 7
> 2L
> 
> Seven in not a factor of 2**111 + 1.
> 
> The reason your code gives wrong results is that you perform true division /
> rather than integer division // which means that you with n a float, which
> loses precision:
> 
> py> (n/9) % 3  # nine is a factor
> 0.0
> py> (n//9) % 3  # exact, without rounding
> 1L
> 
> 
> 
> -- 
> Steven

Love it.

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

#88828

Steven D'Aprano <steve+comp.lang.python@pearwood.info> writes:
> [3, 3, 3, 3, 7, 19, 73, 87211, 262657, 1.4411518807585587e+17]
> Oops, you have a float in there, how did that happen?

Looks like you are using a broken version of Python.

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

#88852

On Sun, 12 Apr 2015 02:31 am, Paul Rubin wrote:

> Steven D'Aprano <steve+comp.lang.python@pearwood.info> writes:
>> [3, 3, 3, 3, 7, 19, 73, 87211, 262657, 1.4411518807585587e+17]
>> Oops, you have a float in there, how did that happen?
> 
> Looks like you are using a broken version of Python.

Well, we know about people who blame their tools ... *wink*

I'm really not using a broken version of Python. You're the one using /=
instead of integer division.

Ah, the penny drops! Are you using Python 2.7 with old-style division? That
would explain it.

Okay, let me do the experiment again, this time with old-division enabled,
using 2.7.


py> n = 2**111 + 1
py> with Stopwatch():
...     pyprimes.factors.factorise(n)
...
[3, 3, 1777, 3331, 17539, 25781083, 107775231312019L]
time taken: 24.011609 seconds
py> with Stopwatch():
...     list(fac(n))
...
[3, 3, 1777, 3331, 17539, 25781083, 107775231312019L]
time taken: 11.743913 seconds

That's certainly an improvement over what I got before, both in time and
correctness. I didn't expect that float arithmetic would be so much slower
than int arithmetic! Go figure.


Here's another demonstration:

py> m = 2**117 - 1
py> with Stopwatch():
...     pyprimes.factors.factorise(m)
...
[7, 73, 79, 937, 6553, 8191, 86113, 121369, 7830118297L]
time taken: 0.089402 seconds
py> with Stopwatch():
...     list(fac(m))
...
[7, 73, 79, 937, 6553, 8191, 86113, 121369, 7830118297L]
time taken: 0.047645 seconds


Nice! Except that your fac() function has a bug: it includes 1 as a prime
factor for some values, which is strictly incorrect.

py> list(fac(4))
[2, 2, 1]

That probably won't make much difference for the speed, but it will
certainly make a difference with the correctness.

Oh:

py> pyprimes.factors.factorise(-1234567)
[-1, 127, 9721]
py> list(fac(-1234567))
[-1234567]


-- 
Steven

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

#88855

Steven D'Aprano <steve+comp.lang.python@pearwood.info> writes:
> Ah, the penny drops! Are you using Python 2.7 with old-style division? That
> would explain it.

Yes, see also the use of the print statement in that post.  I'm
surprised the code compiled at all in Python 3.

> Nice! Except that your fac() function has a bug: it includes 1 as a prime
> factor for some values, which is strictly incorrect.

Good catch, I noticed that too after posting.  

This might be of interest:

http://wrap.warwick.ac.uk/54707/1/WRAP_Hart_S1446788712000146a.pdf

I haven't tried figuring it out or coding it yet.

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

#88856

On Sun, 12 Apr 2015 02:24 pm, Paul Rubin wrote:

> Steven D'Aprano <steve+comp.lang.python@pearwood.info> writes:
>> Ah, the penny drops! Are you using Python 2.7 with old-style division?
>> That would explain it.
> 
> Yes, see also the use of the print statement in that post.  I'm
> surprised the code compiled at all in Python 3.

I wasn't using Python 3. I was using 2.7 with "from __future__ import
division", as the BDFL intended :-)


>> Nice! Except that your fac() function has a bug: it includes 1 as a prime
>> factor for some values, which is strictly incorrect.
> 
> Good catch, I noticed that too after posting.
> 
> This might be of interest:
> 
> http://wrap.warwick.ac.uk/54707/1/WRAP_Hart_S1446788712000146a.pdf
> 
> I haven't tried figuring it out or coding it yet.

Thanks!


-- 
Steven

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

#88830

On Sat, 11 Apr 2015 17:35:07 +1000, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> declaimed the following:

>On Sat, 11 Apr 2015 04:08 pm, Paul Rubin wrote:
>
>> 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):
>
>Nice for some who have fast machines, but on my old jalopy, your code takes
>110 seconds, more than five times slower than mine. It also returns the
>wrong result:
>
>[3, 3, 3, 3, 7, 19, 73, 87211, 262657, 1.4411518807585587e+17]
>
>Oops, you have a float in there, how did that happen?
>
	Off the top of my head -- I'd suspect an older version of Python that
promoted 2**111 to a double, rather than to a Long-Int.

>>> 2**111
2596148429267413814265248164610048L

(forcing float)
>>> 2.0**111
2.596148429267414e+33
>>> 
-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
    wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

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

#88832

Dennis Lee Bieber <wlfraed@ix.netcom.com> writes:
>>Oops, you have a float in there, how did that happen?
> 	Off the top of my head -- I'd suspect an older version of Python that
> promoted 2**111 to a double, rather than to a Long-Int.

No he's being a wise guy.  The /= returned a float result in Python 3
after the first factor was found.  I noticed the /= after posting, but I
figured the print statement would trigger a syntax error in Python 3.
Looks like he did a partial conversion.

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

#88829

On Fri, 10 Apr 2015 23:08:50 -0700, Paul Rubin <no.email@nospam.invalid>
declaimed the following:

>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):
>
	<snip>

>pythonw -u "junk.py"
[3, 3, 1777, 3331, 17539, 25781083, 107775231312019L]
3.55100011826
>Exit code: 0

Win7Pro-64, i7-3770 @ 3.40GHz; Python 2.7

-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
    wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

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

#88863

On 11/04/2015 03:04, Steven D'Aprano wrote:

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

I don'tknow how well it compares more generally but where large amounts
of memory are available a simple sieve works quite well. I have an
implementation available here (in Python 3):

http://ccgi.gladman.plus.com/wp/?page_id=1500

where:

>>> from number_theory import factors
>>> print(tuple(factor(2 ** 111 + 1)))
((3, 2), (1777, 1) , (3331, 1), (17539, 1), (25781083, 1),
(107775231312019, 1))

runs in less than 2 seconds on my laptop.

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

#88866

On Sun, 12 Apr 2015 07:34 pm, Brian Gladman wrote:

> On 11/04/2015 03:04, Steven D'Aprano wrote:
> 
>> 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/
> 
> I don'tknow how well it compares more generally but where large amounts
> of memory are available a simple sieve works quite well. I have an
> implementation available here (in Python 3):
> 
> http://ccgi.gladman.plus.com/wp/?page_id=1500

Um, "simple sieve"? You're using Miller-Rabin to check for candidate prime
factors. I don't think that counts as a simple sieve :-)



> where:
> 
>>>> from number_theory import factors
>>>> print(tuple(factor(2 ** 111 + 1)))
> ((3, 2), (1777, 1) , (3331, 1), (17539, 1), (25781083, 1),
> (107775231312019, 1))
> 
> runs in less than 2 seconds on my laptop.


Although it is not directly comparable to the sieve version I used above, on
my machine I get:

py> import number_theory
py> with Stopwatch():
...     list(number_theory.factors(2**111+1))
...
[3, 3, 1777, 3331, 17539, 25781083, 107775231312019]
time taken: 5.823970 seconds


so there is a quite good speedup available from using Miller-Rabin. But it's
not a simple sieve any more.

By the way, it is possible to get guaranteed deterministic
(non-probabilistic) results with Miller-Rabin, for small integers. By small
I mean less than 2**64. See my pyprimes for details.



-- 
Steven

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

#88868

Steven D'Aprano <steve+comp.lang.python@pearwood.info> writes:
> Um, "simple sieve"? You're using Miller-Rabin to check for candidate
> prime factors. I don't think that counts as a simple sieve :-)

How does Miller-Rabin help?  It has to cost more than trial division.

Meanwhile, trial division up to 100000 is almost instantaneous and gives
the factorization

  [3, 3, 1777, 3331, 17539, 2778562183799360736577L]

where the last factor is composite.

    def pollard(n):
        def g(x): return (x*x+1) % n
        x = y = 2
        while True:
            x,y = g(x), g(g(y))
            d = gcd(abs(x-y), n)
            if d != 1:
                return d

   print pollard(2778562183799360736577L)

finds the factor 25781083 almost instantly.  

Verifying that 25781083 and the remaining factor is prime, and patching
all the code together to factorize in one operation, is left as an
exercise ;-).

Note that the Pollard routine is not guaranteed to find a nontrivial
factor.  If it fails, try a starting value other than 2.  This is also
left as an exercise.

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

#88869

Paul Rubin <no.email@nospam.invalid> writes:
>            ...  d = gcd(abs(x-y), n) ...
>    print pollard(2778562183799360736577L)
> finds the factor 25781083 almost instantly.  
>

Whoops, you need this too:

    def gcd(x,y):
        while True:
            x,y = y,x%y
            if y==0: return x

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

#88873

On 12/04/2015 18:20, Paul Rubin wrote:
> Steven D'Aprano <steve+comp.lang.python@pearwood.info> writes:
>> Um, "simple sieve"? You're using Miller-Rabin to check for candidate
>> prime factors. I don't think that counts as a simple sieve :-)
> 
> How does Miller-Rabin help?  It has to cost more than trial division.

As we factor the number with increasing prime values from a simple
sieve, if the number remaining to be factored is still large it can then
be efficient to run a prime test to see if what remains is prime.

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

#88876

Brian Gladman <blindanagram@nowhere.net> writes:
> As we factor the number with increasing prime values from a simple
> sieve, if the number remaining to be factored is still large it can then
> be efficient to run a prime test to see if what remains is prime.

In the case of 2**111+1, the second-largest prime factor is larger than
the sqrt of the largest one.  Therefore, the obvious trial division
strategy should have stopped as soon as the second-largest factor was
found, since what remained had to be prime.  I agree that this logic
doesn't apply to something like the rho algorithm, where you get a
factor that might not be the smallest one.

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

#88872

On 12/04/2015 15:29, Steven D'Aprano wrote:

>> I don'tknow how well it compares more generally but where large amounts
>> of memory are available a simple sieve works quite well. I have an
>> implementation available here (in Python 3):
>>
>> http://ccgi.gladman.plus.com/wp/?page_id=1500
> 
> Um, "simple sieve"? You're using Miller-Rabin to check for candidate prime
> factors. I don't think that counts as a simple sieve :-)
> 
What I meant here is that the underlying sieve on which factoring
depends - Primes() - is a simple one.  I'm sorry that I didn't make this
clearer.  I agree, of course, that the factoring code itself is more
complex than others are experimenting with but I am using it in
situations where I want it to work reasonbly well for quite large
numbers.

> so there is a quite good speedup available from using Miller-Rabin. But it's
> not a simple sieve any more.
> 
> By the way, it is possible to get guaranteed deterministic
> (non-probabilistic) results with Miller-Rabin, for small integers. By small
> I mean less than 2**64. See my pyprimes for details.

Yes, I have a more complex version but the simple one works well enough
in this context and finds very large primes that would otherwise stall
the code.

Thanks for taking a look.

   Brian

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

#88791

ravas <ravas@outlook.com> writes:
>     for divisor in range(1, end):
>         q, r = dm(dividend, divisor)
>         if r is 0:
>             rlist.append((divisor, q))

Use r == 0 instead of r is 0 there.  "r is 0" is object identity that
might happen to work but that's an implementation detail in the
interpreter.

> output: [(1, 999), (3, 333), (9, 111), (27, 37), (37, 27), (111, 9), (333, 3)]

> How do we describe this function? 

Listing the divisors of n

> Does it have an established name?

It's closely related to factoring.  The number of factors as a function
of n is called the Euler totient function, 

> What would you call it?

Enumerating the divisors.  Easier to do if you know the factors.

> Does 'Rosetta Code' have it or something that uses it?

Don't know.  Try their search function looking for factoring.

> Can it be written to be more efficient?

Yes, definitely.  Simplest is make a list of the factors and then
generate combinations of them.  Factor the number by trial division,
dividing out each factor as you find it, stopping when you get above the
square root of whatever is left.

There are fancier methods to factor even more efficiently and whole
books have been written about them, but the above is a start.

You might like www.projecteuler.net which has lots more of these
math-oriented exercises, though the later ones get pretty hard.

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

#88812

$ python2
Python 2.7.8 (default, Oct 20 2014, 15:05:19) 
[GCC 4.9.1] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> a = 256
>>> b = 256
>>> a is b
True
>>> a = 257
>>> b = 257
>>> a is b
False
>>> 

It's not safe to use 'is' to compare integers.

Use ==

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

#88833

Thank you all. I learned a lot.

[toc] | [prev] | [standalone]

Page 3 of 3 — ← Prev page 1 2 [3]

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

csiph-web