[Jprogramming] Quora Challenge

[Erling Hellenäs]

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 <erling at 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. at - <.
>>>
>>> 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. at - <.
>>>>      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