Velocity Reviews > returning none when it should be returning a list?

returning none when it should be returning a list?

randomtalk@gmail.com
Guest
Posts: n/a

 05-01-2006
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
Guest
Posts: n/a

 05-01-2006
On 30 Apr 2006 21:52:48 -0700, http://www.velocityreviews.com/forums/(E-Mail Removed) declaimed the
following in comp.lang.python:

> 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 Removed) (E-Mail Removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (E-Mail Removed))
HTTP://www.bestiaria.com/

John Machin
Guest
Posts: n/a

 05-01-2006
On 1/05/2006 2:52 PM, (E-Mail Removed) wrote:
> 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
Guest
Posts: n/a

 05-01-2006
(E-Mail Removed) wrote:
> 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
Guest
Posts: n/a

 05-01-2006
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
Guest
Posts: n/a

 05-01-2006
(E-Mail 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
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@gmail.com
Guest
Posts: n/a

 05-01-2006

John Machin wrote:
>
> 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
Guest
Posts: n/a

 05-01-2006
(E-Mail Removed) wrote:

> John Machin wrote:
> >
> > 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?

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
Guest
Posts: n/a

 05-01-2006
Edward Elliott wrote:

> (E-Mail Removed) wrote:
> > 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.

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
Guest
Posts: n/a

 05-02-2006
On 1 May 2006 07:19:48 -0700, rumours say that (E-Mail Removed) might
have written:

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

>>> def f(x):

if x > 4:
print " returning", x
return x
else:
print " start recursion"
f(x+1)
print " end recursion"

>>> print f(0)

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,
The Corinthians