Wilson's Theorem Prime Number CLI Programs

[Sigurthr]

Hey everyone,
Thanks to c0ldshadow's recommendation on a good C++ IDE I was able to finish the project I was working on. I figure I might as well share it with you all.

SigurthrEnterprises Blogspot - Wilson's Theorem

 

[rhd]

Question -

Given that to test whether, say 999 is prime, you have to conduct 997 multiplication operations (for the factorial function), then do you actually save any computing resources over just brute forcing a division of 999 by each number from 0 to the square root of 999 and checking the remainder? Seems like the later would actually be more efficient.

 

[Sigurthr]

It depends on what factors (no pun intended) you're looking at for determining efficiency; time or power.

The modulo (%) function is very processor intensive, and tends to be avoided where one can, so general good coding practice is to call that operation as little as possible. Brute forcing via modulo would be very processor intensive, but probably a heck of a lot faster as the sqrt of a huge number is exponentially smaller than the huge number (man that sounds stupid to say/write).

The other issue is efficacy; Wilson's Theorem is accepted as a 100% accurate method of determining primes. It just isn't used because it would take a supercomputer months to do the computations for even "small" (in terms of where current mathematics is looking) primes. I don't know if there are any special cases where the method you mentioned doesn't work or not.

Anyway, on the subject of efficiency, if I were an advanced programmer I would find a way to save the values for the factorials [for the incremental program, not the checker] as the program is running, so that for example, 1-998 is already done when it goes to check 999. Currently it starts over because of the initialization argument of the inner nested for-loop in the factorial function.

Here's a screenshot of the code in case you're interested: (1366x768) http://i.imgur.com/6dBAj6i.png

edit: in posting that I realized I never corrected the welcome message for the ++ program. Such are the mistakes made when programming when tired, haha. I'll recompile and update the downloadable and links.

edit2: new version pushed and I didn't even have to change the links! I love the stuff Box.com has been implementing lately!

 

[clansley]

The modulo (%) function is very processor intensive, and tends to be avoided where one can, so general good coding practice is to call that operation as little as possible.

I'm guessing you and I work in very different areas. I build huge fault tolerant event driven distributed systems, and I for one couldn't care less how slow the modulo function is But I do understand the need to worry about these kind of things esp in embedded systems.

 

[Sigurthr]

I'm guessing you and I work in very different areas. I build huge fault tolerant event driven distributed systems, and I for one couldn't care less how slow the modulo function is But I do understand the need to worry about these kind of things esp in embedded systems.

I'm just an EE dabbling in C++, hehe. What little I know comes from my book on C++ by Bjarne Stoustrup. I certainly don't self identify as a programmer, haha.

 

[clansley]

I'm just an EE dabbling in C++, hehe. What little I know comes from my book on C++ by Bjarne Stoustrup. I certainly don't self identify as a programmer, haha.

Your skill set is much more applicable to the laser field than mine
You are a very smart guy to have fingers in so many pies (been reading your HV threads too); I always wanted to dabble in electronics, I even took a module at univ for cybernetic electronics and then found out that electronics wasn't as logical (to me) as I expected so I wimped out and only chose the logic gates etc rather than real electronics. Maybe there's still time [May be forced into it if I can't get somebody to build a non-PWM (user) variable laser!]

 

[Sigurthr]

If there's anything that I could commit to explicitly state that I believe in, it is that there is always time to learn something new IF you desire it strongly enough to keep yourself motivated and determined, and if the cards are not stacked against you to access the learning methods, materials, and time investment required.

IMO; unlike programming where there is a "hello world" version that distills everything down into an easily digested formatted version, electronics is a bit more organic in its nature. That does not mean that it is more difficult to learn or that it isn't a subject that everyone can understand. It just means that the patterns you look at to begin learning are not quite as palatable to the untrained eye. If you decide to give it a go, the most important thing you can do is be patient with yourself. Don't let the uni course color your taste of electronics, institutionalized EE instruction is often unbearably bad. It's kind of a running joke amongst the EE community that the entire degree experience is just to open the doors to the jobs where you do the majority of your learning. While not accurate by any means, it effectively illustrates how poor of a meter the classwork is. It's quite common to find graduate EEs who can't put together a LM317 driver circuit.

That being said, I extend the offer to you that I give to anyone on these forums; present yourself as a patient, determined student, who is willing to do their work, and I'll do my best to answer any questions you have via pm, anytime, with no limit to the depth of assistance. Others can well attest to this; I love helping a willing student.

Oh, and thanks for the kind words!

(Btw, building an analog modulated CW laser driver shouldn't be too much of a problem really. Size, heatsinking, current, and topology concerns are the real problem; if you just wanted a variable 0-2A linear driver for a lab module I could whip up a design in a few minutes. It's cramming it into a tiny host that is the problem (and I'd defer you to RHD's experienced hands there).