02102010, 12:24 AM

#11

dondeEstanMisPantalones?
Join Date: Nov 2005
Location: New York Proper
Posts: 1,355

Quote:
Originally Posted by lordofduct
check out this class:
@newblack  not to be rude, but I'd like to point out an issue with using Number (double floating point value), due to the significant value range being much smaller then the MAX value, you can get false positives sometimes for very large primes.

thanks, that's interesting! i dont see how that could be interpreted as rude in any respect, either... though i might consider it rude for you to point out how naive my algorithm is for not excluding evens!



02102010, 04:10 AM

#12

Senior Member
Join Date: Feb 2008
Location: West Palm Beach, FL
Posts: 3,872

oh that comment is more related to a thread I was recently in where some one got very offended when all I did was comment.
Anyways, I didn't fully read the entire thread here and most just took it for the 'primality' question and posted that.
@OP  check out this 2 part article here about Number vs int vs uint. It should shed nearly all the light you may want (probably more) about the issue you are having with MAX values:
part1: http://www.lordofduct.com/blog/?p=90
part2: http://www.lordofduct.com/blog/?p=101
although I only slightly touch on integer and unitinteger in it.
I've been meaning to write some articles about them as well... I actually started one a while back, but it started meandering a bit (more then I usually do) and I wanted to get together a bit more depth to it while not running around in circles. Furthermore I have been waiting on having the time and energy to sit down and outline integer arithmetic and how it all works inside the system.
I just don't know how to put it in words that work well. Maybe my Knuth books will help me find the words (been reading them on the toilet lately.... I sometimes forget to stop).
__________________
www.lordofduct.com  come read my blog!
If you want to know how to program, take a math class, take a lot of math classes!



02102010, 03:42 PM

#13

Registered User
Join Date: Feb 2010
Posts: 7

Thanks for the replies.
I have been testing out your script lordofduct, and I find that it reports a 16 digit prime I found on a website as false (not prime).
Since I didn't quite understand the script you made, (as I'm new to actionscript) I don't know why.
I have also come up with a new and better version of my first script, which is inspired by the input from the replies. This only check odd numbers except for the even number 2. I still don't know how to only make it only pick odd numbers that are also primes.
ActionScript Code:
function primTall (tall:Number):Boolean {
var teller:uint = 2;
var i:uint = 0
while (teller<=Math.floor(Math.sqrt(tall))) {
if (tall%teller == 0) {
i++
teller = tall;
}
else {
}
if(teller == 2) {
teller++;
}
else {
teller = teller + 2;
}
}
if (i == 0) {
return true;
}
else {
return false;
}
}
trace(primTall(1391750021955277)); //this is the prime number lordofduct's program reported as false
Quote:
What I find strange is that when I enter a 20 digit number that ends with 0, 2, 4, 6 or 8 it doesn't report false instantly. Instead it keeps going and times out (15 sec rule). This is weird seeing the first number it would check is 2, and since the 20 digit number ended with an even number, the result of the modulo should be 0.

I now have a theory of why it wont report a number like this
Code:
99907713720748054570
as a false prime instantly. Could it be because it exceeds the limit of 64 bits?
After some more testing, I have found that
Code:
6290696190220566015
is the largest possible int which flash is able to call false. After that, it just says "A script has executed for longer than the default timeout period". This number has 19 digits, but it is not the same as the number reported by wikipedia to be the largest integer in 64 bit which is
Code:
+9,223,372,036,854,775,807
As for newblack's code, it reported the number 25 as a prime number.
 nikeman
Last edited by nikeman; 02102010 at 04:15 PM.
Reason: some more research



02102010, 04:45 PM

#14

dondeEstanMisPantalones?
Join Date: Nov 2005
Location: New York Proper
Posts: 1,355

Quote:
Originally Posted by nikeman
As for newblack's code, it reported the number 25 as a prime number.

lol. yeah i shouldn't just throw shit up without really thinking about it or actually testing it (no more coding in the quickreply box). this should work better:
ActionScript Code:
function isPrime( candidate:Number ) : Boolean
{
var sqrtCandidate:Number = Math.round( Math.sqrt( candidate ) );
if( candidate % sqrtCandidate == 0 ) return false;
if( candidate % 2 == 0 ) return false;
for( var i:int = 3; i < sqrtCandidate; i += 2 )
{
if( candidate % i == 0 ) return false;
}
return true;
}
1 suuuuuuper bad inefficiency of your algorithm, nikeman, is that you're evaluating the square root of the candidate EVERY LOOP. square root is very expensive to calculate and there's no reason to do it more than once!



02102010, 04:59 PM

#15

Senior Member
Join Date: Feb 2008
Location: West Palm Beach, FL
Posts: 3,872

Quote:
Originally Posted by nikeman
Thanks for the replies.
I have been testing out your script lordofduct, and I find that it reports a 16 digit prime I found on a website as false (not prime).
Since I didn't quite understand the script you made, (as I'm new to actionscript) I don't know why.

As I said in my post:

Personally I used integer only because I figured if you really needed to know the primality of very large values (greater then 2^31  1), then you probably don't want to use flash to decide it considering that by our algorithm (we essentially use the same algorithm) you'd potentially loop 23170+ times. (more so if you used your specific algorithm)

The largest int is 2147483647, far shorter then a "16 digit prime". It doesn't work for those because I use integer.
That's also what me follow up post is about... with the errors of floating point values (which should uncover some light). I can GUARANTEE there is NO algorithm that is useful enough in flash that will be accurate with 16 decimal digits. Floats themselves have ~16 decimal digits of significance... that leaves room for TONS of error.
you really should read my article about floats... they ARE NOT 64bit integers (longs).
part1: http://www.lordofduct.com/blog/?p=90
part2: http://www.lordofduct.com/blog/?p=101
The fact your algorithm found your 16 digit prime to be prime is purely coincidental.
If you wanted to accurately discover if larger values are prime I'd advise 2 things:
use binomial coefficients OR my algorithm for speed
do it in a language that supports 64bit integers
__________________
www.lordofduct.com  come read my blog!
If you want to know how to program, take a math class, take a lot of math classes!
Last edited by lordofduct; 02102010 at 05:05 PM.



02102010, 05:08 PM

#16

Registered User
Join Date: Feb 2010
Posts: 7

Quote:
Originally Posted by newblack
1 suuuuuuper bad inefficiency of your algorithm, nikeman, is that you're evaluating the square root of the candidate EVERY LOOP. square root is very expensive to calculate and there's no reason to do it more than once!

ah, lol
fixed it to look like this:
ActionScript Code:
var sqrtTall = Math.floor(Math.sqrt(tall))
while (teller<=sqrtTall)
Looks like your program is working fine, but it reports false on a 20 digit prime
Code:
99907713720748054573
However, this could just be the bitproblem for all I know.



02102010, 05:14 PM

#17

Senior Member
Join Date: Feb 2008
Location: West Palm Beach, FL
Posts: 3,872

There is NO algorithm in flash AS3 that is going to prove a 20 digit prime as being prime or not...
try this:
ActionScript Code:
trace( 99907713720748054573 );
I guarantee you'll get an output of something like:
99907713720748050000
(it may be a bit different, I can't test it right now, at work)
the accuracy you'll get:
int  31 binary digits of significance... or ~10 digits of significance (if less than 2^31)
uint  32 binary digits of significance... or ~10 digits of significance (if less than 2^32)
Number  53 implicit binary digits of significance... or ~16+/ 1 decimal digits of significance
anyways, the amount of time it would take to prove primality is easily approaching the flash timeout point. I don't know, why would you even need to know the primality of a value that large in flash??? In other settings I may understand it, but I would NEVER use flash for analytical purposes like that.
__________________
www.lordofduct.com  come read my blog!
If you want to know how to program, take a math class, take a lot of math classes!
Last edited by lordofduct; 02102010 at 05:22 PM.



02102010, 06:46 PM

#18

Senior Member
Join Date: Feb 2008
Location: West Palm Beach, FL
Posts: 3,872

here is a function giving the primality of values in the largest accurate range AS3 will allow
ActionScript Code:
static public function isDoublePrime( val:Number ):Boolean
{
//if value is out side of accurate range of a double, then throw error
if(val > 9007199254740992) throw new Error("com.lordofduct.utils::LoDMath  can not accurately predict primality of value greater then 2^53 : 9007199254740992.");
//if value is rational, not prime by definition
if(val % 1) return false;
//if value is less then 2, not prime by defintion
if(val < 2) return false;
//if value is even and not 2, not prime by defintion
if(!(val % 2) && val != 2) return false;
//now check if prime
for(var i:int = 3; i <= val / i; i += 2)
{
if(!(val % i)) return false;
}
return true;
}
note if value is greater than 9007199254740992 (2^53) then an error is thrown. There is no way to accurately predict the primality of a value greater than 9007199254740992 in AS3. Number has the longest sig value range (53 bits) and this is the largest possible whole value created using those 53 digits.
Proof, run this:
ActionScript Code:
trace(9007199254740992 + 1);
you will get: 9007199254740992
no change
and of course, updated:
http://code.google.com/p/lodgamebox/...til/LoDMath.as
see isDoublePrime( val:Number ):Boolean
__________________
www.lordofduct.com  come read my blog!
If you want to know how to program, take a math class, take a lot of math classes!
Last edited by lordofduct; 02102010 at 07:30 PM.



02172010, 04:51 PM

#19

Registered User
Join Date: Feb 2010
Posts: 7

thank you, this was helpful
I'm afraid I'm not familiar with all the mathterms you used in your indepth article in your blog, which means I didn't understand everything, but it was interesting to have a loow.



Thread Tools 

Display Modes 
Rate This Thread 
Linear Mode


Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off



All times are GMT. The time now is 06:27 PM.
///

