Home Tutorials Forums Articles Blogs Movies Library Employment Press
Old 02-10-2010, 12:24 AM   #11
newblack
dondeEstanMisPantalones?
 
newblack's Avatar
 
Join Date: Nov 2005
Location: New York Proper
Posts: 1,355
Send a message via AIM to newblack
Default

Quote:
Originally Posted by lordofduct View Post
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!
__________________
i am gibreel farishta
general relativity
jellytanks alpha redux
newblack is offline   Reply With Quote
Old 02-10-2010, 04:10 AM   #12
lordofduct
Senior Member
 
lordofduct's Avatar
 
Join Date: Feb 2008
Location: West Palm Beach, FL
Posts: 3,872
Default

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 unit-integer 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!
lordofduct is offline   Reply With Quote
Old 02-10-2010, 03:42 PM   #13
nikeman
Registered User
 
Join Date: Feb 2010
Posts: 7
Default

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; 02-10-2010 at 04:15 PM. Reason: some more research
nikeman is offline   Reply With Quote
Old 02-10-2010, 04:45 PM   #14
newblack
dondeEstanMisPantalones?
 
newblack's Avatar
 
Join Date: Nov 2005
Location: New York Proper
Posts: 1,355
Send a message via AIM to newblack
Default

Quote:
Originally Posted by nikeman View Post
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 quick-reply 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!
__________________
i am gibreel farishta
general relativity
jellytanks alpha redux
newblack is offline   Reply With Quote
Old 02-10-2010, 04:59 PM   #15
lordofduct
Senior Member
 
lordofduct's Avatar
 
Join Date: Feb 2008
Location: West Palm Beach, FL
Posts: 3,872
Default

Quote:
Originally Posted by nikeman View Post
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 64-bit 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 64-bit 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; 02-10-2010 at 05:05 PM.
lordofduct is offline   Reply With Quote
Old 02-10-2010, 05:08 PM   #16
nikeman
Registered User
 
Join Date: Feb 2010
Posts: 7
Default

Quote:
Originally Posted by newblack View Post
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 bit-problem for all I know.
nikeman is offline   Reply With Quote
Old 02-10-2010, 05:14 PM   #17
lordofduct
Senior Member
 
lordofduct's Avatar
 
Join Date: Feb 2008
Location: West Palm Beach, FL
Posts: 3,872
Default

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; 02-10-2010 at 05:22 PM.
lordofduct is offline   Reply With Quote
Old 02-10-2010, 06:46 PM   #18
lordofduct
Senior Member
 
lordofduct's Avatar
 
Join Date: Feb 2008
Location: West Palm Beach, FL
Posts: 3,872
Default

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; 02-10-2010 at 07:30 PM.
lordofduct is offline   Reply With Quote
Old 02-17-2010, 04:51 PM   #19
nikeman
Registered User
 
Join Date: Feb 2010
Posts: 7
Default

thank you, this was helpful

I'm afraid I'm not familiar with all the math-terms you used in your in-depth article in your blog, which means I didn't understand everything, but it was interesting to have a loow.
nikeman is offline   Reply With Quote
Reply


Thread Tools
Display Modes Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT. The time now is 11:20 PM.

///
Follow actionscriptorg on Twitter

 


Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Ad Management plugin by RedTyger
Copyright 2000-2013 ActionScript.org. All Rights Reserved.
Your use of this site is subject to our Privacy Policy and Terms of Use.