In theory Miller-Rabin can give incorrect result, but the probability of that is lower than the probability of a cosmic ray particle impacting a circuit in your CPU and causing it to give a wrong answer.
I have some thoughts on solving this Quora Challenge which I will post in a bit. On Sun, Sep 17, 2017 at 11:34 AM, Erling Hellenäs <erl...@erlinghellenas.se> wrote: > "Currently, arguments larger than2^31are tested to be prime according to a > probabilistic algorithm (Miller-Rabin)" > http://www.jsoftware.com/docs/help804/dictionary/dpco.htm > Miller–Rabin primality test > https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test > This means that sometimes, for arguments larger than 2^31, 1 p: y will > give an incorrect result? > /Erling > > > On 2017-09-17 19:28, Erling Hellenäs wrote: > >> Strange things happen here. It works but give incorrect results. I just >> changed F to lower case to put it through my tests. Not sure what might >> happen here. I have J 8.04 on this machine. 64 bit. >> I never doubted that p: was good. I just thought that since it was a >> Quora challenge that using p: would not be a good idea, since the algorithm >> used in p: is not known to the audience. It also seemed like some kind of >> cheating, like using a subroutine someone else wrote to solve half the >> problem. >> Well, I also thought p: would have to generate the array of primes for >> each call, but it's obviously not the case. There is a formula which does >> the trick? Or a hash table of primes? >> >> thru=: <. + >:@>. i.@- <. >> >> biggap=: {~ 0 1 - [: (i. <./) 2 -/\ ] >> >> f=: [: thru/ 1 _1 + [: biggap <./ >. >./ <. thru&.(p:inv) >> >> s=: 10 f 100 >> >> s >> >> 20 21 22 >> >> >./90 91 92 93 94 95 96 = s >> >> |length error: scriptd >> >> | >./90 91 92 93 94 95 96 =s >> >> |[-5] j:\j64-803-user\projects\quoraraul.ijs >> >> inv >> >> ^:_1 >> >> >> Cheers, >> >> Erling >> >> On 2017-09-17 17:38, Raul Miller wrote: >> >>> Yes. :) >>> >>> When J provides a mechanism for something it is usually worth trying. >>> Sometimes you can write something faster, but usually J's approach >>> will be useful. >>> >>> For example, in this case, consider this approach: >>> >>> thru=: <. + >:@>. i.@- <. >>> biggap=: {~ 0 1 - [: (i. <./) 2 -/\ ] >>> F=: [: thru/ 1 _1 + [: biggap <./ >. >./ <. thru&.(p:inv) >>> >>> There will be cases where another approach could be more efficient, >>> but it performs reasonably well. >>> >>> Thanks, >>> >>> >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm >> > > > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
