returning none when it should be returning a list?

**John Machin** · May 1 '06, 06:15 AM

Re: returning none when it should be returning a list?

On 1/05/2006 2:52 PM, randomtalk@gmai l.com wrote:[color=blue]
> hello, i have another problem i feel that i have to be missing
> something.. Basically, i've written a recursive function to find all
> the prime up to a number (lim).. here is the function:
>
> The function basically takes in a list of all the prime number found,
> it takes the next number to be tested for (next) and the limit it will
> go up to. It divide next by the list of previous prime numbers if next
> is not bigger than lim, count up all the times where it's not evenly
> divdided, if the result is equal the length of prime number, then we
> have another prime number, lather rinse and repeat :)
>
> def findPrime(seed, next, lim):
> print("seed: " + str(seed) + " next: " + str(next) + " lim: " +
> str(lim))
> print(seed)
> if(next >= lim):
> print(seed)
> return seed
> else:
> count = 0;
> for num in seed:
> modu = math.modf(float (next)/float(num));
> if(modu[0] > 0):
> count += 1
> if(count == len(seed)):
> seed.append(nex t)
> findPrime(seed, next+2, lim)
> else:
> findPrime(seed, next+2, lim)
>
> As you can probably see, i've printed the value of seed up until the
> point where i'm returning the seed, however, the function still returns
> None..
>[/color]

That's because it "falls off the end" of the function, which causes it
to return None. However that's not your only problem. Major other
problem is updating "seed" in situ.

Consider the following:

=== file: pseed.py ===
def findPrime(seed, next, lim):
print "seed: %r, next: %d, lim: %d" % (seed, next, lim)
if next >= lim:
return seed
for num in seed:
# modu = math.modf(float (next)/float(num));
# Try integer arithmetic:
if num > 2 and not (next % num):
# "next" is not a prime number
return findPrime(seed, next+2, lim)
return findPrime(seed + [next], next+2, lim)

# results:
"""[color=blue][color=green][color=darkred]
>>> pseed.findPrime ([1, 2], 3, 30)[/color][/color][/color]
seed: [1, 2], next: 3, lim: 30
seed: [1, 2, 3], next: 5, lim: 30
seed: [1, 2, 3, 5], next: 7, lim: 30
seed: [1, 2, 3, 5, 7], next: 9, lim: 30
seed: [1, 2, 3, 5, 7], next: 11, lim: 30
seed: [1, 2, 3, 5, 7, 11], next: 13, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13], next: 15, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13], next: 17, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17], next: 19, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19], next: 21, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19], next: 23, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23], next: 25, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23], next: 27, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23], next: 29, lim: 30
seed: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29], next: 31, lim: 30
[1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29][color=blue][color=green][color=darkred]
>>>[/color][/color][/color]
"""

# Doh! Looks like recursion not necessary. Google 'eliminate tail
recursion' :-)

def findPrime2(lim) :
seed = [1, 2]
for next in xrange(3, lim, 2):
prime = True
for num in seed:
if num > 2 and not (next % num):
prime = False
break
if prime:
seed.append(nex t)
return seed

# results:
"""[color=blue][color=green][color=darkred]
>>> pseed.findPrime 2(30)[/color][/color][/color]
[1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29][color=blue][color=green][color=darkred]
>>>[/color][/color][/color]
"""

**Edward Elliott** · May 1 '06, 06:25 AM

Re: returning none when it should be returning a list?

randomtalk@gmai l.com wrote:[color=blue]
> The function basically takes in a list of all the prime number found,
> it takes the next number to be tested for (next) and the limit it will
> go up to. It divide next by the list of previous prime numbers if next
> is not bigger than lim, count up all the times where it's not evenly
> divdided, if the result is equal the length of prime number, then we
> have another prime number, lather rinse and repeat :)[/color]

Your basic algorithm as described above sounds workable, but can be made
more efficient (I didn't look closely at your code for bugs). I won't even
go near the complicated number theory algorithms.

1. integer mod will be faster than floating point mod (unless you're getting
into numbers too large to store efficiently as ints, but you'll probably
run into other limitations before you get near that point in this code).

2. you can stop as soon as you find a zero remainder, no need to keep
testing the rest of the primes in the list.

3. you can stop testing numbers at the halfway point. there are no primes
smaller than 2, so no number x can have a factor larger than x/2.

4. in fact you can do even better. a simple proof by contradiction shows
that if primes 1..y don't divide x and y^2 > x then x must be prime. put
another way, once you test up to the square root of x, there's no point
continuing. if one factor were bigger than sqrt(x), the other would have
to be smaller than sqrt(x). but you've already tested the factors smaller
than sqrt(x), so there can't be any factors.

5. you can do better than checking every odd number (next+2) to find the
next prime, but I'm too tired to look into it right now. it may require
more complex machinery.

Locating primes is an interesting challenge because of the seemingly endless
grades of refinements over simple brute-force search. Like I said though,
if speed and size aren't concerns, your algorithm is fine.

**Dan Bishop** · May 1 '06, 09:15 AM

Re: returning none when it should be returning a list?

Edward Elliott wrote:
[in reponse to some prime-number code][color=blue]
> 5. you can do better than checking every odd number (next+2) to find the
> next prime, but I'm too tired to look into it right now. it may require
> more complex machinery.[/color]

You only need to check the prime numbers up to sqrt(n). If you're
calculating primes in sequential order, this is easy. Otherwise, you
can remove a third of the odd divisors by considering only odd numbers
of the form 6k±1 (because 6k±3 is divisible by 3).

def potential_prime s():
yield 2
yield 3
i = 6
while True:
yield i - 1
yield i + 1
i += 6

**Roy Smith** · May 1 '06, 12:35 PM

Re: returning none when it should be returning a list?

randomtalk@gmai l.com wrote:

Several people have already given you good answers as to why you're getting
None, and how to improve the algorithm you're using. I want to address
some stylistic questions.

First, is the
[color=blue]
> if(next >= lim):
> print(seed)
> return seed
> else:
> count = 0;
> [...][/color]

construct. You don't need the else part, since the if clause ends with a
return. You can just un-indent one stop and put everything that is now
inside the "else" at the same level as the "if". This makes your program
easier to read and understand. Your program isn't too bad because it's
only got about a dozen lines of code in the "else", and you only end up
about 4 indents deep. In larger programs, you can end up with 100's of
lines of code and 5, 6, or more indents. Then it's a nightmare to
understand.

The other sylistic issue is this:
[color=blue]
> if(count == len(seed)):
> seed.append(nex t)
> findPrime(seed, next+2, lim)
> else:
> findPrime(seed, next+2, lim)[/color]

You've repeated the call to findPrime(). You refactor that out like:

if(count == len(seed)):
seed.append(nex t)
findPrime(seed, next+2, lim)

Three lines of code instead of five, and no repeated code. Easier to
understand.

**randomtalk@gmail.com** · May 1 '06, 02:37 PM

Re: returning none when it should be returning a list?

John Machin wrote:[color=blue]
>
> That's because it "falls off the end" of the function, which causes it
> to return None. However that's not your only problem. Major other
> problem is updating "seed" in situ.
>[/color]
I'm not sure what "falls off the end" of the function means, i searched
online, it seems to mean that the function has reached the end
prematurely and returned a default identifier to signal success or
not.. Can you please explain what that means?

Other than that, thanks alot for all those who posted! It's been very
educational!

**Fredrik Lundh** · May 1 '06, 03:25 PM

Re: returning none when it should be returning a list?

randomtalk@gmai l.com wrote:
[color=blue]
> John Machin wrote:[color=green]
> >
> > That's because it "falls off the end" of the function, which causes it
> > to return None. However that's not your only problem. Major other
> > problem is updating "seed" in situ.
> >[/color]
> I'm not sure what "falls off the end" of the function means, i searched
> online, it seems to mean that the function has reached the end
> prematurely and returned a default identifier to signal success or
> not.. Can you please explain what that means?[/color]

it means exactly what it says: that execution of the function body reaches
the end of the function without seeing an explicit "return" statement.

Python handles this by inserting an extra "return" statement at the end, to
make sure there's always something to return (a plain "return" returns None
to the caller).

</F>

**Dave Hughes** · May 1 '06, 07:45 PM

Re: returning none when it should be returning a list?

Edward Elliott wrote:
[color=blue]
> randomtalk@gmai l.com wrote:[color=green]
> > The function basically takes in a list of all the prime number
> > found, it takes the next number to be tested for (next) and the
> > limit it will go up to. It divide next by the list of previous
> > prime numbers if next is not bigger than lim, count up all the
> > times where it's not evenly divdided, if the result is equal the
> > length of prime number, then we have another prime number, lather
> > rinse and repeat :)[/color]
>
> Your basic algorithm as described above sounds workable, but can be
> made more efficient (I didn't look closely at your code for bugs). I
> won't even go near the complicated number theory algorithms.
>
> 1. integer mod will be faster than floating point mod (unless you're
> getting into numbers too large to store efficiently as ints, but
> you'll probably run into other limitations before you get near that
> point in this code).
>
> 2. you can stop as soon as you find a zero remainder, no need to keep
> testing the rest of the primes in the list.
>
> 3. you can stop testing numbers at the halfway point. there are no
> primes smaller than 2, so no number x can have a factor larger than
> x/2.
>
> 4. in fact you can do even better. a simple proof by contradiction
> shows that if primes 1..y don't divide x and y^2 > x then x must be
> prime. put another way, once you test up to the square root of x,
> there's no point continuing. if one factor were bigger than sqrt(x),
> the other would have to be smaller than sqrt(x). but you've already
> tested the factors smaller than sqrt(x), so there can't be any
> factors.[/color]

The Prime Number article[1] on Wikipedia has a nice little Python
snippet implementing this algorithm (more or less). See the Finding
Prime Numbers section.
[color=blue]
> 5. you can do better than checking every odd number (next+2) to find
> the next prime, but I'm too tired to look into it right now. it may
> require more complex machinery.
>
> Locating primes is an interesting challenge because of the seemingly
> endless grades of refinements over simple brute-force search. Like I
> said though, if speed and size aren't concerns, your algorithm is
> fine.[/color]

Further reading: the Sieve of Eratosthenes[2] is a relatively simple
and fun little algorithm to implement (also has a size issue in that it
requires a list of numbers from 2 up to the largest number you wish to
test for primality, and I don't think it's any faster than the
algorithm above). A modern refinement called the Sieve of Atkin[3] is
also interesting, a bit faster, although rather more complicated.

If you want to look further into the subject, see the Primality Test
article[4] on Wikipedia (mentions things like probabilistic testing,
the Miller-Rabin primality test, and such like).

[1] http://en.wikipedia.org/wiki/Prime_number
[2] http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
[3] http://en.wikipedia.org/wiki/Sieve_of_Atkin
[4] http://en.wikipedia.org/wiki/Primality_test

Dave.
--

**Christos Georgiou** · May 2 '06, 09:05 AM

Re: returning none when it should be returning a list?

On 1 May 2006 07:19:48 -0700, rumours say that randomtalk@gmai l.com might
have written:
[color=blue]
>I'm not sure what "falls off the end" of the function means, i searched
>online, it seems to mean that the function has reached the end
>prematurely and returned a default identifier to signal success or
>not.. Can you please explain what that means?[/color]

I think that you haven't grasped the fact that a chain of calls of a
recursive function needs a return for *every* invocation of the function
(but I could be wrong :)

Check the following function, analogous to your own:
[color=blue][color=green][color=darkred]
>>> def f(x):[/color][/color][/color]
if x > 4:
print " returning", x
return x
else:
print " start recursion"
f(x+1)
print " end recursion"

[color=blue][color=green][color=darkred]
>>> print f(0)[/color][/color][/color]
start recursion
start recursion
start recursion
start recursion
start recursion
returning 5
end recursion
end recursion
end recursion
end recursion
end recursion
None

Do you see why the function returns None?
--
TZOTZIOY, I speak England very best.
"Dear Paul,
please stop spamming us."
The Corinthians

**Iain King** · May 2 '06, 10:15 AM

Re: returning none when it should be returning a list?

John Machin wrote:[color=blue]
>
> # Doh! Looks like recursion not necessary. Google 'eliminate tail
> recursion' :-)
>[/color]

I did, and found this:

Proper tail recursion

http://www.biglist.com/lists/dssslist/archives/199907/msg00389.html

which explains that the Scheme compiler optimises (obvious) tail
recursion into iterative code. I'm wondering if the python compiler
does the same?

Iain

**Christos Georgiou** · May 2 '06, 10:35 AM

Re: returning none when it should be returning a list?

On 2 May 2006 03:03:45 -0700, rumours say that "Iain King"
<iainking@gmail .com> might have written:

[color=blue]
>John Machin wrote:[color=green]
>>
>> # Doh! Looks like recursion not necessary. Google 'eliminate tail
>> recursion' :-)[/color][/color]
[color=blue]
>
>I did, and found this:
>http://www.biglist.com/lists/dssslis.../msg00389.html
>which explains that the Scheme compiler optimises (obvious) tail
>recursion into iterative code. I'm wondering if the python compiler
>does the same?[/color]

No, it doesn't so far.

More info:

<URL:http://groups.google.c om/groups/search?q=group% 3Acomp.lang.pyt hon+tail+recurs ion+optimizatio n&qt_s=Search >
--
TZOTZIOY, I speak England very best.
"Dear Paul,
please stop spamming us."
The Corinthians

returning none when it should be returning a list?

returning none when it should be returning a list?

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment