0
$\begingroup$

I've developed a code and method that works in tandem with an earlier prime number algorithm I developed here:

https://codereview.stackexchange.com/questions/54753/a-fast-approach-to-prime-number-sieving-non-threaded-array

I have used it to determine whether LARGE numbers are prime or not in a fast amount of time along with why its not prime (if it isn't).

I have found in less than three seconds that 192,841,749,213,451,283 is PRIME according to my methods - I am restricted due to Java array size and memory space to 18 significant digits right now.

How can I test whether my results are correct - despite lower numbers being all accurate? I can't find a resource online that will let me test these numbers, given time.

|cite|improve this question
$\endgroup$
  • $\begingroup$ My code is a mess by the way so don't expect it to be shared right now. $\endgroup$ – Alex Lieberman Aug 26 '14 at 22:43
  • $\begingroup$ I'm not sure why you said that you can't find online resources. It is relatively easy to find plenty. For example you can try alpertron.com.ar/ECM.HTM, which is not even using the fastest algorithm known but can already handle quite large numbers like 142343123413412341324134132431423412341443143243123413412341233. The author even provided his source code and explanation of the algorithm. Wolfram Alpha confirms that this number is prime. $\endgroup$ – user21820 Mar 13 '15 at 6:26
5
$\begingroup$

Your result is not correct, since $$ 192841749213451283=11\cdot883\cdot1300573\cdot15265567 $$

I used PARI/GP to check this. You may wish to download it (it's free) to check the numbers on your own, or use any of a number of free online solutions.

As a quick check, use your program to find the primes up to $2^n$ for small $n$ and XOR (^) the results. You should get

10 627
11 1084
12 2345
13 499
14 4115
15 9929
16 18275
17 72458
18 203653
19 67941
20 877734
21 59156
22 2750
23 3971644
24 1045936
25 6886568
26 11789200
27 37712294
28 133154824
29 496378615
30 52560007

and this should at least show that your program is generally working.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you. Completely overlooked a stupid feature. I will have to rework thanks. $\endgroup$ – Alex Lieberman Aug 26 '14 at 22:56
  • $\begingroup$ Its scope was restricted by the variable type so I wasn't testing all cases - hence the speed misconception. I was confused why it didn't find 11 as a factor. Believe it should work now, just way slower. $\endgroup$ – Alex Lieberman Aug 26 '14 at 23:01
  • $\begingroup$ I'm well aware my code works for general prime finding with speed and accuracy (4.5 seconds up to N = 1,000,000,000). I modified it to attack larger numbers than the array can hold and neglected to account for int conversion to long I believe. Although seeing how fast you responded I'm not so sure how fast my algorithm is anymore lol. $\endgroup$ – Alex Lieberman Aug 26 '14 at 23:03
  • $\begingroup$ @AlexLieberman: The first cut of a program won't usually be fast, and I have the advantage of working in a faster language, C. If you think your idea is worth pursuing then go for it. On the other hand 3 seconds is not fast for primality testing numbers of that size; gp takes 0.7 seconds to test the million largest 64-bit numbers (finding 22475 primes). $\endgroup$ – Charles Aug 26 '14 at 23:09
  • 1
    $\begingroup$ For numbers under 2^64, Pari/GP uses AES BPSW and has been verified correct. Above that, as Charles stated, ispseudoprime does BPSW while isprime will do an APRCL proof. There are programs that run 2x faster than gp for 64-bit numbers as well. It's definitely a fun area to work on. $\endgroup$ – DanaJ Aug 27 '14 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.