Prime Number Generators

The Partridge Family were neither partridges nor a family. Discuss.
User avatar
Zedtho
Posts: 189
Joined: February 14th, 2017, 7:32 pm

Prime Number Generators

Post by Zedtho » March 24th, 2017, 7:11 am

Recently, I've been looking into Prime number generators, not because I want to generate the next biggest prime number (if I recall correctly, it's got about 22billion digits at the moment), but simply because I wanted to see how fast I could make it. Currently I'm just looking for ideas on how to speed it up.

There are a few methods of generating prime numbers:
1) Brute force, try to divide the number through every number before it.
(What I had been doing until I reached 1billion)
2) I thought maybe putting all the prime numbers I found into a vector, and whenever I check if a number is a prime number, I simply try to divide it by the prime numbers in the vector (since every non prime number is made out of multiplied prime numbers)

I could imagine this would be faster, but I don't know if the copying and taking from the vector would slow it down more than it would benefit it.
Also, to example 2) I could probably add a switch that stops looking for a divisor after it reaches half of the number that's being checked if it's a prime number, because all the following divisors won't be able to divide it regardless of if it is a prime number or not. But again, do these switches make it faster or will they ultimately slow down the program?

I should add I'm doing this after episode 15, which is why I'm currently outputting the numbers to the command prompt, and not to a file (which would be nicer)

One advantage that example 1 definitely has, is that I can start looking for numbers from f. ex one billion if I set it like that, but example 2 would give bad output since it won't have the needed prime numbers (2,3,5,7,9...) in its vector to try to divide the number by.

Regardless, thanks for taking the time to read this.

(Please also tell me if I should explain what I mean more)
Last edited by Zedtho on March 25th, 2017, 8:42 am, edited 1 time in total.

mmmmmm
Posts: 38
Joined: August 12th, 2013, 6:33 am

Re: Prime Number Generators

Post by mmmmmm » March 24th, 2017, 7:35 am

You only need to test up to sqrt(n) if n is your primenumber in case 1)

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Prime Number Generators

Post by chili » March 24th, 2017, 8:43 am

Yeah, divide only primes, divide only up to sqrt(n), only examine odd numbers. Definitely multithreading is a big win here too (hyperthreading probably not so much). Slightly tricky because results depend to a certain degree on previous results, but not too bad.

You can also get a big boost going AVX2, but since there is no integer divide instruction for AVX, you'll need to synthesize one yourself.

If the goal is just generate as many as possible as fast as possible, a sieve algorithm will give you the biggest win of all perhaps:

https://en.wikipedia.org/wiki/Generatin ... ime_sieves
Chili

User avatar
Zedtho
Posts: 189
Joined: February 14th, 2017, 7:32 pm

Re: Prime Number Generators

Post by Zedtho » March 24th, 2017, 12:03 pm

Edit: False information on my part in this post, unsigned long long ints hold up to trillions.


One problem I've gotten though, is the integer limit. I've heard of long long ints, but those only go till 8 8 billionish, 16 billion when unsigned. Are there any bigger ones supported by C++? Also, is the % operator worth it in this case, or is a user-defined operator more efficient.

Also, thanks a lot for the answers! I'm currently looking into sieves
Last edited by Zedtho on March 25th, 2017, 1:55 pm, edited 2 times in total.

cameron
Posts: 794
Joined: June 26th, 2012, 5:38 pm
Location: USA

Re: Prime Number Generators

Post by cameron » March 24th, 2017, 4:02 pm

Guess you could use unsigned long long or string for really large numbers.
Computer too slow? Consider running a VM on your toaster.

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Prime Number Generators

Post by chili » March 24th, 2017, 4:06 pm

There are libraries for arbitrary-precision arithmetic; I would grab one of them.

Shit gets real slow once you get into that tho.
Chili

User avatar
Zedtho
Posts: 189
Joined: February 14th, 2017, 7:32 pm

Re: Prime Number Generators

Post by Zedtho » March 24th, 2017, 5:50 pm

I read up on some stuff, and apparently they look at 2^n - 1 and check if that is a prime number or not, since there are special rules you can use on them.
Basically, they don't check every number, they just check for the biggest one out there which is easy to calculate. (Well, it still took about a month to find the biggest prime number we know of)

I guess I'll have to refocus and check what my goal is with this, to find the biggest prime number out there, but skip a lot of them inbetween, or to find all prime numbers in a given area.

Also, the obvious problem with integer sizes, which seems to be very hard to handle.

Apparently the most-used website for this stuff is called https://www.mersenne.org/
So, you can be the next person to find the biggest prime number! (If you download their program, and make your computer calculate it for 30 months)

albinopapa
Posts: 4373
Joined: February 28th, 2013, 3:23 am
Location: Oklahoma, United States

Re: Prime Number Generators

Post by albinopapa » March 25th, 2017, 8:39 am

Your wrong about the 4 billion limit of long long. long long is a 64 bit number 2^64, which is way more than 4 billion. The 4 billion-ish limit is for 32 bit long/int not long long.

Code: Select all

32bit long/int limit:                           2,147,483,647
32bit unsigned long/int limit:                  4,294,967,295 
64bit long long limit:              9,223,372,036,854,775,807
64bit unsigned long long limit is: 18,446,744,073,709,551,615
If you think paging some data from disk into RAM is slow, try paging it into a simian cerebrum over a pair of optical nerves. - gameprogrammingpatterns.com

User avatar
Zedtho
Posts: 189
Joined: February 14th, 2017, 7:32 pm

Re: Prime Number Generators

Post by Zedtho » March 25th, 2017, 8:42 am

Oh, thanks for noticing!
I'll correct that in the original post

User avatar
LuisR14
Posts: 1248
Joined: May 23rd, 2013, 3:52 pm
Location: USA
Contact:

Re: Prime Number Generators

Post by LuisR14 » March 25th, 2017, 8:49 am

yep, was gonna correct that, way lots, 18 trillions+ :P
always available, always on, about ~10 years c/c++, java[script], win32/directx api, [x]html/css/php/some asp/sql experience. (all self taught)
Knows English, Spanish and Japanese.
[url=irc://irc.freenode.net/#pchili]irc://irc.freenode.net/#pchili[/url] [url=irc://luisr14.no-ip.org/#pchili]alt[/url] -- join up if ever want real-time help or to just chat :mrgreen: --

Post Reply