We are about to switch to a new forum software. Until then we have removed the registration on this forum.
I'm wondering if anyone has used Processing to generate very large prime numbers at random (for use in encryption, or at least a creative nod thereto). I found a little info for Java, but it seems Processing lacks the libs to carry it out.
import java.math.BigInteger;
BigInteger definitePrime(int bits, Random rnd) {
BigInteger prime = new BigInteger("4");
while(!isPrime(prime)) prime = BigInteger.probablePrime(bits,rnd);
return prime;
}
It doesn't understand type Random nor the isPrime call. Thoughts?
Answers
here, lots of flaws, but maybe it helps...
see
http://www.tutorialspoint.com/java/math/biginteger_probableprime.htm
http://professorjava.weebly.com/isprime.html
main problem in my sketch is probably that I often use .intValue() ...
;-)
this puzzles me
(not just in chrisir's code - all the examples i found on the web also did it)
you don't have to check every number as the divider - if n % 4 = 0 then n % 2 would also have been 0, so you don't need to check i = 4. or any other multiple of 2. using i += 2 would halve the numbers you'd check (having made sure n % 2 != 0)
(in fact, you only have to check prime numbers as the divisors, 2, 3, 5, 7, 11 etc. and then only up to the sqrt of the number under test.)
Once I wrote a function like that with my father : P
http://forum.processing.org/one/topic/how-would-i-write-a-function-to-determine-whether-a-number-is-prime-s.html
Made some tweaks for the sake of speed: :ar!
P.S.: Oops! Little l8! @koogs was faster HEHE! But I guess mine is a bit speedier! O:-)
While I'm at it @koogs, lemme ask ya why don't you have an avatar yet?! :O)
@koogs: You would be correct on this matter. Though line 6 through 8 would be unnecessary. That is, if you actually trust your code. :P
Saying that, meaning that the JVM might screw with some math. But I trust Java way more than that.
@Chrisir: There's actually a way of not using intValue(), and no, it's not what you think. It actually involves doing the opposite of taking a square root.
Multiplying 2 numbers is a much cheaper operation than a square root. So instead of:
you can do:
So, in the end, having worked a lot with prime numbers, the most optimized method, if you're not checking millions of different numbers, for finding prime numbers would be:
Which determines the 18 digit prime number 981168724994134051 in 4.6 seconds. Fairly fast for such a large number.
Now, for actually generating prime numbers, you could use an actual prime number array generator.
If you are going to test more than a million different numbers for primality, then actually generating a test array once will be a big help. Cuts a lot of corners v.s. using the
isProbablePrime()
method. I won't explain why this is so, as there is quite a bit of logic that arises from other bits of logic, etc.Then, you could use the resulting array, and test numbers against it. Just iterate over elements, and check if the tested number is prime.
I recommend that you don't change the data type of the method above though. Your machine might not be able to handle the whole array, otherwise.
In the link _vk posted PhiLho mentioned the Sieve of Eratosthenes which I was about to suggest. The general idea is to avoid testing numbers that are divisible by something already tested (what koogs said).
Say you try val%2 == 0 and val is not divisible by 2. It doesn't make any sense to try val%4 == 0, val%6 == 0, val%8 == 0, etc. because val%2 == 0 already failed. Here is a GIF that shows the idea: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#mediaviewer/File:Sieve_of_Eratosthenes_animation.gif
without line 6 it doesn't check that num % 4 == 0 (or 6, or 8...)
the first bit checks it's not exactly 2 and the main loop starts from 3 and goes up 2 at a time.
--
be wary that the SoE requires storage, albeit one bit per integer. so it might not be suitable for really large prime numbers - 981168724994134051 bits is still a lot 8)
It's just that I don't see there being a time when adding 2 to an odd number will make it even.
I.e. 8001 + 2 will never be 8004.
So basically, 4, 6, 8, and all others will just be skipped automatically. 3+2 = 5, 5 + 2 = 7, and 7 + 2 = 9. And since we're starting with 3, everything deals with itself on its own.
try it!
this is chrisir's original post calling my isPrime2() instead of his original
it reports 4 as a prime, which it patently isn't.
(i think you are thinking that this is the code that is generating the numbers. it's not, it's the code that's checking whether the numbers are prime)
You would be right. :\">
If only I had actually tested my code above. Mine has the same mistake. :-\"
And it's not that I thought it was generating primes. But for some reason, my mind just swapped the two, or something. So yes. You indeed need that check. My mistake.
i've been profiling the above, just out of curiosity. and there's really not a lot in any of the optimisations, even 128 bit numbers are coming back in 10s of milliseconds or so. even my optimisation of skipping half the factors doesn't seem to make much difference. i think something else (creation of draw window? BigInteger.probablePrime?) is causing a lot of noise and making decent profiling difficult. i did notice this at higher bit rates though:
false, true, true, true...
same with:
(starts around 40 bits (1068714100087 for instance) and slows the whole thing down because it keeps rejecting good primes)
My isPrime() version uses
long
, which is 63 bits at most. Your BigInteger is 128, completely unreliable!In order to amend that, I've expanded my version to deal w/
int
,long
and BigInteger ranges: :-bdAlright, everyone. Try your hand at the method one of JavaScripter's calculators use:
It was originally intended to return the least prime factor of a number. I've even tested this method on my TI-83, and it still works very well.
Now, I've transformed that into what you see above.
Personally, I still have trouble believing that 7 + 30x (that expression alone) generates valid primes every time (I'd think that this is based on a modified version of "sexy primes").
Also, when you test this, I will warn you that you have to let the CPU warm up to have an equal comparison of this, and the methods above. It has achieved speeds up to 3.5x of my original code (on my workstation, at least).
Edit: Ah yes. Once again, I forget to actually check 2, 3, and 5. Fixed.
Adapted for my example too! :ar! Dunno if it's any faster though... :-@
Warning: Since my version is using
int
for the iterator, it doesn't work for 63-bitlong
values!Well, here's a bit of a test. An even match between the 2 algorithms.
Most of the the algorithms, excluding the one from JavaScripter, were for the most part the same, so I just took the most optimized one (feel free to replace it if you have a better one).
Here's the test code. I have a relatively high end computer, now, so isPrime() took 13.5 seconds to run, whereas isPrimeJS() to 6.7 seconds.
The Stopwatch class is there, because it times the algorithms in nanoseconds, rather than milliseconds. This helps get a more accurate reading.
Tell us what you get.
In order to properly warm-up, we gotta call the actual methods being tested! :-w
I've replaced both isPrime() & isPrimeJS() w/ my own versions.
I've only had to modify them to use a
long
iterator since9051643576320000001L
is a 63-bit value!If that was at most 62-bit, my unmodified
int
versions coulda been used instead! :-<Probably would net slightly better results methinks...
Indeed, isPrimeJS() is the clear winner. W/ my version slightly faster than the 1 you tested with! \m/
And my own modified isPrimeLong(), using
6
step iterator jumps is much faster than the 1 using2
only!P.S.: My isPrimeJS() when using
|
rather than||
in the chained check expression is a few millis faster! :PHowever, it's a tiny slower for the isPrimeLong()'s case! #-o
You guys are insane. Incredibly helpful, thank you!
Insane. In a good way. ;)
Glad to help. I'm sure others are too.
I've posted these algorithms in the Ruby's GitHub! Which coincidentally were trying to optimize their prime() implementation: https://github.com/ruby/ruby/pull/736 =:)