Prime Factor Coding Challenge

[BruceAmmons]

Try the prime factor coding challenge!!!

This is being sponsored by Ammons Engineering, so I will be answering any questions people may have here.

Bruce

[BruceAmmons]

If you are wondering about the details of the challenge, check it out here:

http://www.ni.com/devzone/lvzone/codingchallenge.htm

Bruce

[TiTou]

Hi Bruce !

I'd like to know what kind of computer will run the speed test ?
Mac (G3, G4, G5, PIV ?) or PC (AMD, Intel, 32 bit CPU, 64 bit CPU ?)
and also what Os will be installed ?

Thanks

[BruceAmmons]

Most likely my laptop or desktop.  Both are Windows XP, Pentium PCs.  The laptop is Pentium M, and the desktop is an older Pentium 4.  These are both 32 bit machines.

Bruce

[BruceAmmons]

I have attached a test VI that has a list of 100 numbers and their factors.  This list of numbers is very similar to what the final test will be like.  You can use this VI to test your solution and make sure it works properly.  I saved this back to LV 6.1.

Bruce

[TiTou]

Smaller "seed" arrays, such as the prime numbers up to 1000, are allowed.

I found the above sentence in the challenge's rules (following the link you gave) but don't really know how I shall understand it.
An array up to 1000 prime numbers or an array with prime numbers, the greater one being less than 1000 ?
Thank you for making this clear, and sorry about my low english skills.

[BruceAmmons]

Either interpretation is fine.  The number 1000 is approximate in any case.  I am not going to count how many prime numbers you have in a table.  You just can't have a table for all the prime numbers - you have to generate the majority of your prime numbers.

Some algorithms start with a small "seed" array of known primes, which are used to generate the larger primes.  That is the main intention for allowing a small starter table.

Another issue is storage.  Storing the complete list of primes compactly takes several Mb of space, minimum.  I don't want anybody submitting a 10 or 20 Mb solution - that is just too bulky.

Bruce

[altenbach]

Bruce, I like this challenge!

So, How are you guys doing. Anyone tried anything yet? 🙂

I just spend a while this morning to make a first quick&ugly draft with the following results (1GHz PIII, 512MB RAM). This is the "total time" for all 100 examples, all correctly solved:

First run after fresh loading of LabVIEW:  <70 seconds total (Includes dynamic table generation).
All later runs: <13 seconds (using cached table data).

I don't use any pre-computed seed table at all. No fancy algorithms, just plain vanilla brute force. The initial table generation is currently mostly disk trashing and swapping instead of  computations. I have some ideas to dramatically improve this, though. 😉

(I am currently switching over to a much newer, faster laptop, so things will improve automatically, too 😄 )

I modifed your test VI to display the results of the last four runs. Here is the result of four runs after rebooting the computer. There is some jitter due to OS activity, but nothing major. Run "-3" is "first run".

Sooo... who's the first one that does it under 1 second?! 😮

Message Edited by altenbach on 09-18-2005 03:13 PM

[altenbach]

Bruce,

One problem is that a DBL representation is not sufficient to hold all possible 16 digit numbers. (53 bit mantissa!). (try to enter 2^53+1 ;))

(LabVIEW claims ~15 digits for DBL).

I think many 16 digit problems cannot be solved unless resorting to higher resolution math. Are we supposed to do that?

Do you for example get the right solution for 8876247534257515  (your highest problem +2)? My code currenty has a problem with it (maybe It is a bugs in my code, though ;))

[BruceAmmons]

You can't just randomly select 16 digit numbers to factor.  The one you picked has a prime factor that is larger than 8 digits.  If you represent everything as DBL during factoring, you should be able to get the proper prime factors in this case.  NOTE:  This number would not be used in the challenge, since the largest prime factor will only be 8 digits.

My trick is to generate two 8 digit numbers and factor them separately.  I multiply them together to get the 16 digit number that has to be factored by your vi, and I combine the prime factors to get the prime factors of the 16 digit number.  By selecting my 8 digit numbers carefully, I can control the difficulty of the factorization, and I can guarantee none of the prime factors are greater than 8 digits.

You are right that a DBL can't represent all 16 digit integers.  However, it can represent every integer up to 9E15.  Somewhere past that (after 2^53, as you point out), it can only represent even integers.  If I were you, I would make sure my program can handle every 16 digit integer that can be represented by a DBL.

Bruce

FYI, I checked with my program.  The factors of your number are 5 and 1775249506851503.

Message Edited by Bruce Ammons on 09-20-2005 11:48 PM