1 2 Previous Next 56 Replies Latest reply on May 15, 2007 1:23 PM by kglad

    Prime Calculator

    isaacewing
      Hello everyone,

      for the last week i have been trying to develop a prime number calculator. at first, it was a single input function that determined if it was prime or not. now it takes two numbers (min, max) but it takes to long and is not efficient enough to computer anything large within a certain range. (i.e. 0-15000). how would i make this algorithm significantly more efficient... without using the for loop to compare each number against a modulus check.

      ////////////////////////////////////////////////////////////////////
      code attached with screen print of flash file
      ////////////////////////////////////////////////////////////////////
      download zip version with all files:
      rar version: prime number test (flash cs3+as2)
      zip version: prime number test (flash cs3+as2)
      thank you for any help
      isaaac
        • 1. Re: Prime Calculator
          Rothrock Level 5
          Well you've got a couple of things going against you. Finding primes is hard and Flash is bad at math!

          There might be better algorithms out there so first be sure you do a good google search.

          By taking too long do you mean you get the "A script is causing Flash to run slow." message? If so, you can break up your for loop by using a setInterval to pass your prime_test loops chunks of 100 or 1000 or whatever seems to work best. If it gets through a chunk then it sets another short interval before starting the next. Be very careful when doing this because you can get into an endless loop. So be SURE to save every time before you test it.

          Other than that I can't really think of much you could do.
          • 2. Re: Prime Calculator
            NSurveyor Level 2
            Your primality test is quite slow, because it checks all the way up to the number itself until it finds a divisor. However, we only need to go up to sqrt(x), because if there were a prime factor,q > sqrt(x), then q/x < sqrt(x) and q/x would divide the number.

            I was confused as to why you have your program show the non-primes as opposed to the primes? You use "tavn" and "numv" in the final output... I wasn't sure if this was intended, so I left it alone.

            Also, there's no need to initialize variables as undefined, as they already will be. And, you can't delete variables after return, but they are local variables anyways so it doesn't matter.

            Using the attached code, I got all primes less than 20000 in 1.376 seconds.
            • 3. Re: Prime Calculator
              NSurveyor Level 2
              A much better way to find primes is to use a prime sieve, as opposed to checking if each number in a range is prime. One very simple and easy to implement would be the Sieve of Eratosthenes. Basically, you start with all numbers from 2 to m. You start with 2, and cross out all multiples of 2 (from 2*2). The next uncrossed out number (3) is your next prime, and then you cross out all multiples of 3 from (3*3 as 3*2 is already gone). The next uncrossed out number (5) is your next prime, and then you cross out all multiples of 5 (from 5*5 as 5*4, 5*3, 5*2 are all gone), etc. Check out http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes for more information.

              Using this method, I could calculate all primes less than 30000 in 0.994 seconds.
              • 4. Re: Prime Calculator
                Rothrock Level 5
                Hey NSurveyor – how is it going?

                That is really cool. I suspected there was a better way and know we know!
                • 5. Re: Prime Calculator
                  NSurveyor Level 2
                  Hey. I'm doing pretty good. I haven't been on the forums in quite awhile... busy with schoolwork and other things, but I'm trying to fit it back in. And I haven't done much flash work either... only interesting thing would be 100% AS Tetris - http://geocities.com/saif7463/tetris.swf . How're you?

                  Yup, the Sieve of Eratosthenes has always been fascinating to me. The steps are so simple and primitive, yet it produces the primes.
                  • 6. Prime Calculator
                    isaacewing Level 1
                    i have implemented the script for help although it still is not efficient enough... i am testing numbers starting from range 1,000,000. the end function when it is all finished will take a min and a max for input and go from min to the max but for now, it goes from 0 (i know its not a prime, but it is a start) to whatever is defined as the max number. i used the sieve of eratosthenes function and found it to be very good until i started testing it in the 1,200,000 range it gives me the 'error, not responding' message (i know it is from the timeout set by flash after 15(s). that is not the problem (sort of), i need it to be more efficient. i want to use numbers in the 64-bit range (it is for password and encryption generation). i was reading the http://en.wikipedia.org/wiki/Sieve_of_Atkin page and seems like that is the best algorithm to infuse into this project however i am not sure how to set that up. the pseudocode is a little to... disoriented... anyone... any suggestions... anything... please!!! thank you rothrock and nsurveyor for the help already, you have been very nice and i do appreciate it very much.

                    ALSO, i was reading a million... maybe even five million... different pages relating to the comparisons between sieve of eratosthene/atkin and came to the following conclusion. since they are based on wheel factorization why couldn't you somehow infiltrate their code with pi and simplify those together using the pi for accuracy and speed... does that make sense.
                    • 7. Re: Prime Calculator
                      Rothrock Level 5
                      I don't know what to tell you. When we get to math like this it is just at the end of my ability to grasp. Personally I'm working on doing some large matrix manipulations and that is taxing my brain so I don't have much left to offer for your issue. :)

                      In many ways I've managed to speed up what I'm doing, but Flash really isn't cut out for the maths. So at a point I just have to bite the bullet and spread out the calculations. When publishing for Flash 9 you can change the timeout from the default 15 seconds, but it seems to max out at 60? (Anybody else confirm that?)

                      Here are a couple of tricks I've found for my matrices:

                      Iterate backwards through loops, ie for(var i=0;i<256*256;i++) is slower than for (var i=256*256-1;i>=0;i--); I think there is even a slightly faster version of this, but I can't remember exactly how it is formatted.

                      Calculations are quicker on local variables.

                      Look for tricks. In my case I'm multiplying a 16 x 65536 matrix by its transpose. In that case the result will always be a symmetric matrix. So I only have to compute a bit over half and then just copy that to the other triangle.

                      I don't know if any of that helps you. Maybe we can keep this topic alive until kglad comes back from his cruise! (If you don't know, he is one of the most helpful folks here AND he happens to be a professional mathematician.)

                      PS: Are you using Flash CS3? When I publish Nsurveyor's code for AS3 it runs in about 120 milliseconds. (I removed the trace of the primes because that slows things down a bit.) If I change the publish settings to AS2 it takes about 1500 milliseconds. Wow! A whole order of magnitude is insane. I'm going to have to rework my matrix stuff for AS3 I think!
                      • 8. Re: Prime Calculator
                        isaacewing Level 1
                        yeah, i tested the prime number calc with 2 million and after the initial 60 seconds it starts to die. i tested it to 72 seconds and man it was sluggish. i was also using flash 9 pro.

                        do you think it would help if i assembled the data in a 2d array?

                        i have heard of presenting the for loop with the large number first so as the information and data list (array's) become filled with data, the actual data is significantly smaller keeping the speed at a fair equilibrium. also, doing a sort or reversing the matrix at the end is always an easy way of finishing all that off.

                        i didn't realize calculations were faster on local variables, it seems like that is common sense because they are local as oppose to somewhere else where they would have to be located each time they are needed.

                        what do you mean by matrix by its transpose?

                        well well well, kglad is a professional mathematician huh... wow haha that would help... we are two rookies to the game, im guessing your pretty good at a.s. in flash, im likewise but im not mathematician. did you know if they want to get their phd in math, they have to either prove or disprove something... oh my god, how hard would that be??? i don't think i could ever do that.i don't know him but i would like to meet him. do you know when he gets back or maybe when he left.

                        when you say you ran nsurvey's code ni as3 and it timed at 120 ms, what input value did you use (30k). yeah all this is in flash 3... download the zip or rar file i attached to this at the end of my origianal post... it has all the files in it.
                        • 9. Re: Prime Calculator
                          Rothrock Level 5
                          I don't know if matrix math will help you, it is just an example of some processor intensive stuff that I'm trying to do in Flash. So I'm just saying that be open to the idea that as you work with this you might discover some tricks specific to what you are doing that make the whole thing easier/faster.

                          As for the time test, yes, I just copied his Sieve code, removed the traces, and then tried it as a frame code. Make sure that even if you are using CS3, that you are publishing for the correct player and the correct flavor of AS.
                          • 10. Re: Prime Calculator
                            Rothrock Level 5
                            PS: Actually I delete the delete line and the line that traces the primes. Obviously I didn't delete the line that tells me the time!
                            • 11. Re: Prime Calculator
                              isaacewing Level 1
                              haha alright
                              • 12. Re: Prime Calculator
                                NSurveyor Level 2
                                Alright, I've converted the pseudo-code into ActionScript. Unfortunately, it is still slower, because of it's inefficient way of findind solutions to the diophantine quadratics.
                                • 13. Prime Calculator
                                  isaacewing Level 1
                                  I really like the way you setup your code... especially the way you setup the functions... naming them after the type they are, very user-friendly. Also, I especially like the timing function.

                                  You say the dilemma of efficiency still applies because of the diophantine quadratics problem... well, I was under the impression that the atkin equation was very efficient. You know, I was scouring the internet for additional topics like this one and there are a multitude of solutions to this equations but I am unable to convert those into actionscript. I really hate to sound like a rookie but man that kind of math is perplexing to me. if i wanted to test numbers in the 64-bit range with this equation (the equation being either one), what would you postulate the wait time would be to produce a solution. I tried to do that today but ran out of time. If i sent you links to the equations I found, could you tell me if they would be accurate or not... I hate to ask if you would be willing to convert those into actionscript as well so I will do that if you don't want (you have helped me more than enough).

                                  Finally, I was reading the wheel factorization method and thought about that all day today... my question is this: because of the way that works and the complexity of these equations, could they be simplified by applying pi to them... like below.

                                  //this link is for a picture of two different equations seperated by a light shade of color over
                                  //them. Like i said earlier, i do not understand these but i can postulate what they mean
                                  //and utilize google to help further my understanding (goddd, sometimes i wish i was
                                  //a mathematician!).
                                  // equations picture
                                  //this link is the actual page i found to eqations on and it has an explanation of what they
                                  //mean, how they are applied and so on.
                                  // prime number explanations
                                  //here is another interesting site with a much better breakdown of the information above
                                  //and is a little more simplistic
                                  // this is a lot easier to understand
                                  //this is really interesting and explains the zeta function and how to use it (don't really
                                  //know if it can be applied but it's cool
                                  // the zeta function
                                  //MAYBE THIS IS THE EQUATION WE ACTUALLY NEED TO SOLVE THIS... LET ME
                                  //KNOW IF YOU THINK SO...
                                  // hm function
                                  • 14. Re: Prime Calculator
                                    isaacewing Level 1
                                    where did everybody go?
                                    • 15. Re: Prime Calculator
                                      Rothrock Level 5
                                      Hi. I'm still here. Just don't know what else I can contribute.

                                      I don't know anything about wheel factorizations, so I don't know what to say.
                                      • 16. Re: Prime Calculator
                                        isaacewing Level 1
                                        hey do you know if that guy is back from vacation yet... also, i know your a matrix guru but i have another question about errors in flash... it is error 2025 from an a.s. 3 file and a flash cs3 file.
                                        • 17. Re: Prime Calculator
                                          Rothrock Level 5
                                          Well evidently, "The supplied DisplayObject must be a child of the caller." :) I have no idea. I'm finding AS quite difficult to work with.

                                          I haven't seen kglad posting here, so I don't know. I'm sure he will be around eventually.
                                          • 18. Re: Prime Calculator
                                            isaacewing Level 1
                                            HA, i know god i hate those kind of error messages, they give no feedback and its so hard to find out what is wrong, i started deleting different movie instances and it fixes it but then it messes up and i can not find any pattern or relation to make a connection for why this is coming up. you said you are finding as hard to work with... version 2 or 3?
                                            • 19. Re: Prime Calculator
                                              Rothrock Level 5
                                              Oh version 3. AS2 is great. The documentation rocks and I've been using it for a very loooonnggg time. AS3 – the documentation is awful, there is no syntax checking, and oh, did I mention the documentation sucks!
                                              • 20. Re: Prime Calculator
                                                Rothrock Level 5
                                                Oh version 3. AS2 is great. The documentation rocks and I've been using it for a very loooonnggg time. AS3 – the documentation is awful, there is no syntax checking, and oh, did I mention the documentation sucks!
                                                • 21. Re: Prime Calculator
                                                  isaacewing Level 1
                                                  haha yeah, i completely agree, i HATE as3, it is the worst thing since micheal jackson. i love as2, it was so perfect and everything flowed together and the syntax was robust.
                                                  • 22. Re: Prime Calculator
                                                    Rothrock Level 5
                                                    For me there is no real reason that I would HAVE to use AS3 and the support for AS2 is still quite good in CS3.

                                                    The main thing is that AS3 is so much faster for certain math things I'm trying to do. So that is good. So my plan is to poke at it here and poke at it there and we will see what we learn.
                                                    • 23. Re: Prime Calculator
                                                      Level 7
                                                      isaacewing,

                                                      > haha yeah, i completely agree, i HATE as3, it is the worst
                                                      > thing since micheal jackson.

                                                      I take it you're not old enough to remember when Michael Jackson was the
                                                      greatest thing since sliced bread? (And I'm only a 30-something.)

                                                      > i love as2, it was so perfect and everything flowed together
                                                      > and the syntax was robust.

                                                      AS2 is far from perfect, though it was certainly an improvement over
                                                      AS1, which in turn was an improvement over the ActionScript in Flash 4. Of
                                                      course, AS3 is far from perfect, too. I can't imagine a language that *is*
                                                      perfect ... but maybe you were exaggerating for emphasis. ;)

                                                      I don't see how it can be said that everything "flows together" in AS2.
                                                      For example -- off the top of my head -- let's say you want to load a JPG in
                                                      AS2. The concept here is loading, so a newcomer to Flash (but someone
                                                      familiar with object-oriented programming) might look for a Loader class.
                                                      As it happens, there is a Loader Component, but for the sake of discussion,
                                                      let's not venture into Component territory. Already, this newcomer feels
                                                      lost. How on earth should someone know to look in the MovieClip class in
                                                      order to find a method that loads a JPG?

                                                      And what method am I talking about? MovieClip.loadMovie(). That's load
                                                      *movie* -- now how does that "flow" with the idea of loading a static image
                                                      file? It doesn't, but we're Flashers, so we adapt. ;) Maybe, instead,
                                                      this newcomer stumbles upon the MovieClipLoader class. That would be an
                                                      alternative for loading JPGs, and a good one, because it raises events to
                                                      indicate load start, progress, complete, and more. But again, the name is
                                                      misleading, because MovieClipLoader loads far more than just SWFs (movies).

                                                      When this JPG is finally loaded -- by whatever method -- the developer
                                                      will find it is locked to a particular movie clip container. Whatever
                                                      MovieClip instance holds the JPG is, from then on, the instance that is
                                                      essentially married to it. No divorce allowed..

                                                      In AS3, SWFs, JPGs, GIFs, etc. are loaded with the Loader class. When
                                                      loaded, the image is added to the display list of an object that supports
                                                      the addChild() method -- such as a movie clip. In AS3, this JPG can be
                                                      "re-parented" to another movie clip container (or sprite, etc.) as often as
                                                      desired. Talk about robust! In AS2 this sort of thing simply isn't
                                                      possible.

                                                      By the way, there's a secret involved in my reply, isaacewing ... hold
                                                      on just a bit, and I'll get to that soon. ;)

                                                      Let's look at another example of how AS2 is arguably not a language that
                                                      "flows together"; let's look at events. In AS2, it's possible to handle
                                                      events in at least four ways. To wit: a) the on()/onClipEvent() functions;
                                                      b) dot notation handlers, such as myButton.onRelease = function(){}; c) the
                                                      addListener() method; and d) the addEventListener() method. How would a
                                                      newcomer know which approach to use? That's a good question! The anwer(s)
                                                      depend(s) on context, on which object is dispatching the events. It's one
                                                      of those "AEIOU and sometimes Y" situations, where experience -- or constant
                                                      referral to the Language Reference -- is the only thing that helps.

                                                      Contrast this with AS3, where these various approaches are all neatly
                                                      collapsed into one: addEventListener(). Someone new to the language need
                                                      only learn one technique, and it's consistent almost throughout.

                                                      Almost? Yes, almost. Certain video-related events are exceptions, and
                                                      I was shocked to learn that, because the AS3 marketing touts an overhauled
                                                      event handling system. So ... sure, AS3 isn't perfect, but I admitted that
                                                      going in. Experienced AS2 developers may reply to this message with dozens
                                                      of arguments on what makes AS2 better, and I welcome them to keep on
                                                      truckin' with AS2. ;)

                                                      Remember that secret I alluded to earlier? The secret is, I *love* AS2.
                                                      It has its foibles, but I'm very familiar with them. In a sense, they're
                                                      "my" foibles, because I work with (and around) them so often. Do I like
                                                      AS3? Do I love it? Honestly ... yes and yes. Am I struggling to learn the
                                                      new language? You betcha. I also remember struggling to learn AS2, to
                                                      learn it on a truly useful level, which involves writing class files and
                                                      maybe even dipping into design patterns to coordinate families of custom
                                                      classes. I also love JavaScript, which is (at least currently) similar in
                                                      many respects to AS1. These are all dialects of the ECMAScript
                                                      specification. I guess, the answer is I love ECMAScript.

                                                      Let's everyone keep our chins up. Some people are going to prefer AS2
                                                      for one reason or another; some are going to prefer AS3. AS3 is more
                                                      powerful; it supports strong typing at runtime, which is one of the reasons
                                                      it performs better. Rothrock has discovered that by way of his mathmatical
                                                      endeavors. In his case, that's reason enough to hike the rocky trail of a
                                                      new language. AS3's API is considerably larger than AS2's and is, to my
                                                      thinking, better organized into logically related packages. On the other
                                                      hand, AS2 is more familiar.

                                                      There's room in this town for both languages, depending on the needs at
                                                      hand.

                                                      Rothrock, the book you're going to want is Colin Moock's Essential
                                                      ActionScript 3.0, which is now available (yesss!). At 944 pages, it rivals
                                                      his ActionScript for Flash MX, the Definitive Guide in scope and is
                                                      considerably longer than the 500-page Essential ActionScript 2.0, which
                                                      presumably corresponds to the larger API for AS3.

                                                      Use this URL, and Colin gets a small percentage of the sale.

                                                      http://www.amazon.com/exec/obidos/ASIN/0596526946/ref=nosim/moockorg

                                                      I imagine, given the sort of programming you dig, you may also be
                                                      interested in Keither Peters' new AS3-specific Making Things Move! ...

                                                      http://www.amazon.com/Foundation-Actionscript-3-0-Animation-Making/dp/1590597915/


                                                      David Stiller
                                                      Adobe Community Expert
                                                      Dev blog, http://www.quip.net/blog/
                                                      "Luck is the residue of good design."


                                                      • 24. Re: Prime Calculator
                                                        Rothrock Level 5
                                                        I have no doubt that AS3 will rock. So far I've been very impressed by its speed improvements. I just think they forgot two or three very important parts.

                                                        Syntax Checking
                                                        Decent documentation
                                                        Even the tiniest bit of help for those coming to AS3 from AS2.

                                                        Especially the documentation. In the last two versions of Flash the documentation was STELLAR. The answer to most any questions was easily had once you learned to ignore the search and just go to the class you were interested in. Yes for new folks finding the class was sometimes hit and miss, but overall it was quite simple if you used the help files.

                                                        Now you have to figure out the class you might be interested in.

                                                        Hope it doesn't inherit all of its properties and methods from some other class two or three levels up.

                                                        If so look those up too.

                                                        Read up on all the classes needed to supply the arguments. And/or all the classes used to supply return values.

                                                        And then hope very much that the specific method or property you are interested in actually has a code example at the bottom buried in the possible example.

                                                        Not to mention that many of the entries are just stubs that basically repeat the name of the method/property but in a complete sentence.

                                                        I'm sure over time I will get to love AS3, but it is incredibly frustrating at the moment.
                                                        • 25. Re: Prime Calculator
                                                          I'm sincerely sorry that the ActionScript 3.0 documentation does not meet your needs. We not only appreciate your feedback, but also take your feedback very seriously. Just in case you haven't seen these, here are links to some articles that you may find useful:

                                                          http://www.adobe.com/devnet/flash/articles/first_as3_application.html Introduction to migration issues.
                                                          http://www.adobe.com/devnet/flash/articles/as3_debugger.html Introduction to the new debugger.
                                                          http://www.adobe.com/devnet/actionscript/articles/event_handling_as3.html Introduction to the new event handling system.
                                                          http://www.adobe.com/devnet/actionscript/articles/actionscript_tips.html Highlights differences between ActionScript 2.0 and ActionScript 3.0.
                                                          http://www.adobe.com/devnet/actionscript/articles/image_viewer.html A Colin Moock article that Walks you through the conversion of an AS2 app to AS3.

                                                          http://www.adobe.com/designcenter/video_workshop/?id=vid0130 Getting Started with AS3
                                                          (The Video workshop contains all kinds of useful tutorials, btw. They are like mini online courses.)

                                                          http://www.adobe.com/designcenter/flash/articles/flacs3_migration_08.html Part of this article describes AS2 v. AS3 and working with the script editor in Flash CS3.

                                                          This final link is part of the regular documentation, but I thought it was still worth mentioning in case you haven't seen it. The migration table lists the differences between ActionScript 2.0 and 3.0: http://livedocs.adobe.com/flash/9.0/ActionScriptLangRefV3/migration.html

                                                          We definitely welcome any additional feedback or suggestions you or any one else may have about the documentation (we hear you about the need for more examples in the language reference). You may even want to start a new thread about the documentation to give it more visibility. We'll definitely work even harder next time to get the documentation back to where you expect it to be.
                                                          • 26. Re: Prime Calculator
                                                            Rothrock Level 5
                                                            Thank you Francis. Obviously it is your (collective your, not you personally) fault for setting the bar so extraordinarily high in the last two versions of Flash. :)

                                                            The documentation is quite good – compared to things like Word, etc. It is just a bit rough in a few places that have got me.

                                                            I will take a look at the links you have provided. I had not seen the migration chart. It would be nice, for example if things like a compile time migration error would somehow link or reference such a chart. That would lead people to find it when they need it.

                                                            Also, I just find it hard to read the help files. Having all the methods and properties on one "page" may be easier from a versioning/updating view, but often when I type something into the editor, select it and press F1 it takes me quite a while to actually locate that I have indeed come to the right entry. This is especially true for ones that are far down on the page and it might not scroll to the exact spot.

                                                            Also, it seems that often if I am using a property that is a class has inherited from something way above it. That the help doesn't take me to the correct entry. For example someone was helping me with loading multiple images using the Loader class. It turns out that the Loader class inherits the name property from the DisplayObject class. But if I do this:

                                                            myLoader.name

                                                            and select name and press f1 I am sent to the name property of the Error class. So unless I tracked down:

                                                            Loader class: nope no name property
                                                            DisplayObjectContainer: nope no name property
                                                            InteractiveObject: nope no name property
                                                            DisplayObject: Oh here it is.

                                                            Anyways that makes that a bit difficult. Here is the thread were that came up.

                                                            http://www.adobe.com/cfusion/webforums/forum/messageview.cfm?forumid=15&catid=288&threadid =1265968&highlight_key=y

                                                            Another person started a thread about the syntax checking and I have been keeping it alive. Please see it here:

                                                            http://www.adobe.com/cfusion/webforums/forum/messageview.cfm?catid=288&threadid=1264371

                                                            PS: Over all I am loving CS3. Please accept my congrats (and pass them along to everybody) on making such a nice product. I just want it to be a little better.
                                                            • 27. Re: Prime Calculator
                                                              kglad Adobe Community Professional & MVP
                                                              if you're trying to find all the prime numbers in a certain range (with its lower bound significantly greater than 2), you should try using one of the probablistic methods based on fermat's little theorem.

                                                              the miller-rabin test is easy to implement and computationally feasible for flash.
                                                              • 28. Re: Prime Calculator
                                                                isaacewing Level 1
                                                                thank you to everyone who has contributed to this. Francis Cheng... you have elevated any frustration that i clearly brought onto myself when i took on this task for my friend. Rothrock has contributed to this greatly and for that i am sincerely apprecative. in addtion, i do not think what i said perviously was appropriate becuase i was upset and tired with flash and the michael jackson comment was in deed out of line. i really appreciate the approach to took to assist me becuase after all... you dont owe me an explanation and i am very happy that you helped. the as3 is typical 'beginner' frustration and since i am spoiled with as2 i suppose i need to grow up and just learn it.

                                                                Francis, i will extensively read/research each link you have sent and like i stated earlier, i am very appreciative.

                                                                kglad... your answer is so simplistic and yet it does in fact seem feasible (of course i had to scour google to find out what that function is about). i am very greatful for your help as well.... thank you everyone... you have elevated all my frustration and i am very greatful.
                                                                • 29. Re: Prime Calculator
                                                                  kglad Adobe Community Professional & MVP
                                                                  the following is the continuation of a discussion that was being conducted in private:

                                                                  with regard to the size of numbers that flash can handle, i believe, it is limited to 32-bit integers and cannot handle 64-bit integers reliably.

                                                                  further, there's no known way to reduce the problem of deciding if a particular number is prime by evaluating numbers less than that particular number. and there's good reason to think it is impossible to do so. so, trying to reduce a primality problem of a 64-bit integer into problems involving 32-bit integers is going to fail.

                                                                  regarding prime numbers, security and computers:

                                                                  the reason prime numbers are used for security (in rsa, for example) is because there is no known formula/algorithm/machine that can factor large numbers in your lifetime. so, you're not going to use actionscript, nor any other programming language, to factor large numbers.

                                                                  the greatest mathematicians in history have tried and failed to solve the simplest of problems: given a number, find its prime factors or even, given a number determine if it is prime. it's highly unlikely a brillant hacker will come along and find a way to crack large number factoring when the best mathematicians have failed. that's why people trust rsa (though i don't think many bankers understand that).

                                                                  currently, the fastest methods to determine primality of a number use probabilistic methods. ie, given a particular number it's much easier to say it's ALMOST certainly prime than it is to say it is prime. and that's why i suggested you move from using the sieve of erastosthenes to one of the probabilistic methods based on fermat's little theorem.

                                                                  and finally, just why are you trying to determine primality of numbers? if you're trying to use that for security purposes, actionscript is not adequate. 32-bit and even 64-bit numbers are not even close to being large enough for security use.

                                                                  p.s. computers have greatly advanced work on prime numbers and one of the first (if not the first) proposed use of computers involved prime numbers (turing and the riemann hypothesis).

                                                                  p.p.s. as machines advance and compute more rapidly, larger numbers are used for security purposes. currently, i think, numbers with several hundred digits are used to secure financial transactions.

                                                                  with regard to my academic background:

                                                                  B.A. in mathematics, University of California, Irvine, CA, 6/70.
                                                                  M.S. in mathematics, Louisiana State University, New Orleans, LA, 6/72.
                                                                  Ph.D. in mathematics, Purdue University, West Lafayette, IN, 6/76.
                                                                  Postdoctoral Scholarship in Medical Genetics, University of California, Los Angeles, CA, 9/78.
                                                                  M.D., Yale University School of Medicine, New Haven, CT, 6/82.
                                                                  Pediatric Residency, University of California, Los Angeles, CA, 6/85.
                                                                  Diplomate of the American Board of Pediatrics, 5/88.

                                                                  • 30. Re: Prime Calculator
                                                                    Rothrock Level 5
                                                                    Yeah, what kglad said. That is what I meant in my initial post, only he says it eloquently and with meaning. :)

                                                                    For this type of thing Flash/AS is a fun bit of a toy, but anything serious in prime numbers you won't get far.

                                                                    kglad – I didn't know you were that kind of doctor too!
                                                                    • 31. Re: Prime Calculator
                                                                      kglad Adobe Community Professional & MVP
                                                                      yes, i changed careers in 1980 and went into medicine. that kept me busy and stopped my mathematics research and publications.
                                                                      • 32. Re: Prime Calculator
                                                                        kglad Adobe Community Professional & MVP
                                                                        p.s. i've set the script timeout to 5 minutes and had flash correctly continue executing a for-loop for over 4 minutes and 50 seconds.
                                                                        • 33. Re: Prime Calculator
                                                                          isaacewing Level 1
                                                                          i don't understand,what does that mean... are you saying you implemented a function and ran it for that long... if so what was it and what was the output?
                                                                          • 34. Re: Prime Calculator
                                                                            kglad Adobe Community Professional & MVP
                                                                            that's just an informational item for rr. he asked (above) if anyone could get the timeout to extend beyond 60 seconds.

                                                                            the code below is an implementation of the rabin-miller method for determining if a number is prime. but you should read my message a few above this that discusses several issues related to your thread.

                                                                            • 35. Re: Prime Calculator
                                                                              isaacewing Level 1
                                                                              actually i read your previous posts thoroughly and i loved them. they were very informative... my question is with the attached code... that is what ran for 4:50, was it those two input values which are 1,000,021 to 1,000,041... so it took that long to computer them... one of my friends said the way to calculate efficiency is to use the formula O(n), where n is b - a... does that make sense. so using that formula and determining its solution would using c or c++ or java be a better way to compute this algorithm or is it irrelevant.
                                                                              • 36. Re: Prime Calculator
                                                                                kglad Adobe Community Professional & MVP
                                                                                the above code executes in less than 600ms on my computer.

                                                                                the comment about extending the default actionscript timout was directed to rothrock who asked if anyone could extend the timeout beyond 60 seconds.

                                                                                when you talk about efficiency or speed in this forum there are 2 main things to consider:

                                                                                1. the efficiency of actionscript
                                                                                2. the efficiency of the algorithm encoded by your actionscript.

                                                                                the main problem here, is 1: actionscript was not designed to handle arithmetic calculations efficiently and is not designed to handle large numbers nor a high degree of accuracy in its calculations.

                                                                                it makes no difference whether you use rabin-miller (that i encoded above and is, for numbers that flash can handle, 100% reliable and is big oh of 7*log-cubed of n or you found an algorithm that's 100 times more efficient that rabin-miller.

                                                                                actionscript would still be too slow and is still limited in the magnitude (32-bit) of numbers it can handle.

                                                                                so, to do any signficant calculations involving prime numbers you would want to use a language more adept at handling arithmetic calculations. for example, check the calculation speed at the below link. try 50!+1 and look how fast that number is factored. and then look at the length of that source code.

                                                                                actionscript would require nearly an eternity to execute that code and still couldn't handle numbers that large and so would yield an erroneous result.

                                                                                http://www.alpertron.com.ar/ECM.HTM

                                                                                but again, what are you trying to do? why are you trying to test numbers for primality?
                                                                                • 37. Re: Prime Calculator
                                                                                  isaacewing Level 1
                                                                                  i am trying to test numbers for primality because i want securely transfer information and variables from flash to php scripts for sending/receiving through a site i am developing right now. do i need to use that kind of security when calling php scripts or does it not matter. i have one other problem (well it is the real problem, everything else is just semantics like the prime calculator, i really would like to figure that out but i just do not have the knowledge/knowhow) and that problem is the displayobject function flash cs3 and as3 report when i press the tab key in a certain area of my document... the forum is argument error 2025...
                                                                                  • 38. Re: Prime Calculator
                                                                                    kglad Adobe Community Professional & MVP
                                                                                    are you concerned that information will be intercepted after it's sent from flash and before it's received by your php script?

                                                                                    error 2025: have you explicitly defined tab ordering for objects in that area of your document?
                                                                                    • 39. Re: Prime Calculator
                                                                                      isaacewing Level 1
                                                                                      yes to both, i do not want any sort of security risk during the send/receive process... or at least minimize them as much as possible.

                                                                                      the second part is yes, i have specified tabbing orders for each part of the document. in order to provide a more organized and structured way to input (not that it is necessary however i think it is nice to have setup in the background) i set the unique tab order for each part of the document in in order to provide a sort of ease for the users that tab to the next input part or section rather than use their mouse. there are roughly eight sections right now and the first two work fine, the last one works all work in their own realm however when i combined them the problem arises. as noted in the topic argument error 2025 i have denoted through trial and error that the problem resides with the part2 and/or part3 sections and after testing for some time yesterday and today i have come to the conclusion it has nothing to do with the tab keys... the error is returned when you tab but the actual error probably has something to do with the name of a variable that overlaps another one (i.e. matching variable names). although i have not successfully tested this and found this to be true it is my current hypothesis for why this error is occurring.
                                                                                      1 2 Previous Next