5 Replies - 483 Views - Last Post: 01 January 2013 - 07:08 AM Rate Topic: -----

#1 BloodyInari  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 16-November 09

Memory Error in Primes

Posted 30 December 2012 - 12:29 AM

So I'm writing some code for a little prime number theory project of mine and I keep dealing with a memory error at some upper bound for some input value. I'm wondering if there might be a means to circumventing the problem and allowing the program to continue its computation, even if it takes more memory/time/etc. than what is normally allowed for?

My error:
>>> x.getDPF(987654321)

Traceback (most recent call last):
  File "<pyshell#6>", line 1, in <module>
    x.getDPF(987654321)
  File "C:\Python27\projects\primes.py", line 87, in getDPF
    if self.ifPrime(val) == 1:
  File "C:\Python27\projects\primes.py", line 42, in ifPrime
    for inc in range(1,val):
MemoryError



but is no problem if I do this:
>>> x.getDPF(123456789)
[[3, 2], [3607, 1], [3803, 1]]



The getGCD and ifPrime block (lines 31 to 45):
    def GCD(self, alpha, beta):
        if beta == 0:
            return alpha
        else:
            return self.GCD(beta, alpha % beta)

    def ifPrime(self, val):
    #checks if prime
        
        if val <= 1:
            return 0
        for inc in range(1,val):
            if self.GCD(val, inc) != 1:
                return 0
        return 1



and the getDPF or distinct prime factors block (lines 82 to 102):
    def getDPF(self, val):
    #gives distinct prime factors: i.e. 12546 -> [[2,1][3,2][17,1][41,1]]

        self.list_dist = self.clearList(self.list_dist)

        if self.ifPrime(val) == 1:
            return [[val,1]]
        else:
            for i in range(len(self.getPrimeFactor(val))):
                self.list_dist.append([0])
                self.list_dist[i][0] = self.list_pfactor[i]
                self.list_dist[i].append(1)

            for j in range(len(self.list_pfactor)):
                incr = 0
                while float(val)/self.list_pfactor[j] == val/self.list_pfactor[j]:
                    val /= self.list_pfactor[j]
                    incr += 1
                self.list_dist[j][1] = incr     
                
            return self.list_dist



Any useful tidbits?

This post has been edited by BloodyInari: 30 December 2012 - 12:33 AM


Is This A Good Question/Topic? 0
  • +

Replies To: Memory Error in Primes

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2102
  • View blog
  • Posts: 3,207
  • Joined: 21-June 11

Re: Memory Error in Primes

Posted 30 December 2012 - 06:44 AM

I don't think there's such a thing as a configurable memory limit in Python (unless you're using Jython). If you're getting a MemoryError, you probably exceed the actual amount of available memory - not some setting that can be changed.
Was This Post Helpful? 1
  • +
  • -

#3 BloodyInari  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 16-November 09

Re: Memory Error in Primes

Posted 30 December 2012 - 07:42 AM

View Postsepp2k, on 30 December 2012 - 07:44 AM, said:

I don't think there's such a thing as a configurable memory limit in Python (unless you're using Jython). If you're getting a MemoryError, you probably exceed the actual amount of available memory - not some setting that can be changed.


I suspected as much... <_</>
I assume one method would probably be along the lines of having a more efficient process that isn't nearly as "greedy" for memory? However, I'm dubious that I could get anything much more than a few hundred or thousand (or million maybe?) more cycles even if it was the best possibly written code I could think of. Considering the numbers I'm interested in are running at about 10^9 to 10^12 (when the program crashes) or so, its doubtful it would meet the level of standard.

Ok, even given that restriction, what would be a potential way(s) of dealing with this problem in such a fashion to meet my goal (if any at all...)?

This post has been edited by BloodyInari: 30 December 2012 - 04:04 PM

Was This Post Helpful? 0
  • +
  • -

#4 alexr1090  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 44
  • View blog
  • Posts: 124
  • Joined: 08-May 11

Re: Memory Error in Primes

Posted 01 January 2013 - 01:48 AM

oh this is a cool error lol it reminds me of myself trying to solve some project euler problems a while back. I'm thinking you're just trying to find primes, and if that's the case (tell me if it's not) then you're doing too much work. Here's a link explaining what you need to prove whether a number is prime. And if you really want to feel foolish for slaving over trying this for hours (as I did, believe me) have a look at the spoiler. Warning: Don't look at the spoiler if you don't want to see answers to project Euler!
Spoiler

Was This Post Helpful? 0
  • +
  • -

#5 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2102
  • View blog
  • Posts: 3,207
  • Joined: 21-June 11

Re: Memory Error in Primes

Posted 01 January 2013 - 06:24 AM

View Postalexr1090, on 01 January 2013 - 09:48 AM, said:

I'm thinking you're just trying to find primes


He's trying to find the distinct prime factors of a given number.

Quote

Here's a link explaining what you need to prove whether a number is prime.


From that link:

Quote

This is called the Sieve of Erasthenes.


No, it's not. And I'm not talking about the fact that they misspelled Eratosthenes. The Sieve of Eratosthenes works by crossing out multiples. It does not work by going back through the primes you've already found and checking whether any of them divide the current number.
Was This Post Helpful? 1
  • +
  • -

#6 BloodyInari  Icon User is offline

  • D.I.C Head

Reputation: 6
  • View blog
  • Posts: 106
  • Joined: 16-November 09

Re: Memory Error in Primes

Posted 01 January 2013 - 07:08 AM

View Postalexr1090, on 01 January 2013 - 02:48 AM, said:

oh this is a cool error lol it reminds me of myself trying to solve some project euler problems a while back. I'm thinking you're just trying to find primes, and if that's the case (tell me if it's not) then you're doing too much work. Here's a link explaining what you need to prove whether a number is prime. And if you really want to feel foolish for slaving over trying this for hours (as I did, believe me) have a look at the spoiler. Warning: Don't look at the spoiler if you don't want to see answers to project Euler!
Spoiler


View Postalexr1090, on 01 January 2013 - 02:48 AM, said:

I'm thinking you're just trying to find primes


actually, I've got the bit already covered for determining if a number "is prime", as shown here:
def GCD(self, alpha, beta):
    if beta == 0:
        return alpha
    else:
        return self.GCD(beta, alpha % beta)

def ifPrime(self, val):
#checks if prime
    
    if val <= 1:
        return 0
    for inc in range(1,val):
        if self.GCD(val, inc) != 1:
            return 0
    return 1


The GCD (greatest common denominator) method effectively goes exactly what you posted but works in my case, is still an applicable function for any composite numbers I may want to use as input for my other functions.

I was originally going to use this bit of code (that I later hashed out) for simple primality testing:
    def ifPrime(self, val):
        if val <= 1:
            return False
        # range starts with 2 and only needs to go up the squareroot of n
        for inc in range(1, int(val**0.5)+1):
            if val % inc == 0:
                return False
        return True


In fact, the for loop above is effectively exactly the same as the GCD() function and is almost exactly equivalent to what was described in your linked article.

View Postsepp2k, on 01 January 2013 - 07:24 AM, said:

View Postalexr1090, on 01 January 2013 - 09:48 AM, said:

I'm thinking you're just trying to find primes


He's trying to find the distinct prime factors of a given number.


^Absolutely correct. :yes:

You know, going back to the memory overflow problem, I was thinking that an iterated looping function that checks for the correct factors, clears all memory stored excepting the list of factors, and procedurally checks and clears until the process terminates.

I realized that when I do a function call for getDPF(), none of the memory stored from prior (now obsolete) function calls are expunged, therefore taking up otherwise available memory.

This post has been edited by BloodyInari: 01 January 2013 - 07:41 AM

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1