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

#88909

Dave Angel <davea@davea.name> 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**11111 -1  ...
>>>> math.log2(x)
> 11111.0

Yes, exactly that.  Thus (not completely tested):
    
    def isqrt(x):
        def log2(x): return math.log(x,2)  # python 2 compatibility
        if x < 1e9: 
           return int(math.ceil(math.sqrt(x)))
	a,b = divmod(log2(x), 1.0)
	c = int(a/2) - 10
	d = (b/2 + a/2 - c + 0.001)
	# now c+d = log2(x)+0.001, c is an integer, and
        # d is a float between 10 and 11
	s = 2**c * int(math.ceil(2**d))
	return s

should return slightly above the integer square root of x.  This is just
off the top of my head and maybe it can be tweaked a bit.  Or maybe it's
stupid and there's an obvious better way to do it that I'm missing.

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

#88911

On 04/13/2015 01:25 AM, Paul Rubin wrote:
> Dave Angel <davea@davea.name> 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**11111 -1  ...
>>>>> math.log2(x)
>> 11111.0
>
> Yes, exactly that.

Well that value x has some 3300 digits, and I seem to recall that float 
only can handle 10**320 or so.  But if the point of all this is to 
decide when to stop dividing, I think our numbers here are somewhere 
beyond the heat death of the universe.

   Thus (not completely tested):
>
>      def isqrt(x):
>          def log2(x): return math.log(x,2)  # python 2 compatibility
>          if x < 1e9:

Now 10**9 is way below either limit of floating point.  So i still don't 
know which way you were figuring it.  Just off the top of my head, I 
think 10**18 is approx when integers don't get exact representation, and 
10**320 is where you can't represent numbers as floats at all.

>             return int(math.ceil(math.sqrt(x)))
> 	a,b = divmod(log2(x), 1.0)
> 	c = int(a/2) - 10
> 	d = (b/2 + a/2 - c + 0.001)
> 	# now c+d = log2(x)+0.001, c is an integer, and
>          # d is a float between 10 and 11
> 	s = 2**c * int(math.ceil(2**d))
> 	return s
>
> should return slightly above the integer square root of x.  This is just
> off the top of my head and maybe it can be tweaked a bit.  Or maybe it's
> stupid and there's an obvious better way to do it that I'm missing.
>

If you're willing to use the 10**320 or whatever it is for the limit, I 
don't see what's wrong with just doing floating point sqrt.  Who cares 
if it can be an exact int, since we're just using it to get an upper limit.

And I can't figure out your code at this hour of night, but it's much 
more complicated than Newton's method would be anyway.

-- 
DaveA

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

#88915

Dave Angel <davea@davea.name> 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 at this hour of night, but it's much
> more complicated than Newton's method would be anyway.

What I posted is just straightforward arithmetic.  I'd expect Newton's
method to be more complicated if you want to bound the error carefully
and make sure it is non-negative.  Maybe I'm wrong about that though.

Note my comment "d is between 10 and 11" is slightly inaccurate.  d can
in some cases be slightly above 11 but that is fine.

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

#88916

On Monday 13 April 2015 15:25, Paul Rubin wrote:

> Dave Angel <davea@davea.name> 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**11111 -1  ...
>>>>> math.log2(x)
>> 11111.0
> 
> Yes, exactly that.  Thus (not completely tested):
>     
>     def isqrt(x):
>         def log2(x): return math.log(x,2)  # python 2 compatibility
>         if x < 1e9:
>            return int(math.ceil(math.sqrt(x)))
> a,b = divmod(log2(x), 1.0)
> c = int(a/2) - 10
> d = (b/2 + a/2 - c + 0.001)
> # now c+d = log2(x)+0.001, c is an integer, and
>         # d is a float between 10 and 11
> s = 2**c * int(math.ceil(2**d))
> return s
> 
> should return slightly above the integer square root of x.  This is just
> off the top of my head and maybe it can be tweaked a bit.  Or maybe it's
> stupid and there's an obvious better way to do it that I'm missing.

Check the archives: I started a thread last November titled "Challenge: 
optimizing isqrt" which is relevant. Also:

http://code.activestate.com/recipes/577821-integer-square-root-function/



-- 
Steve

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

#88936

Steven D'Aprano <steve+comp.lang.python@pearwood.info> 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 sieve(ps):
        p = ps.__next__()
        yield p
        yield from sieve(a for a in ps if a % p != 0)

    primes = sieve(itertools.count(2))
    print(list(itertools.islice(primes,20)))

It's not that practical above a few hundred primes, probably.

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

#88937

On Tue, Apr 14, 2015 at 12:42 PM, Paul Rubin <no.email@nospam.invalid> 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)
>
>     primes = sieve(itertools.count(2))
>     print(list(itertools.islice(primes,20)))

Small point: Calling dunder methods is usually a bad idea, so I'd
change this to "p = next(ps)" instead. But yep, that works...
inefficiently, but it works.

ChrisA

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

#88938

Chris Angelico <rosuav@gmail.com> 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.

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

#88943

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 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)
> 
>     primes = sieve(itertools.count(2))
>     print(list(itertools.islice(primes,20)))
> 
> It's not that practical above a few hundred primes, probably.

Upto 490 its instantaneous
At 500 recursion stack overflows
[Yeah one can set the recursion limit]

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

#88954

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 than what
>> I posted.
>> 
>> 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)
>> 
>>     primes = sieve(itertools.count(2))
>>     print(list(itertools.islice(primes,20)))
>> 
>> It's not that practical above a few hundred primes, probably.
> 
> Upto 490 its instantaneous

Not really instantaneous.

py> with Stopwatch():
...     x = list(itertools.islice(sieve(itertools.count(2)), 499))
...
time taken: 0.086171 seconds
py> from pyprimes import primes
py> with Stopwatch():
...     y = list(itertools.islice(primes(), 499))
...
time taken: 0.002802 seconds
py> x == y
True


I have to admit, I expected it to be significantly slower than it actually
is. Just goes to show, I've been using Python for 15+ years and my
intuition as to what is fast and what is slow is still mediocre at best.

Any beginner who thinks they can optimize code without measuring it first is
deluding themselves.


-- 
Steven

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

#88957

On Tue, 14 Apr 2015 12:42 pm, Paul Rubin wrote:

> Steven D'Aprano <steve+comp.lang.python@pearwood.info> 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 sieve(ps):
>         p = ps.__next__()
>         yield p
>         yield from sieve(a for a in ps if a % p != 0)
> 
>     primes = sieve(itertools.count(2))
>     print(list(itertools.islice(primes,20)))
> 
> It's not that practical above a few hundred primes, probably.

Oh! I thought that looked familiar... that's a recursive version of David
Turner's implementation of Euler's sieve. It is very popular in Haskell
circles, usually written as:

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

According to O'Neill, it has asymptotic performance of O(N**2/(log N)**2),
which means that it will perform very poorly beyond a few hundred primes.

Here is an iterative version:

def turner():
    nums = itertools.count(2)
    while True:
        prime = next(nums)
        yield prime
        nums = filter(lambda v, p=prime: (v % p) != 0, nums)


On my computer, your recursive version is about 35% slower than the
iterative version over the first 499 primes.



-- 
Steven

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

#88974

Steven D'Aprano <steve+comp.lang.python@pearwood.info> 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 it to Python.
I probably saw it before though, so it looks like a case of
not-exactly-independent re-invention.

> 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 still hit the nesting limit about equally
soon, because of the nested filters.  I like the faster versions in the
O'Neill paper.

> On my computer, your recursive version is about 35% slower than the
> iterative version over the first 499 primes.

Interesting.  I wonder why it's slower.

A Hamming (or "5-smooth") number is a number with no prime factors
larger than 5.  So 20 (= 2*2*5) is a Hamming number but 21 (= 3*7) is
not.  The first few of them are:
  [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]

Here's an ugly computation of the millionth Hamming number, converted
from Haskell code that you've probably seen.  I'd be interested in
seeing a cleaner implementation.  

================================================================
import itertools, time

def merge(a0,b0):
    def advance(m): m[0] = next(m[1])
    a = [next(a0), a0]
    b = [next(b0), b0]
    while True:
        if a[0] == b[0]:
            yield a[0]
            advance(a)
            advance(b)
        elif a[0] < b[0]:
            yield a[0]
            advance(a)
        else:
            yield b[0]
            advance(b)

def hamming(n):
    hh = [1]
    def hmap(k):
        for i in itertools.count():
            yield k * hh[i]

    m = merge(hmap(2),merge(hmap(3), hmap(5)))
    for i in xrange(n):
        hh.append(next(m))
    return hh[-1]

# this takes about 2.4 seconds on my i5 laptop with python 2.7,
# about 2.8 sec with python 3.3.2

t0=time.time()
print (hamming(10**6-1))
print (time.time()-t0)
================================================================

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

#88981

On Tue, Apr 14, 2015 at 8:37 PM, Paul Rubin <no.email@nospam.invalid> wrote:
> Steven D'Aprano <steve+comp.lang.python@pearwood.info> 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 still hit the nesting limit about equally
> soon, because of the nested filters.  I like the faster versions in the
> O'Neill paper.

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.
You might eventually get a seg fault when the C stack space runs out,
however.

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

#88982

Ian Kelly <ian.g.kelly@gmail.com> 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(fuel):
	f = lambda x:x
	for i in range(fuel): f = lambda x,g=f: 1+g(x)
	return f

    >>> d(3)
    <function <lambda> at 0x1a3b9b0>
    >>> d(100)(0)
    100
    >>> d(1000)(0)

    Traceback (most recent call last):
      File "<pyshell#24>", line 1, in <module>
        d(1000)(0)
      File "<pyshell#20>", line 3, in <lambda>
        for i in range(fuel): f = lambda x,g=f: 1+g(x)
      File "<pyshell#20>", line 3, in <lambda>
      [ 1000's of lines snipped ]
    RuntimeError: maximum recursion depth exceeded
    >>> 

This happens in both 2.7 and 3.3.4.

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

#88983

On Wed, Apr 15, 2015 at 9:21 AM, Paul Rubin <no.email@nospam.invalid> wrote:
> Ian Kelly <ian.g.kelly@gmail.com> 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(fuel):
>         f = lambda x:x
>         for i in range(fuel): f = lambda x,g=f: 1+g(x)
>         return f
>
>     >>> d(3)
>     <function <lambda> at 0x1a3b9b0>
>     >>> d(100)(0)
>     100
>     >>> d(1000)(0)
>
>     Traceback (most recent call last):
>       File "<pyshell#24>", line 1, in <module>
>         d(1000)(0)
>       File "<pyshell#20>", line 3, in <lambda>
>         for i in range(fuel): f = lambda x,g=f: 1+g(x)
>       File "<pyshell#20>", line 3, in <lambda>
>       [ 1000's of lines snipped ]
>     RuntimeError: maximum recursion depth exceeded
>     >>>

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. Basically, yours has direct
recursion in the Python code, while Steven's does not. The only
recursion in Steven's code is inside of the filter built-in function,
very nicely masked :).

Running Steven's code for a while, on a 32-bit install of Python 3.4.2
on Win64, printing the results, eventually produces:
[A whole pile of primes snipped]
784489
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in turner
  File "<stdin>", line 6, in <lambda>
MemoryError: Stack overflow

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

#88987

Chris Kaynor <ckaynor@zindagigames.com> 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 has direct recursion in the Python code, while
> Steven's does not. 

I would have said: both have deeply nested function calls but no
recursion per se.

I did another test with Python 2.7.5 under Idle:

    from itertools import ifilter
    def f(xs): return ifilter(lambda x:True, xs)

    def t(n):
        xs = range(10)
        for i in xrange(n): xs = f(xs)
        print list(xs)

and it seemed to survive up to around 130k nested filters, with a
slightly non-deterministic limit: 130900 worked some of the time and
crashed some of the time.  Interesting.

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

#88988 — Searching the archives

Hi--

I'm new here.  How do you search the archives?

--Gil

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

#88989 — Installing Python

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

Hi--

I'm on MacOS 10.6.8, learning to use Amazon Web Services' Simple Storage Service's Command Line Interface (AWS S3 CLI).

They say in their documentation that their CLI needs Python version 2.7 or 3.4.  I checked in terminal:

$ python --version
Python 2.6.1

So I ran the python-2.7.9-macosx10.6.pkg downloaded from https://www.python.org/downloads/ and now...

$ python --version
Python 2.7.9
$ aws --version
aws-cli/1.7.22 Python/2.6.1 Darwin/10.8.0

...it seems to me that the AWS CLI thinks it is still using the old version.  

Will this cause problems later?  Can it be fixed?  

--Gil

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

#88990 — Re: Searching the archives

On 15/04/2015 19:47, Gil Dawson wrote:
> Hi--
>
> I'm new here.  How do you search the archives?
>
> --Gil
>

There's nothing builtin to mailman (v 2.x which we're using). You've got 
a few options:

* Use Google (or whatever engine) with site:, eg:

https://www.google.co.uk/search?q=site:mail.python.org/pipermail/python-list/+windows

* Use some other service like markmail:

http://markmail.org/search/?q=list%3Aorg.python.python-list+windows

* (As a last resort): 
https://groups.google.com/forum/#!forum/comp.lang.python

But, seriously, please don't post back through Google Groups: it messes 
up the formatting considerably and will generally annoy people.

TJG

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

#88996 — Re: Installing Python

In article <4048AD0C-A403-4141-AB8B-5884A008496A@GilDawson.com>,
 Gil Dawson <Gil@GilDawson.com> wrote:

> Hi--
> 
> I'm on MacOS 10.6.8, learning to use Amazon Web Services' Simple Storage 
> Service's Command Line Interface (AWS S3 CLI).
> 
> They say in their documentation that their CLI needs Python version 2.7 or 
> 3.4.  I checked in terminal:
> 
> $ python --version
> Python 2.6.1
> 
> So I ran the python-2.7.9-macosx10.6.pkg downloaded from 
> https://www.python.org/downloads/ and now...
> 
> $ python --version
> Python 2.7.9
> $ aws --version
> aws-cli/1.7.22 Python/2.6.1 Darwin/10.8.0
> 
> ...it seems to me that the AWS CLI thinks it is still using the old version.  
> 
> Will this cause problems later?  Can it be fixed?  

I don't have any personal experience using that package but, from the 
instructions I see on their website, if you followed their instructions 
to download and install pip, you've installed aws into the system Python 
(2.6) rather than your new Python 2.7.  As of 2.7.9, Pythons installed 
from python.org now include their own version of pip.  What you could 
try is the following:

1. Uninstall the 2.6 version of aws:

   sudo pip uninstall aws

2. Install aws with the 2.7 version of pip:

   python2.7 -m pip install aws

In the future, whenever something suggests using "pip" or "sudo pip", 
just use "python2.7 -m pip" instead to be (more) certain that you are 
installing to the Python instance you want.

-- 
 Ned Deily,
 nad@acm.org

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

#89006

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 "Sleight on Eratosthenes".
> 
> Oh cool, I wrote very similar Haskell code and converted it to Python.
> I probably saw it before though, so it looks like a case of
> not-exactly-independent re-invention.
> 
> > def turner():
> >     nums = itertools.count(2)
> >     while True:
> >         prime = next(nums)
> >         yield prime
> >         nums = filter(lambda v, p=prime: (v % p) != 0, nums)

Here's a massive parallel (and more massively inefficient)
Turner sieve as bash script

$ cat nos2

n=2
while true ; do
	echo $n
	n=$(($n + 1))
done

$ cat filt 
read x
while true ; do
    if [ $(($x % $1))  -ne 0 ] ; then
	echo $x
    fi
    read x
done


$ cat sieve
read x
echo $x
filt $x | sieve


Call as
nos2|sieve|less
For 1st ten primes

$ nos2|sieve |head
2
3
5
7
11
13
17
19
23
29

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

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

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

csiph-web