ECPP is the best algorithm if you want proof of a correct result for any
large number? https://en.wikipedia.org/wiki/Elliptic_curve_primality
/Erling
Den 2017-09-17 kl. 22:30, skrev Roger Hui:
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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
