Jump to content


Photo

Prime Finder Dll


  • Please log in to reply
11 replies to this topic

#1 tomster1996

tomster1996

    GMC Member

  • New Member
  • 312 posts

Posted 29 May 2010 - 11:19 AM

Here is my '...' Prime Finder DLL.

It has been optimised for finding thousands of prime numbers in seconds. In a console test it managed to find 300000 prime numbers in under an hour on my laptop! Useful for strong encryption keys and studying the mathematics of prime numbers.

It has 6 prime finding functions (not including the initiation function).
You can preload thousands of prime numbers into an array so if you want to retrieve a prime number later, it will be returned instantaniously.

The zip folder contains an example, the dll file, and the gml script file.

Posted Image

Updated:
- Example of saving primes to a file added.
- Prime checking technique is now much faster thanks to Maarten Baert

Feedback would be appreciated :)

Tom.

Edited by tomster1996, 31 May 2010 - 03:25 PM.

  • 0

#2 score_under

score_under

    Least kawaii

  • GMC Member
  • 1321 posts

Posted 29 May 2010 - 01:40 PM

Actually, that's painfully slow.
  • 0

Anti-Decompiler for GM6.1 to GM8.1.91! :GM8_new: [Main skin by Sindarin]
Discontinued.

decimal2.png
^ Signature image because it's been sorta empty since the old host died

If you need to contact me, I still get notification emails from PMs.


#3 tomster1996

tomster1996

    GMC Member

  • New Member
  • 312 posts

Posted 29 May 2010 - 01:53 PM

Actually, that's painfully slow.

Oh.
Well if you think about it when you get over the 50000th prime number, to find the next prime number you need to scan millions of times. This number, 1777777777, took 3 seconds to scan because it is prime, whereas this number, 1000000000, was instantaniously recognised as not prime.

At least it's quicker than this :) http://www.math.com/...rime-number.htm

Edited by tomster1996, 29 May 2010 - 02:01 PM.

  • 0

#4 score_under

score_under

    Least kawaii

  • GMC Member
  • 1321 posts

Posted 29 May 2010 - 11:06 PM

...Sorry, I thought you said it found prime numbers *up to* 300000 in an hour. I take that back.
(Though I bet you could speed the algorithm up by using int instead of double in the prime check routine. In C, "x%y" will find the remainder after dividing x by y (integers).)

Edited by score_under, 29 May 2010 - 11:14 PM.

  • 0

Anti-Decompiler for GM6.1 to GM8.1.91! :GM8_new: [Main skin by Sindarin]
Discontinued.

decimal2.png
^ Signature image because it's been sorta empty since the old host died

If you need to contact me, I still get notification emails from PMs.


#5 tomster1996

tomster1996

    GMC Member

  • New Member
  • 312 posts

Posted 30 May 2010 - 02:11 PM

...Sorry, I thought you said it found prime numbers *up to* 300000 in an hour. I take that back.
(Though I bet you could speed the algorithm up by using int instead of double in the prime check routine. In C, "x%y" will find the remainder after dividing x by y (integers).)


That's ok.

I am actually using integers to check if a number's a prime but I am simultaneously checking if it is divisble by 2 different numbers.
So if I was checking 48611, the function would check these numbers.
(3,24305)(5,24303)(7,24301)... and so on.
If the number is divisble, the function return not prime (false).
If the two numbers meet, the function returns the number as a prime (true).

In a console application using the same code as the dll, finding the 20,000th prime number (224737) takes under 10 seconds, however in the game maker application using the dll, it takes over 20 seconds to find the 20,000th prime number.
The code to find the 20,000th prime number is all in one dll function so I'm not sure why this is happening.
  • 0

#6 Maarten Baert

Maarten Baert

    GMC Member

  • GMC Member
  • 750 posts
  • Version:GM8.1

Posted 31 May 2010 - 11:42 AM

If you want to know whether N is prime, you don't have to check every number between 1 and N, just between 1 and sqrt(N) is enough.

bool is_prime(unsigned long a) {
	if(a<2) return false;
	if(a<4) return true;
	if(a%2==0) return false;
	unsigned long i = 3;
	while(i*i<=a) {
		if(a%i==0) return false;
		i += 2;
	}
	return true;
}
The fastest naive algorithm I can think of. It finds the 20,000th prime number (224737) instantly. It finds the 1,000,000th prime number (15485863) in 6 seconds. :)

And don't forget to turn optimisations on, it can make a big difference as the compiler will probably use registers to store i and a.

Edited by Maarten Baert, 31 May 2010 - 12:08 PM.

  • 0
Posted Image

#7 tomster1996

tomster1996

    GMC Member

  • New Member
  • 312 posts

Posted 31 May 2010 - 11:51 AM

If you want to know whether N is prime, you don't have to check every number between 1 and N, just between 1 and sqrt(N) is enough :).

bool is_prime(unsigned long a) {
	if(a<2) return false;
	if(a<4) return true;
	if(a%2==0) return false;
	unsigned long i = 3;
	while(i*i<=a) {
		if(a%i==0) return false;
		i += 2;
	}
	return true;
}
The fastest naive algorithm I can think of ::lmao::.

And don't forget to turn optimisations on, it can make a big difference as the compiler will probably use registers to store i and a.


Ok, I'll try that method, but I wasn't actually checking every number between 1 and N, I was checking every odd number between 3 and half of N.

There's a handwritten method to find primes where you draw out a table of numbers.
Firstly you take away the multiples of 2, then the multiples of 3, then 4, and so on until you are left with the prime numbers. I wonder if I could manipulate that into code.

EDIT:
Thanks a BILLION!!! Your method made finding 20,000 primes number take from 20 seconds to half a second!

I went from
if(i>(value/4)+1){
  return 1;
}
to
if(i*i>value){
  return 1;
}

Edited by tomster1996, 31 May 2010 - 12:08 PM.

  • 0

#8 Maarten Baert

Maarten Baert

    GMC Member

  • GMC Member
  • 750 posts
  • Version:GM8.1

Posted 31 May 2010 - 12:09 PM

Yes, you were right, now it takes just 2 seconds to find the 1,000,000th prime.
primes = new unsigned long[1000000];
	if(primes==NULL) {
		printf("memory allocation failed.\n");
		return 0;
	}
	
	printf("BEGIN\n");
	primes[0] = 2;
	primes[1] = 3;
	unsigned long a = 3;
	unsigned long *prime = primes+2;
	while(prime!=primes+1000000) {
		a += 2;
		unsigned long *p = primes;
		unsigned long i = *p;
		while(i*i<=a) {
			if(a%i==0) goto next;
			i = *(++p);
		}
		*(prime++) = a;
		next:;
	}
	printf("END, last prime = %lu\n", a);
	system("pause");
	
	delete[] primes;

EDIT: 0.5 seconds is reasonable, it takes 17.32ms on my computer.

Edited by Maarten Baert, 31 May 2010 - 12:18 PM.

  • 0
Posted Image

#9 tomster1996

tomster1996

    GMC Member

  • New Member
  • 312 posts

Posted 31 May 2010 - 12:24 PM

EDIT: 0.5 seconds is reasonable, it takes 17.32ms on my computer.


I'm on a laptop, you probably have more processing power than me.
But still those speeds are amazing!

EDIT:
just did a little more editing on the code, it does now take about 0.2 seconds to find the 20,000th prime

Edited by tomster1996, 31 May 2010 - 12:33 PM.

  • 0

#10 tie372

tie372

    Bassist of Death

  • New Member
  • 1038 posts
  • Version:Unknown

Posted 02 June 2010 - 06:12 PM

This is still going to be really slow (at least when numbers get to any decent size). Trial division is faster only up until ~12-13 digits (from my experience), which is hardly useful for cryptography (a 25 digit private key is hardly secure). You'd have to move onto Fermat's Little Theorem or (even better) Rabin Miller.

Fermat

-Take P, the number you're testing.
-Take a list of the first 10 prime numbers.
-For each small prime p, do (p^(P-1)) % P
-If the result is not one, then P is definitely not prime.
-Otherwise, P is "probably prime"


And Rabin Miller's a lot more complicated, but is more accurate and a lot faster than Fermat's little. Both of these require doing arbitrary precision arithmetic.

Edited by tie372, 02 June 2010 - 06:13 PM.

  • 0
Posted Image
Posted ImagePosted ImagePosted Image

#11 score_under

score_under

    Least kawaii

  • GMC Member
  • 1321 posts

Posted 02 June 2010 - 10:47 PM

if(i*i>value){
  return 1;
}

Do you realize that it's most likely faster to compute the value of (int)sqrt(value), save it in a variable, and do this?
if(i>sqrt_val){
  return 1;
}
This is because it's faster to just look up a number (that you calculated at the start of the function) than to perform a multiplication.

Edited by score_under, 02 June 2010 - 11:37 PM.

  • 0

Anti-Decompiler for GM6.1 to GM8.1.91! :GM8_new: [Main skin by Sindarin]
Discontinued.

decimal2.png
^ Signature image because it's been sorta empty since the old host died

If you need to contact me, I still get notification emails from PMs.


#12 tim.vangehugten

tim.vangehugten

    GMC Member

  • GMC Member
  • 72 posts

Posted 04 June 2010 - 08:44 PM

If you want to speed up a lot, use assembly language.
You might want to take a look at: http://www.bookgoldm...Blog.aspx?aid=2
and http://jweb.us/source_code/?p=225
  • 0