Amazing prime! >^oo^<

Got a LiveCode personal license? Are you a beginner, hobbyist or educator that's new to LiveCode? This forum is the place to go for help getting started. Welcome!

Moderators: Klaus, FourthWorld, heatherlaine, kevinmiller

Post Reply
Mariasole
Posts: 214
Joined: Tue May 07, 2013 9:38 pm

Amazing prime! >^oo^<

Post by Mariasole » Thu Oct 18, 2018 4:53 pm

Hello to all the friends of the forum!

And of course also a special greeting to the very few girls :wink: who wandering through these posts! (but those that are there are really good! :D ).

I'm experimenting to figure out if a number belongs to the family of prime numbers. That's why the post is called "amazing prime"! 8)

In short, LiveCode brings me home, for free, (almost) all the prime numbers I want! :roll:
The problem is the speed ...


I found two scripts that tell me if a number is a prime number.

The first is this:

Code: Select all

on mouseUp
    ask ""
    put p(it) into field "a"
end mouseUp
function p n
    if n is 1 then return false
    repeat with i=2 to n-1
        if n mod i is  0 then return false
    end repeat
    return true
end p
source: https://bit.ly/2OzDQa4


The second is this:

Code: Select all

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 <> 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

source: https://bit.ly/2P5GvYt


Let's take this test with this proven prime number: 10456997

Both scripts give the same result: true!

The second script is much faster than the first!

Now, let's try a new number (this is also a proven prime number). It's a bit bigger!
9007199254740781

Both scripts give the same result: false! Why FALSE?

Using pen and paper in about two minutes I have tried that 9007199254740781 is a prime number !!! (I'm joking, obviously) :D :D :D

Actually I used this site which, in real time, with a script, (I believe in javascript.. or php?), immediately gave me the result!

https://primes.utm.edu/curios/includes/primetest.php

How is this possible?

Thanks for the help, your amazing help!

Mariasole
>^..^<
No input, no output. Man - Joe Strummer
Garbage in, garbage out (GIGO) - anonymous

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 5625
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

Re: Amazing prime! >^oo^<

Post by dunbarx » Thu Oct 18, 2018 7:26 pm

MariaSole.

LC is limited in its ability to properly handle large numbers, anything over about 17 decimal digits (or so)

That is why you get erroneous results if you try to multiply "123456789123" by "987654321987". This is a limitation not of LC per se, but of the computer.

As for speed, others may comment on what machines or algorithms are used by websites such as the one you mentioned. I made an anagram program a while back, and it works, but is not nearly as fast as online sites.

Craig Newman

jacque
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 4702
Joined: Sat Apr 08, 2006 8:31 pm
Location: Minneapolis MN
Contact:

Re: Amazing prime! >^oo^<

Post by jacque » Fri Oct 19, 2018 4:56 pm

Actually I used this site which, in real time, with a script, (I believe in javascript.. or php?), immediately gave me the result!

https://primes.utm.edu/curios/includes/primetest.php

How is this possible?
If I were doing a web site like that I'd store a list of thousands of prime numbers and just look to see if the user entry is in the list. That would be the fastest way.

-- one of the girls :)
Jacqueline Landman Gay | jacque at hyperactivesw dot com
HyperActive Software | http://www.hyperactivesw.com

bogs
Posts: 2382
Joined: Sat Feb 25, 2017 10:45 pm

Re: Amazing prime! >^oo^<

Post by bogs » Fri Oct 19, 2018 5:11 pm

jacque wrote:
Fri Oct 19, 2018 4:56 pm
If I were doing a web site like that I'd store a list of thousands of prime numbers and just look to see if the user entry is in the list.
And where might you get such a list I hear you ask? Well, someplace like this :D

--one of the bogs :twisted:
Image

[-hh]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 1812
Joined: Thu Feb 28, 2013 11:52 pm
Location: Göttingen, DE

Re: Amazing prime! >^oo^<

Post by [-hh] » Sat Oct 20, 2018 1:30 am

Hi girls and boys.

Whether a number is prime is, TMHO, of only secondary interest. At least a lookup in a list is really not a real problem for LiveCoders.

More interesting is which are the prime factors of all the numbers we can reach with LiveCode. (The primes have themselves as single factor, so you check the primality too with that more general approach).
This more general question can't you handle fast with a list.

Which numbers can we reach with the algorithm below?
I think 2^53-1 = 9007199254740991 = 6361*69431*20394401 is a limit,
or factorial(22) = 1124000727777607680000 = (2^19)*(3^9)*(5^4)*(7^3)*(11^2)*13*17*19.

That is, 2^53+1 isn't correctly factorized any more and factorial(23) isn't correctly factorized any more. I don't know why we can go that high with factorial, perhaps a LC team member can come in to that?

The script below does the factorization very fast (in LC 9.0.1 on a medium fast machine (2.5 GHz)).
The Mariasole example 9007199254740991 (=2^53-1) is here done in 15 millisecs.

[Edit. Sorry, I forgot in (1.)to change my testing variable "f" to "factors".]

1. The factorize script (determines prime factors only).

Code: Select all

-- the collector is the local variable factors
-- put this script into the button's script
function factorize N, p0
  if N mod 2 = 0 then -- collect (multiple) factor 2
    put 2 &"*"  after factors
    return factorize(N/2,3)
  else
    -- factors smaller than p0 are already tested,
    -- but p0 is possibly a multiple factor, so:
    repeat with x = p0 to sqrt(N) step 2
      if N mod x = 0 then
        put x &"*" after factors
        return factorize(N/x,x)
      end if
    end repeat
  end if
  if N > 1 then
    put N after factors
    return 42 -- a joke as it doesn't matter, factors collects
  end if
end factorize
2. The button script.

Code: Select all

local factors

on mouseUp
  put the millisecs into m1
  set cursor to watch
  put fld "IN" into N
  put empty into factors
  put value(N) into N1 -- so we can input expressions
  put factorize(N1,3) into nirwana -- collects the factors
  put N & " = " & collectPowers(factors) &cr& N1 into fld "OUT"
  put (the millisecs - m1) & " ms" into fld "timing"
end mouseUp

-- count multiplicity of the prime factors
function collectPowers s
  set itemdel to "*"
  repeat for each item I in s
    add 1 to b[I]
  end repeat
  put the keys of b into kb
  sort kb numeric
  repeat for each line L in kb
    if b[L] is 1 then put L & "*" after t
    else put "(" & L &"^"& b[L] & ")*" after t
  end repeat
  return char 1 to -2 of t
end collectPowers
3. The factorial script.

Code: Select all

-- n is an integer >= 0
function factorial n
  if n <=  1 then return 1
  if n > 2 then
    subtract 1 from n
    return (n+1)*factorial(n)
  else return 2
end factorial
You can check your results here (Mathematica computes exactly also very big numbers).

For example:
http://www.wolframalpha.com/input/?i=Fa ... ger+2^53-1
Last edited by [-hh] on Sun Oct 21, 2018 12:03 am, edited 1 time in total.
shiftLock happens

bogs
Posts: 2382
Joined: Sat Feb 25, 2017 10:45 pm

Re: Amazing prime! >^oo^<

Post by bogs » Sat Oct 20, 2018 11:50 am

That is fascinating -hh!
Image

SparkOut
Posts: 1824
Joined: Sun Sep 23, 2007 4:58 pm

Re: Amazing prime! >^oo^<

Post by SparkOut » Sat Oct 20, 2018 6:44 pm

Not just fascinating, it's awesome (as usual to expect from [-hh] of course)

bogs
Posts: 2382
Joined: Sat Feb 25, 2017 10:45 pm

Re: Amazing prime! >^oo^<

Post by bogs » Sat Oct 20, 2018 9:49 pm

Oh yah? Upstage my 'fascinating' with "awesome" will you ?! Ok, you asked for it, I now say it is
SUPERCALIFRAGILISTICEXPEALIDOCIOUS!!

So nyah! :P
Image

Mariasole
Posts: 214
Joined: Tue May 07, 2013 9:38 pm

Re: Amazing prime! >^oo^<

Post by Mariasole » Mon Oct 22, 2018 4:58 pm

Thank you so much to everyone! Girls and boys!

I will proceed in order of appearance...

In fact, I study and meditate on your every help! The fact is that I'm not very fast, so I always need some time ...! :)
dunbarx wrote:
Thu Oct 18, 2018 7:26 pm
That is why you get erroneous results if you try to multiply "123456789123" by "987654321987". This is a limitation not of LC per se, but of the computer.
Thanks Craig. In fact, I had the doubt that it could depend on the computer (01101101 01100101 01101111 01110111 ecc.), and I studied this fact, even if I do not understand much. Let's say that things arrive "thanks to the smell", as they say in my part, that is "instinctively". But we'll talk more about this down the post!
jacque wrote:
Fri Oct 19, 2018 4:56 pm
If I were doing a web site like that I'd store a list of thousands of prime numbers and just look to see if the user entry is in the list. That would be the fastest way.
Dear Jacque! How nice to be in two girls in this forum! (Hey, is there any other girl in the forum?) :roll: .
Thank you for suggesting me the method of the list.
In fact, I just wanted to understand why the calculation did not work with the scripts I had found.

You must consider that my preparation in mathematics is really elementary, so, looking for a formula to get prime numbers quickly, I also came across some lists!

The most complete, among my research, is certainly this http://www.primos.mat.br/. Or rather, it's a collection of lists ... but it's huge !!!! So even if I wanted to, I could not use the method! (Thank you too, "one of the bogs" :D :D :D for the link !!!)

And now, from Göttingen, in all its splendor, he arrives, the wizard of the code, the acrobat of the factorial, the alpha male of the functions, the juggler of prime numbers, ladies and gentlemen it is for me a pleasure to welcome here among us -hh! (applause and ovations).

- hh thank you very much for your Lcode*! I'm really moved by the result, and I'm committing myself to study it. :D It is very elegant and beautiful. Plus I learned the existence of factorials. 8) I did not know about their existence. For me, completely ignorant, it was like discovering a new enigmatic game. Thank you so much - hh! You always teach me so many things!

As for the LC math limit, looking for something about the Craig's doubt and about factorials, I found this information on Wikipedia: Integer overflow. (https://bit.ly/2HgXdxB). (Oh my God, did I reinvent the wheel or hot water? :lol: ) Is it possible that LC suffers at some point of this problem right after the "-hh limit"? (The discovery of the limit, was made by -hh with his famous test "factorial(22)")

Will LC team members succeed in explaining why the "-hh limit"? Posterity will judge... :D

Grazie a tutti ragazze e ragazzi!
Mariasole
>^..^<


PS: Lcode (also lcode) is not a typographical error! It's a piece of code written live code! 8)
No input, no output. Man - Joe Strummer
Garbage in, garbage out (GIGO) - anonymous

[-hh]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 1812
Joined: Thu Feb 28, 2013 11:52 pm
Location: Göttingen, DE

Re: Amazing prime! >^oo^<

Post by [-hh] » Mon Oct 22, 2018 6:15 pm

Mariasole, la regina del forum belcanto :
Your posts are like an aria by Bellini. :wink:
shiftLock happens

Mariasole
Posts: 214
Joined: Tue May 07, 2013 9:38 pm

Re: Amazing prime! >^oo^<

Post by Mariasole » Tue Oct 23, 2018 9:10 am

Tempra o Diva,
Tempra tu de' cori ardenti,
Tempra ancor lo zelo audace,
Spargi in terra quella pace
Che regnar tu fai nel ciel.


smack! :wink:
No input, no output. Man - Joe Strummer
Garbage in, garbage out (GIGO) - anonymous

jacque
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 4702
Joined: Sat Apr 08, 2006 8:31 pm
Location: Minneapolis MN
Contact:

Re: Amazing prime! >^oo^<

Post by jacque » Tue Oct 23, 2018 9:59 pm

I know there are at least one or two other women on the forum but they don't appear very often.

On a computer, mathematical calculations are limited by the storage capactity in memory, as I understand it. The limitation is a physical one based on how high a computer can count before running out of room (this is probably a bad explanation but maybe gives an idea.)
Jacqueline Landman Gay | jacque at hyperactivesw dot com
HyperActive Software | http://www.hyperactivesw.com

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 5625
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

Re: Amazing prime! >^oo^<

Post by dunbarx » Tue Oct 23, 2018 11:18 pm

There are threads on this. The limiting issue is the 64 bits that LC uses to do math. From the thread;

http://forums.livecode.com/viewtopic.ph ... +for+large
LiveCode uses 64-bit IEEE 754 floating-point representation for numbers. This provides around 16 digits of decimal precision, which should be enough for most users' financial calculations.

You are cubing a 10-digit number, which produces a 30-digit number. This is more than can be represented by a 64-bit floating point number.

The precision of the calculation in this example is exactly as defined by the LiveCode language specification and the IEEE 754 standard. I am therefore closing this report as "not a bug".
Craig

Mariasole
Posts: 214
Joined: Tue May 07, 2013 9:38 pm

Re: Amazing prime! >^oo^<

Post by Mariasole » Fri Oct 26, 2018 5:49 pm

jacque wrote:
Tue Oct 23, 2018 9:59 pm
The limitation is a physical one based on how high a computer can count before running out of room (this is probably a bad explanation but maybe gives an idea.)
Now I understand better! Thanks Jacque! LC is pink! :D
dunbarx wrote:
Tue Oct 23, 2018 11:18 pm
The limiting issue is the 64 bits that LC uses to do math. From the thread;
Thanks Craig, I read the whole thread (it took a while!) ... I did not understand all, but I took notes for my new strange experiments! For example, using Mathematica with a shell ... But I do not know what Mathematica is !!! (but of course I can imagine it...!)

Thank you so much for the help you give me!

Mariasole
>^..^<
No input, no output. Man - Joe Strummer
Garbage in, garbage out (GIGO) - anonymous

Post Reply

Return to “Getting Started with LiveCode - Complete Beginners”