Help with prime number code C++

[jonnin]

So that is pretty good then?
no, not really :)

understanding computer speed ... there are different ways to talk about it. Lets explore:
your code on my box took just under 4 min.
My code on my box with the new tweek took 8 seconds.
One way to look at it is, indeed, that your code examined 600 million things in 4 min, and some might say, that is a lot in a small amount of time, sure.
But another way to look at it is that 4*60 is 240 seconds. that is 30 times slower than what I did. Personally, I consider something that runs TWICE as fast to be a major improvement in a piece of code, and getting a 10X speed up is unheard of unless the original coder did something very wrong. I don't mean this to offend you, but just telling you how I look at code performance. I am usually trying to get 10 PERCENT increases in code and calling it good. That would mean your code would run in 10 seconds to my 8, for example, and I would be pleased by the improvement. If yours ran twice as slow, in 15 seconds or so, and I got it down to 8, I would be very, very happy and excited. Going from 240 to 8 ... would have me looking for the coder to have a little chat (not a mean one, but an educational one -- everyone makes mistakes and I am a nonstop bug factory some days).

Of course, if you just want the answer, and your code too 3 min and now you have that answer, improving it to get the same answer again is just wasting time. Sometimes, your first cut gets the answer and even if it is terrible, you are done and stop there. If the answer is the end goal, once you get it, you stop, and that means your code is 'fine' -- it did what you needed done. My above observations are about tuning code that runs over and over and may be dragging down a program making the users grumpy about its unnecessary slowness. If you can cut the time a user sits there being irritable at your program in half, that is a big win. And, as some wit once put it, time is money. If corporations had back all the payroll spent waiting on programs, they could all invest in a new building by now.

[markyrocks]

Its all good. I just figured that the code you posted literally takes forever to run on my machine ( not a dis on your code, I obviously have to figure out what is up with my computer) that the fact that I was able to get my code to complete in a reasonable amount of time that I'd be in the same ballpark. I don't claim to be a professional or anything. Just a amateur hobbyist. My setup clearly isn't giving me a good picture as to how fast anything is running. Just very odd. Maybe i have a virus, who knows. I remodel bathrooms for a living. I just got paid today for a very big job so pretty happy about that. $-)

edit. after i compile your code jonnin and use the optimizations etc it finishes in like 10 seconds.

[jonnin]

I am not really a pro anymore either. Glad you got the optimize settings figured out. Your code is not so bad -- its just that this particular problem has been studied to death. "my" code is using what other people who worked the problem figured out...

[markyrocks]

I've been playing around with your posted code minus whatever tweeks you had suggested. I was able to get it to run in like 2 seconds using multithreading. (At least i believe it was running correctly). I may have had some kinda error. I had it doing 2 billion numbers in roughly 8 seconds. I was trying to cut even more time off of that but I think I got carried away and broke some stuff. You should give it a shot see what you can come up with.
For me it seemed like 4 threads was the sweet spot. After I went past that it just seemed like diminishing returns. I'll post what I got when I get it back to working right. I have to wrap this bathroom up real quick today so won't be able to mess with it until later.

[jonnin]

threading may be tricky as each iteration depends on the previous iteration to knock out some of the terms. If you have a thread removing every 6th value for 3's (9,15,21...) and another trying to remove the 7s they both touch 21 (and many other values..).

It would be an interesting study to thread it so it minimizes or eliminates any redundant work.
And yes, as I coded it, it does some redundant work single threaded too.

Like anything else, you can use a lookup table for a long, long time before you actually need to start finding values, if you really, really want speed. You can just shovel the answer into a table from a file and be done in a blink...

threads cost time to set up, and your cpu can only support so many (more than 2-3 per core will start to have context swap problems). So each machine will have a sweet spot for its hardware.

[markyrocks]

ok so i will admit that the last post i made is probably bs and I tried every way from here to sunday to fix the multi threading issue and it seemed like no matter what i did there i was running up against either a hardware limit or i was breaking something else whatever i'm glad i moved past that. I wrote hundreds of lines of code and approached the problem from every angle that i could possibly think of.... This is so sad, bc literally the following code that i've settled on figures out if a number is prime almost instantly and included is basically the highest prime number that i could find which is like 999 billiion. i just can't believe it.... I've tested it pretty thoroughly. Maybe i'm delusional. But as far as i can tell its accurate... I've even included a link to a website where i found prime numbers up to 999 billion.

int main()
{
	unsigned long long u = 999999999989; //  47055833459 5560695863 179424673  // http://compoasso.free.fr/primelistweb/page/prime/liste_online_en.php prime number list up to 1000 billion

		bool isPrime = true;
		for (size_t i = 3; i < floor(sqrt(u) + 1); i += 2) {
			if (u % i == 0) { isPrime = false; break; }
		}
		if (isPrime && u % 2 != 0 || u == 2) { cout << u << " is prime\n"; }
		else{ cout << u << " is not prime\n"; }
}

Id also like to say that the way I kinda came to this conclusion was that regarding the "sieve" I significantly sped that up bc I eliminated the second for loop and in a nutshell worked backwards via using.

for(size_t i = 3; i<sqrt(u); i+=2){
size_t backwards = u % i == 0 ? u : (u + i) - (u % i); 
p[backwards] = false;
p[backwards - i] = false;
if(!p[u]) {break;}
}

something like that. Then I realized that the bool vector wasn't letting me go past like 10 billion so I eliminated it completely bc after all the point of this is to figure out if 1 number is prime.

Edit obviously the last bit of code would go out of bounds if the vector wasn't bigger than i plus u etc

[dhayden]

literally the following code that i've settled on figures out if a number is prime almost instantly

You've discovered just how fast modern computers are. The loop runs half a million times. That's nothing when you can execute 4 BILLION instructions per second. On my computer, the program runs in 60ms.

You may find that it runs even faster if you precompute floor(sqrt(u)+1). it depends on whether the optimizer is smart enough to do that itself.

[jonnin]

vector bool solves it for a smaller problem cleanly. The sieve itself solves it for huge values but you need a better way to keep your answers. Possibly a sparse matrix type approach where the not-prime values are tossed (like the 0s in a sparse ). Its not the algorithm, its the way I coded it, because I assumed vector bool would do what you needed as it looked like homework.

[markyrocks]

I'm not the op. I just been playing around with it. @dhayden.... this is quite an improvement (for me anyways) bc the first version I wrote took 10s of minutes to find out if a prime number around 600 million. I'm happy about it, thats all I care about. Just purely a learning experience. @jonnin we were just talking about improvements and time etc. To me this is a big win. It solves the problem and like you said previously, minimizes the amount of time the user is waiting for an answer. If a vector was added for the purpose of storing answers it would probably add next to nothing in terms of time to save the answer after the fact. I realize that the above could be improved even further if there was a way to only have i increment to prime numbers only but it seems like any attempts to do that short of just having a file to stream in the numbers which up to 999 billion would be a pretty big file are pretty costly as far as time and memory. It works im satisfied, and as was stated previously gets it done far quicker than 80 trillion years or whatever lol.