On Wednesday, April 15, 2015 at 8:07:31 AM UTC+5:30, Paul Rubin wrote:
> Steven D'Aprano writes:
> > primes = sieve [2..]
> > sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]
> > In her paper http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf, Melissa
> > O'Neill calls this the "Slei
Chris Kaynor writes:
> That code is substantially different that the code that Steven
> D'Aprano posted: Steven's uses filter to call the lambdas, while your
> calls the lambdas from another lambda.
I wouldn't have thought it made a difference, but apparently it does.
Thanks.
> Basically, yours
On Wed, Apr 15, 2015 at 9:21 AM, Paul Rubin wrote:
> Ian Kelly writes:
>> Nope. You do end up with a lot of nested filter objects, but there's
>> no recursion in the Python code, which means that you're not piling up
>> frame objects, and you'll never hit the interpreter's recursion limit.
>
> I
Ian Kelly writes:
> Nope. You do end up with a lot of nested filter objects, but there's
> no recursion in the Python code, which means that you're not piling up
> frame objects, and you'll never hit the interpreter's recursion limit.
I think you do get frame objects. A quick experiment:
def d
On Tue, Apr 14, 2015 at 8:37 PM, Paul Rubin wrote:
> Steven D'Aprano writes:
>> def turner():
>> nums = itertools.count(2)
>> while True:
>> prime = next(nums)
>> yield prime
>> nums = filter(lambda v, p=prime: (v % p) != 0, nums)
>
> This is nice, though it will s
Steven D'Aprano writes:
> primes = sieve [2..]
> sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]
> In her paper http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf, Melissa
> O'Neill calls this the "Sleight on Eratosthenes".
Oh cool, I wrote very similar Haskell code and converted
On Tue, 14 Apr 2015 12:42 pm, Paul Rubin wrote:
> Steven D'Aprano writes:
>> http://code.activestate.com/recipes/577821-integer-square-root-function/
>
> The methods there are more "mathematical" but probably slower than what
> I posted.
>
> Just for laughs, this prints the first 20 primes usin
On Tue, 14 Apr 2015 08:35 pm, Rustom Mody wrote:
> On Tuesday, April 14, 2015 at 8:12:17 AM UTC+5:30, Paul Rubin wrote:
>> Steven D'Aprano writes:
>> >
http://code.activestate.com/recipes/577821-integer-square-root-function/
>>
>> The methods there are more "mathematical" but probably slower tha
On Tuesday, April 14, 2015 at 8:12:17 AM UTC+5:30, Paul Rubin wrote:
> Steven D'Aprano writes:
> > http://code.activestate.com/recipes/577821-integer-square-root-function/
>
> The methods there are more "mathematical" but probably slower than what
> I posted.
>
> Just for laughs, this prints the
Chris Angelico writes:
> Small point: Calling dunder methods is usually a bad idea, so I'd
> change this to "p = next(ps)" instead.
Oh yes, I forgot about that. I'm used to ps.next() and was irritated to
find that it doesn't work in Python 3, so I did the ugly thing that was
closest. Thanks.
--
On Tue, Apr 14, 2015 at 12:42 PM, Paul Rubin wrote:
> Just for laughs, this prints the first 20 primes using Python 3's
> "yield from":
>
> import itertools
>
> def sieve(ps):
> p = ps.__next__()
> yield p
> yield from sieve(a for a in ps if a % p != 0)
>
> prim
Steven D'Aprano writes:
> http://code.activestate.com/recipes/577821-integer-square-root-function/
The methods there are more "mathematical" but probably slower than what
I posted.
Just for laughs, this prints the first 20 primes using Python 3's
"yield from":
import itertools
def sie
On Monday 13 April 2015 15:25, Paul Rubin wrote:
> Dave Angel writes:
>> But doesn't math.pow return a float?...
>> Or were you saying bignums bigger than a float can represent at all?
>> Like:
> x = 2**1 -1 ...
> math.log2(x)
>> 1.0
>
> Yes, exactly that. Thus (not completely
Dave Angel writes:
>> if x < 1e9:
> Now 10**9 is way below either limit of floating point.
The idea was just to get rid of the case where c (further down in the
code) ends up being a negative number. Floating point works fine for
numbers that small.
> And I can't figure out your code
On 04/13/2015 01:25 AM, Paul Rubin wrote:
Dave Angel writes:
But doesn't math.pow return a float?...
Or were you saying bignums bigger than a float can represent at all? Like:
x = 2**1 -1 ...
math.log2(x)
1.0
Yes, exactly that.
Well that value x has some 3300 digits, and I seem
Dave Angel writes:
> But doesn't math.pow return a float?...
> Or were you saying bignums bigger than a float can represent at all? Like:
x = 2**1 -1 ...
math.log2(x)
> 1.0
Yes, exactly that. Thus (not completely tested):
def isqrt(x):
def log2(x): return mat
On 04/12/2015 11:30 PM, Paul Rubin wrote:
Dave Angel 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
Dave Angel 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 ;-)
--
htt
On 04/12/2015 09:56 PM, Paul Rubin wrote:
Marko Rauhamaa 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
Marko Rauhamaa 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
Brian Gladman 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 lar
On 12/04/2015 18:20, Paul Rubin wrote:
> Steven D'Aprano 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 nu
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,
Paul Rubin 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
--
https://mail.pyth
Steven D'Aprano 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 10 is almost instantaneous and
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]
>>
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 di
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.
>
wolfram.hinde...@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!
T
On Sun, 12 Apr 2015 02:24 pm, Paul Rubin wrote:
> Steven D'Aprano 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 w
Steven D'Aprano 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
On Sun, 12 Apr 2015 02:31 am, Paul Rubin wrote:
> Steven D'Aprano 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 thei
On Sun, Apr 12, 2015 at 9:58 AM, Terry Reedy 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 implemen
On 4/11/2015 5:10 PM, Chris Angelico wrote:
On Sun, Apr 12, 2015 at 3:52 AM, Paul Rubin 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 Pyt
Am Samstag, 11. April 2015 09:14:50 UTC+2 schrieb Marko Rauhamaa:
> Paul Rubin :
>
> > This takes about 4 seconds on a Intel(R) Core(TM) i5-3230M CPU @ 2.60GHz
> > laptop (64 bit linux):
>
> Converted to Python3:
>
> #!/usr/
On Sun, Apr 12, 2015 at 3:52 AM, Paul Rubin 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
Marko Rauhamaa 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
Paul Rubin :
> Marko Rauhamaa 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 sti
Thank you all. I learned a lot.
--
https://mail.python.org/mailman/listinfo/python-list
Dennis Lee Bieber 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
Marko Rauhamaa 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 Pytho
Steven D'Aprano 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.
--
https://mail.python.org/mailman/listinfo/python-list
$ 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 ==
--
htt
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 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
On Sat, 11 Apr 2015 04:08 pm, Paul Rubin wrote:
> Steven D'Aprano 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
Paul Rubin :
> 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
Steven D'Aprano 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 bi
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
ar
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 99
ravas 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.
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
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))
-
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,
53 matches
Mail list logo
