LinuxQuestions.org
Latest LQ Deal: Linux Power User Bundle
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 12-18-2004, 09:13 PM   #1
Chrax
Member
 
Registered: Apr 2004
Distribution: Dapper
Posts: 167

Rep: Reputation: 31
C Prime Generator


http://chrax.freezope.org/programs/c/prime.c

This is one of my first C projects. It is a prime number generator that can run indefinitely, and outputs to a log.
I've gotten it to a stable state, i.e. I haven't been able to crash it and it works beautifully.

What I'd like is for a more seasoned programmer to look over this and perhaps give some tips on improving it, such as more efficient coding practices, perhaps a better algorithm, or maybe more efficient libraries, such as for parsing command line arguments.

Note that in order to compile it you need to have the GMP library installed, and compile it with the gcc flag -lgmp.

Thanks for your time,
Chris

Last edited by Chrax; 12-18-2004 at 09:14 PM.
 
Old 12-18-2004, 10:12 PM   #2
leonscape
Senior Member
 
Registered: Aug 2003
Location: UK
Distribution: Debian SID / KDE 3.5
Posts: 2,313

Rep: Reputation: 47
I don't know if this will help you, but this is a function I use to check if a number is prime. Its very efficent, and quite diffrent from what your doing. Its a code snippet I have, but I can't remember now eactly where I got it from ( but it is from a PD source I'm sure. )

Code:
bool isPrime(long value)
{
   long j, r, rold, rnew;
   r = 0;
   rnew = 1;
   do
   {
      rold = r;
      r = rnew;
      rnew = ( r + ( value / r ) );
      rnew >>= 1;
   }
   while( rold != rnew );

   for (j = 2; ( j <= rnew ); ++j)
   {
      if ( value % j == 0 )
      return false;
   }
   return true;
}
Its been a while since I used C, so I wouldn't feel able to comment on the rest really.

Last edited by leonscape; 12-18-2004 at 10:14 PM.
 
Old 12-19-2004, 08:13 PM   #3
Chrax
Member
 
Registered: Apr 2004
Distribution: Dapper
Posts: 167

Original Poster
Rep: Reputation: 31
I've never seen this before. What does this mean?
Code:
rnew >>= 1;
 
Old 12-19-2004, 08:30 PM   #4
leonscape
Senior Member
 
Registered: Aug 2003
Location: UK
Distribution: Debian SID / KDE 3.5
Posts: 2,313

Rep: Reputation: 47
>> Is the right bit shift operator, on ints it basically divides a number by two for every shift you do. so

rnew = rnew >> 1;

Is a very fast way of dividing by two. Of course, it doesn't do 0.5 so if rnew = 9, after this operation it equals 4. >>= is short hand for the above.
 
Old 12-20-2004, 01:03 AM   #5
Chrax
Member
 
Registered: Apr 2004
Distribution: Dapper
Posts: 167

Original Poster
Rep: Reputation: 31
I see. That was a sqrt approximation algorithm.

Anyway, thanks. I tried out just checking through all numbers less than the sqrt, and it now goes considerably faster than just checking through my primes list. I suppose my earlier method was a holdover from when I wrote this in perl and used arrays. So now, instead of
Code:
prime = fopen("/asdf/primelog","r");
    while(gmp_fscanf(prime,"%Zd",&test) != EOF && mpz_cmp(test,root) <= 0 &&
          flag == 0){
      mpz_mod(mod,thisnum,test);
      if (mpz_cmp_si(mod,0) == 0)
	flag = 1;
    }
    fclose(prime);
I have
Code:
mpz_set_ui(test,3);
    while(mpz_cmp(test,root) <= 0 && flag ==0){
      mpz_mod(mod,thisnum,test);
      if(mpz_cmp_si(mod,0)==0)
	flag = 1;
      mpz_add_ui(test,test,2);
    }
I think I'd like to be able to use arrays, or at least toggle between using arrays and brute forcing, but I'd also like to use a minimal amount of memory, as there's no way this could hope to compete with the existing logs, and is really just a curiosity.

Last edited by Chrax; 12-20-2004 at 05:25 PM.
 
Old 12-20-2004, 02:16 PM   #6
rustynailz
Member
 
Registered: Jun 2004
Distribution: MDK 9.2/10.0, VectorLinux 4.0
Posts: 50

Rep: Reputation: 15
You should google Fermat's Little Theorem. Exhaustive searching is not the way to go about checking for primes - it's horribly inefficient.

FLT says that if p is a prime which does not divide a, then a^(p-1)=1 (mod p).

If you use FLT with 20 generators, the odds of a false positive are very small.
 
Old 12-20-2004, 05:26 PM   #7
Chrax
Member
 
Registered: Apr 2004
Distribution: Dapper
Posts: 167

Original Poster
Rep: Reputation: 31
From what I've read, that seems to get me various sequences, none of which will contain all primes. And it is not my goal to find a ton of primes really quickly. My goal is pretty much to have primes scroll across the left side of my desktop in order.
 
Old 12-20-2004, 05:47 PM   #8
rustynailz
Member
 
Registered: Jun 2004
Distribution: MDK 9.2/10.0, VectorLinux 4.0
Posts: 50

Rep: Reputation: 15
Yes, but you're still testing each number to see if it's prime.

It's far more efficient than a brute force algorithm, and works for most numbers save the odd strange one (look up Carmichael numbers to see what I mean).

Generating all of the primes between 1 and 1,000,000,000 would be much much faster using FLT. Your algorithm is an exponential time one - the FLT algorithm is somewhere between polynomial time and exponential time.

These three indian guys actually found a deterministic polynomial time algorithm to test primality. Check it out here:
http://www.cse.iitk.ac.in/news/primality.html
 
Old 12-21-2004, 01:56 PM   #9
aluser
Member
 
Registered: Mar 2004
Location: Massachusetts
Distribution: Debian
Posts: 557

Rep: Reputation: 42
How high do you mean to search for primes? You can store numbers up to about 18 quintillion in an unsigned long long, making GMP unnecessary for numbers lower than that.

If you don't mind using a bit of ram, the sieve of erasthones is supposed to be a reasonably fast, easy to write way to enumerate primes. link: http://www.math.utah.edu/~alfeld/Eratosthenes.html

If you're low on ram and swap space, you could mmap the array into a file or try to play games with throwing out or writing to disk parts of the array you're not using.
 
Old 12-23-2004, 01:02 AM   #10
Chrax
Member
 
Registered: Apr 2004
Distribution: Dapper
Posts: 167

Original Poster
Rep: Reputation: 31
Aluser, I'm not trying to find all of the primes in a certain range, I'm continuously expanding my list. So even if I had the RAM of Jesus, I couldn't very well use the sieve of Erasthones. Also, I realize that at this point (around 4B), the GMP library's not necessary. However, I don't want to have to rewrite my program once I add a few more decimal places on. I'd rather work on the fun bits than redoing the base program.

I think I've decided on not using arrays at all, simply because *eventually* I will be using up a fuck-ton of memory.

Rustynailz, thanks for that link. If I get around to it, I'll try to implement a more elegant primality test than I've got, but other things have come up, and this isn't a priority. But eventually (read: within the next semester) I'll play with that, and I'll update you on how it went.


By the way, today my log exceeded maximum file size, so I'm going to end up making lists of 100M primes in primelog.n . So this should be pretty neat.

My ultimate goal for this project is to be able to have a base log somewhere and be able to dole out processing cycles to people who have this program. So as long as I'm still in school, I should have a hall's worth of free processing devoted to making numbers fly along the left of my desktop.

Last edited by Chrax; 12-23-2004 at 01:05 AM.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
RSA prime numbers? tarballedtux Linux - Security 19 06-28-2008 06:12 PM
Thread joining and prime nos msriram_linux Programming 2 11-26-2004 05:54 AM
c++ prime numbers loop problem muddlnx Programming 6 08-31-2004 10:14 PM
Algo for Relatively prime No. LinuxTiro Programming 5 11-17-2003 09:02 PM
mersenne prime number zetsui Linux - Software 3 08-23-2003 01:23 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 09:08 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration