returning none when it should be returning a list?

Discussion in 'Python' started by randomtalk@gmail.com, May 1, 2006.

  1. Guest

    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..
     
    , May 1, 2006
    #1
    1. Advertising

  2. On 30 Apr 2006 21:52:48 -0700, 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

    HTTP://wlfraed.home.netcom.com/
    (Bestiaria Support Staff: )
    HTTP://www.bestiaria.com/
     
    Dennis Lee Bieber, May 1, 2006
    #2
    1. Advertising

  3. John Machin Guest

    On 1/05/2006 2:52 PM, 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]
    >>>

    """
     
    John Machin, May 1, 2006
    #3
  4. 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.
     
    Edward Elliott, May 1, 2006
    #4
  5. Dan Bishop Guest

    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
     
    Dan Bishop, May 1, 2006
    #5
  6. Roy Smith Guest

    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.
     
    Roy Smith, May 1, 2006
    #6
  7. Guest

    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!
     
    , May 1, 2006
    #7
  8. 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>
     
    Fredrik Lundh, May 1, 2006
    #8
  9. Dave Hughes Guest

    Edward Elliott wrote:

    > 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.
    --
     
    Dave Hughes, May 1, 2006
    #9
  10. On 1 May 2006 07:19:48 -0700, rumours say that 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,
    please stop spamming us."
    The Corinthians
     
    Christos Georgiou, May 2, 2006
    #10
  11. Iain King Guest

    John Machin wrote:
    >
    > # 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
     
    Iain King, May 2, 2006
    #11
  12. On 2 May 2006 03:03:45 -0700, rumours say that "Iain King"
    <> might have written:


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


    No, it doesn't so far.

    More info:

    <URL:http://groups.google.com/groups/search?q=group%3Acomp.lang.python+tail+recursion+optimization&qt_s=Search>
    --
    TZOTZIOY, I speak England very best.
    "Dear Paul,
    please stop spamming us."
    The Corinthians
     
    Christos Georgiou, May 2, 2006
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. David Freeman
    Replies:
    8
    Views:
    7,743
    tcena9
    Feb 16, 2011
  2. length power
    Replies:
    2
    Views:
    116
    Rustom Mody
    Apr 10, 2014
  3. Skip Montanaro
    Replies:
    0
    Views:
    85
    Skip Montanaro
    Apr 10, 2014
  4. Johannes Schneider

    Re: why i have the output of [None, None, None]

    Johannes Schneider, Apr 10, 2014, in forum: Python
    Replies:
    0
    Views:
    73
    Johannes Schneider
    Apr 10, 2014
  5. Terry Reedy
    Replies:
    0
    Views:
    84
    Terry Reedy
    Apr 10, 2014
Loading...

Share This Page