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

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

### Amazing prime! >^oo^<

Hello to all the friends of the forum!

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

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

In short, LiveCode brings me home, for free, (almost) all the prime numbers I want!
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
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)

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
Posts: 6179
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

### Re: Amazing prime! >^oo^<

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
Posts: 5115
Joined: Sat Apr 08, 2006 8:31 pm
Location: Minneapolis MN
Contact:

### Re: Amazing prime! >^oo^<

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: 3817
Joined: Sat Feb 25, 2017 10:45 pm

### Re: Amazing prime! >^oo^<

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

--one of the bogs

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

### Re: Amazing prime! >^oo^<

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: 3817
Joined: Sat Feb 25, 2017 10:45 pm

### Re: Amazing prime! >^oo^<

That is fascinating -hh!

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

### Re: Amazing prime! >^oo^<

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

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

### Re: Amazing prime! >^oo^<

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

So nyah!

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

### Re: Amazing prime! >^oo^<

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?) .
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" 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. It is very elegant and beautiful. Plus I learned the existence of factorials. 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? ) 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...

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!
No input, no output. Man - Joe Strummer
Garbage in, garbage out (GIGO) - anonymous

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

### Re: Amazing prime! >^oo^<

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

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

### Re: Amazing prime! >^oo^<

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!
No input, no output. Man - Joe Strummer
Garbage in, garbage out (GIGO) - anonymous

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

### Re: Amazing prime! >^oo^<

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
Posts: 6179
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

### Re: Amazing prime! >^oo^<

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: 218
Joined: Tue May 07, 2013 9:38 pm

### Re: Amazing prime! >^oo^<

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