Home Tutorials Forums Articles Blogs Movies Library Employment Press

 ActionScript.org Forums Determine is a number is prime or not
 Register FAQ Members List Social Groups Calendar Search Today's Posts Mark Forums Read

02-10-2010, 12:24 AM   #11
newblack
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!
__________________
i am gibreel farishta
general relativity
jellytanks alpha redux

 02-10-2010, 04:10 AM #12 lordofduct 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 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!
02-10-2010, 03:42 PM   #13
nikeman
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; 02-10-2010 at 04:15 PM. Reason: some more research

02-10-2010, 04:45 PM   #14
newblack
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 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

02-10-2010, 04:59 PM   #15
lordofduct
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 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.

02-10-2010, 05:08 PM   #16
nikeman
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 bit-problem for all I know.

 02-10-2010, 05:14 PM #17 lordofduct 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; 02-10-2010 at 05:22 PM.
 02-10-2010, 06:46 PM #18 lordofduct 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; 02-10-2010 at 07:30 PM.
 02-17-2010, 04:51 PM #19 nikeman Registered User   Join Date: Feb 2010 Posts: 7 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.

 Thread Tools Display Modes Rate This Thread Linear Mode Rate This Thread: 5 : Excellent 4 : Good 3 : Average 2 : Bad 1 : Terrible

 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 Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home ActionScript Forums Group     ActionScript 3.0     ActionScript 2.0     ActionScript 1.0 (and below)     Simple Stuff (Newbies) Flash General Questions     Flash 10 General Questions     Flash 9 General Questions     Flash 8 General Questions     Other Flash General Questions Flex     Flex 2, 3 & 4     Flex 1 Extensions and Plugins     Components     JSFL - Extending Flash Desktop, Mobile and non-browser Environments     AIR (Apollo)     FlashLite / Portable Devices Development     Projectors and CDs Supporting Technologies     HTML and JavaScript     haXe     Server-Side Scripting     Flash Remoting     Flash Media Server General     Best Practices     Gaming and Game Development     Animation and Effects     Flashants Support Forum Community Boards     General Chat     Just for Kicks Challenges     Detention Flash In Action     Site Check     Cool Sites     Widgets Decommissioned     Projects and Positions CMS Forums     Announcements Board     Content Postings / Updates     Product Review Requests     CMS Technical Questions     Process Questions     Collaboration & Suggested Articles

All times are GMT. The time now is 07:13 AM.

///