Primes and primality checking

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Primes and primality checking

Sannyasin Brahmanathaswami via use-livecode
Hey folks,

This guy over on stackoverflow.com<http://stackoverflow.com> is asking for help generating and testing very large prime numbers.
http://stackoverflow.com/questions/43600252/generate-and-check-the-primality-of-very-large-numbers-in-livecode

I came up with this:

on mouseUp
    local tNum
    put fld "testNum" into tNum
    put isPrime(tNum) into fld "report"
end mouseUp

function isPrime pNum
    if pNum <> 2 AND pNum mod 2 = 0 then
        return false
    end if
    repeat with x = 3 to sqrt(pNum) step 2
        if pNum mod x = 0 then
            return false
        end if
    end repeat
    return true
end isPrime


However, it doesn’t seem to be reliable for very large numbers (> 100 digits) as the fellow wants. My math skills are pretty creaky. Anybody want a crack at this? It’s a fun challenge, plus it can boost LC’s presence on stackoverflow.

Cheers,

Devin

Devin Asay
Director
Office of Digital Humanities
Brigham Young University

_______________________________________________
use-livecode mailing list
[hidden email]
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
Reply | Threaded
Open this post in threaded view
|

Re: Primes and primality checking

dunbarx
Devin.

i don't get an overflow error til 309 digits. Where did the guy set a limit?

Making some sort of composite gadget, like we played around with a while ago on the forum to allow long multiplications, additions, etc. without limit would be a general solution without, er, limit.

Maybe Hermann can step in?

But post your offering. As you say, it will firm LC within stack overflow.

Craig
Reply | Threaded
Open this post in threaded view
|

Re: Primes and primality checking

Sannyasin Brahmanathaswami via use-livecode
Long Math is a longstanding ACL contest theme, and I think we've talked
about it here, before, too, because every language runs into precision
issues - sooner or later you're going to run out of digits in the register.

So in LC
Put the value into a container
Write the math algorithms that does it the way you know how to do it when
you are doing it manually.  It's very straightforward.

On Tue, Apr 25, 2017 at 1:27 PM, dunbarx via use-livecode <
[hidden email]> wrote:

> Devin.
>
> i don't get an overflow error til 309 digits. Where did the guy set a
> limit?
>
> Making some sort of composite gadget, like we played around with a while
> ago
> on the forum to allow long multiplications, additions, etc. without limit
> would be a general solution without, er, limit.
>
> Maybe Hermann can step in?
>
> But post your offering. As you say, it will firm LC within stack overflow.
>
> Craig
>
>
>
> --
> View this message in context: http://runtime-revolution.
> 278305.n4.nabble.com/Primes-and-primality-checking-tp4714219p4714234.html
> Sent from the Revolution - User mailing list archive at Nabble.com.
>
> _______________________________________________
> use-livecode mailing list
> [hidden email]
> Please visit this url to subscribe, unsubscribe and manage your
> subscription preferences:
> http://lists.runrev.com/mailman/listinfo/use-livecode
>



--
On the first day, God created the heavens and the Earth
On the second day, God created the oceans.
On the third day, God put the animals on hold for a few hours,
   and did a little diving.
And God said, "This is good."
_______________________________________________
use-livecode mailing list
[hidden email]
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
Reply | Threaded
Open this post in threaded view
|

Re: Primes and primality checking

dunbarx
In reply to this post by dunbarx
A modification from the web, similar, adapted to LC:

on mouseUp
   local tNum
   put fld 2 into tNum
   put "" into fld 1
   put isPrime(tNum) into fld 1
end mouseUp

function isPrime pNum
   if pNum ≤ 1 then return false
   if pNum ≤ 3 then return true
   if pNum mod 2 = 0 or pNum mod 3 = 0 then return false
   repeat with y = 5 to  sqrt(pNum)
      if pNum mod y = 0 or pNum mod (y + 2) = 0 then return false
      else return true
   end repeat
end isPrime

Same overflow issue at 309 digits.

Craig
Reply | Threaded
Open this post in threaded view
|

Re: Primes and primality checking

Sannyasin Brahmanathaswami via use-livecode
In reply to this post by Sannyasin Brahmanathaswami via use-livecode
On 04/25/2017 11:15 AM, Mike Kerner via use-livecode wrote:
> Long Math is a longstanding ACL contest theme, and I think we've talked
> about it here, before, too, because every language runs into precision
> issues - sooner or later you're going to run out of digits in the register.

In addition, it's one of those interview coding tests you throw in to
see if someone checks their work.

--
  Mark Wieder
  [hidden email]

_______________________________________________
use-livecode mailing list
[hidden email]
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
Reply | Threaded
Open this post in threaded view
|

Re: Primes and primality checking

Sannyasin Brahmanathaswami via use-livecode
In reply to this post by Sannyasin Brahmanathaswami via use-livecode
On 2017-04-25 17:01, Devin Asay via use-livecode wrote:
> However, it doesn’t seem to be reliable for very large numbers (> 100
> digits) as the fellow wants. My math skills are pretty creaky. Anybody
> want a crack at this? It’s a fun challenge, plus it can boost LC’s
> presence on stackoverflow.

You can only represent integers up to around 2^53 without losing
precision (as they are represented using IEEE doubles) which means the
maximum number you can check for primality using this method is around
9007199254740992.

Warmest Regards,

Mark.

--
Mark Waddingham ~ [hidden email] ~ http://www.livecode.com/
LiveCode: Everyone can create apps

_______________________________________________
use-livecode mailing list
[hidden email]
Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode