fahlers wrote: You beat me with my own (sorry: with Dan Shanks') algorithm. Did you discover it independently?
I knew about it before you annouced that you used it to achieve your first impressive time, yes. I was busy implementing Brent's Rho while you were doing SQUFOF, I suspect. I had started reading Jason Gower's Ph.D dissertation around the point that your first timings and comments were posted. And my priorities changed a bit after that, I'll admit. I was surprised at first at how much more efficient it was - I believed at the time that the Rho method could compete. Brent's Rho generally requires only a few hundred to perhaps a thousand iterations to find factors of this size, while Shanks algorithm sometimes needs tens of thousands. I thought that this would negate the extra work involved in dealing with higher precision numbers. I think that both algorithms are commonly used to factor relations used in the quadratic sieve because of their speed with numbers of this size.
I imagine you would have at least equaled my execution speed had you had more time to develop your code. I guess I managed to sacrifice a bit more sleep for the sake of this challenge!
I submitted several versions of my code, and here I've attached one of them - not sure if its the one Bruce used as the final one or not. I've never claimed to be a Labview expert, so I'd welcome any critiques of it as well as questions, if there are any. Written in Labview 7.1.
Nice come back Lynn!
I should also recognize that Pitt and CMU were still using their DecSystem 10's and 20's as late as 1990.
KL-10 instruction set was the most powerful instrction set I have ever worked with. Hyperbolic functions were implemented in machine code and variabel length bit fields were supported (a "byte" code be defined as being from 1 to 36 bits long). It took a freight train to move one those babies. If you had bad memory, you had to count rows of cabinets to find the the right cabinet. They actually used light bulbs and not LEDS!
Ok, brief tangent on a real-world application of prime factors that doesn't relate to cryptography or hashing.
I was working on an LabVIEW RT app a few years back where the data rate was too high to stream to disk or TCP/IP. Fortunately the duration was short enough that we could simply stuff data into RAM until the end of the test and write to disk afterward.
Due to a quirk/bug/anomaly/whatever, we found that we couldn't use the simple approach of allocating memory at the beginning of each run because RT didn't de-allocate fully at the end of the prior run. We would regularly get only 2-4 runs in before having to reboot the RT box. Eventually we found that instead of calling "Initialize Array", we were able to get memory allocation by calling "Reshape Array" with an empty array input. By wrapping a loop and unitialized shift register around the whole thing, we could now perform actual allocation on our first run after boot but then keep reusing the exact same memory space for all subsequent runs. Voila! No more need to keep rebooting the RT box!
Where do the primes come in? Well, we had to pick an appropriate total size for the storage array. In our case, the user could choose to "record" anywhere from 1 to 16 channels of AI data, using a potentially different number on each run. So the question is, can we choose an array size that will exactly fit an integer # of samples no matter how many channels are in each sample? And the answer is yeah, sure, just use prime factoring to help determine the least common multiple for all integers from 1 to 16. Leaving some of this as an exercise for the reader, the spanning set of prime factors is 2*3*2*5*7*2*3*11*13*2 = 720720. So a 1D array with a dimension of 720720 (or some integer multiple of it) can be exactly resized into any needed 2D shape to accomodate the 2D data returned from an AI Read.
This allowed fast turnaround from one test to the next because were no longer trying to allocate big contiguous chunks of RAM (which could take tens of seconds). The Reshape simply tells LabVIEW how to interpret the row & column indices, it requires no manipulation of the actual memory at all.
Anyhow, I thought it was kinda cool to have another real-world use for small primes. (The other one has to do with gearing -- it's often desirable for mating gears to have numbers of teeth that are mutually prime, i.e., no common prime factors. This way each tooth encounters every other tooth before repeating.)
Nice story Kevin,
I may use your reshape idea next week.
As I understand it, primes come into play with cicadas where they come in different versions, each being dormant most of the time but only coming out to reproduce in prime number multiples of years. That way the 7 year cicada only comes out the same year as the 13 year cicada once every 91 years.
Yep, primes are cool!