returning none when it should be returning a list?

[randomtalk]

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(next)
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..

 

[Dennis Lee Bieber]

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

No -- you aren't saving it...

saved = findPrime(...)

call "saved" whatever is needed for you usage.
--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

 

[John Machin]

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(next)
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..

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

>>> pseed.findPrime([1, 2], 3, 30)

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

# 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(next)
return seed

# results:
"""

>>> pseed.findPrime2(30) [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
>>>

"""

 

[Edward Elliott]

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

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]

Edward Elliott wrote:
[in reponse to some prime-number code]

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.

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_primes():
yield 2
yield 3
i = 6
while True:
yield i - 1
yield i + 1
i += 6

 

[Roy Smith]

(e-mail address removed) 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

if(next >= lim):
print(seed)
return seed
else:
count = 0;
[...]

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:

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

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

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

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

 

[randomtalk]

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.

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]

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?

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]

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.

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.

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.

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]

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?

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:
if x > 4:
print " returning", x
return x
else:
print " start recursion"
f(x+1)
print " end recursion"

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?

 

[Iain King]

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

I did, and found this:
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]

I did, and found this:
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?

No, it doesn't so far.

More info:

<URL:http://groups.google.com/groups/sea...ython+tail+recursion+optimization&qt_s=Search>