LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

Prime Factor Coding Challenge

Well my first reactions was "now you tell me!"

 

Thanks CC!

With your mention of the word sieve you may have saved me from certain death in this competition. But I will not rule out my need of a "mathamortician" yet. Smiley Happy

My version of the prime finding code was based on what I learned in grade school about prime numbers. I thought is an accomplishment when I figured out I did not have to check values larger the largest of consecutive primes divided into the number I was checking.

So in my intital attempt to figure out what a sieve was I found a posting in a web-page that said I did not have to check any value larger than the square-root of the number I was checking. At this point a light bulb went on when I realized my observation converged on the square-root. So I cleaned things up and it turns out I can now find all of the primes less than 100,000,000 in only 9 minutes and 47 seconds.

This code is uses only 4.6K and would probably be a competittor if there were not other more efficient techniques not previously known to a Math Wimp.

Back to the web and more searching. So after finding out that my approach is good for small numbers but just will not work for large numbers and reading about equivalence and matrix operations I was lamenting my situation to my wife over dinner. She THEN said "Sieve, I did one of those in college." Smiley Surprised  So now I have a fresh approach that may help me.

Since I do not like throwing away my work and since the approach I am using can not be used in the "Challenge" I am attaching the code as an open example (in LV 7.1).

 

Feel free to sit back and laugh if you want. Just remeber that ther is a mean old bear chasing you armed with a sieve. Smiley Tongue

Ben

Message Edited by Ben on 10-09-2005 09:37 AM

Message Edited by Ben on 10-09-2005 09:38 AM

Retired Senior Automation Systems Architect with Data Science Automation LabVIEW Champion Knight of NI and Prepper LinkedIn Profile YouTube Channel
Download All
Message 71 of 186
(2,727 Views)
Hi everyone.
 
I'm new using labview. I'm interested and I want participate in this challenge Smiley Happy But I have a problem... How can I handle 16 digits in my software? My software only works with 8 digits (99999999). Smiley Sad
 
Can someone help me with this problem?
It looks very funny!
 
Thanks for read this... and sorry about my english language Smiley Tongue
 
 
 
 
0 Kudos
Message 72 of 186
(2,548 Views)
You need to used DBL representation for the product of the prime numbers, it can deal with about 16 decimal digits. (Or you could wait for LabVIEW 8.0, which support 64bit integers ;))
0 Kudos
Message 73 of 186
(2,545 Views)
OK, CC. The gloves are off! Try to beat this! 😄  (everybody else, please ignore this post:o)
0 Kudos
Message 74 of 186
(2,589 Views)


 


altenbach a écrit:
OK, CC. The gloves are off! Try to beat this! 😄  (everybody else, please ignore this post:o)


Ouch ! Not bad ! I'm really impressed ! I was sure you were improving your vi, but not to such an extent ! 😮

However, I also made some progress. 😉

Try this one and come back later ! :D:D:D

Chilly Charly    (aka CC)

         E-List Master - Kudos glutton - Press the yellow button on the left...
        
Message 75 of 186
(2,585 Views)
😄
 
Cute! I guess you discovered my new algorithm!
 
... and I thought slowing it down a bit and scrambling the VI data (Couple of XORs with the loop counter, etc) will throw you off the right track for a few hours longer. Here's my original, clean and faster version. I think it is competitive with your latest try. The only way to make it faster is to make it at least 4x bigger in size. 😞
 
Easily beats your version by a factor of two with about the same VI size. 😄
 
.... back to the fancier algorithms. 🙂

Message Edited by altenbach on 10-09-2005 10:43 PM

Message 76 of 186
(2,588 Views)
Erm, guys, I'm starting to feel left out here.

Partially because I've no new code yet (A new algorithm, yes, but no new code).

Anyone able to post these in 6.1 so I can have a look at the times?  Or is someone willing to run all on a specific maching and post the relative speeds?

Shane.
Using LV 6.1 and 8.2.1 on W2k (SP4) and WXP (SP2)
0 Kudos
Message 77 of 186
(2,584 Views)
Shane,
 
Here are the times for the last four posted "Chaos" entries for a 1.6Ghz Pentium M, 1GB under LabVIEW 7.1
 
BeatCCToo.vi  (Me) 5ms
DittoFaster.vi (Me) <1ms
 
Don't worry, the last three entries probably won't work that well for the coding challenge. 🙂
0 Kudos
Message 78 of 186
(2,580 Views)
He he I think I get it:

Bruce:  Smaller "seed" arrays, such as the prime numbers up to 1000, are allowed.
Titou:  An array up to 1000 prime numbers or an array with prime numbers, the greater one being less than 1000 ?
Bruce: You just can't have a table for all the prime numbers - you have to generate the majority of your prime numbers.
Altenbach: I guess you discovered my new algorithm!

Or rather I really HOPE I get it, otherwise the race just got kinda one-sided 😄

I'm working on a new algorithm for sieving generating Primes, and I'll post as soon as I get around to code something.

Just out of curiosity.  Where has the "primes up to 2,400,000" come from?  Surely this isn't enough to allow a proper solution of the coding challenge, or am I missing something really major here......  I'm generating 5,7 million prime numbers each time.... :(

Shane.
Using LV 6.1 and 8.2.1 on W2k (SP4) and WXP (SP2)
Message 79 of 186
(2,565 Views)


@shoneill wrote:
He he I think I get it:

Bruce:  Smaller "seed" arrays, such as the prime numbers up to 1000, are allowed.
Titou:  An array up to 1000 prime numbers or an array with prime numbers, the greater one being less than 1000 ?
Bruce: You just can't have a table for all the prime numbers - you have to generate the majority of your prime numbers.
Altenbach: I guess you discovered my new algorithm!



Just out of curiosity.  Where has the "primes up to 2,400,000" come from?  Surely this isn't enough to allow a proper solution of the coding challenge, or am I missing something really major here......  I'm generating 5,7 million prime numbers each time.... 😞



I may be a little off here since I looked at this awhile ago and have been sitting on the sidelines, watching people throw code back and forth at each other.  Here are my questions and observations:

First, isn't an 8 digit prime number up to 100 Mil?  So if pi(100Mil)=5,761,455, aren't there 5.7Mil primes that we need to be concerned with, not 2.4Mil?.  Or did I miss an idosyncrasy somewhere?

Second, I never came up with a fancy schmancy way to generate primes, although I did get a really slow method.  The road I immediately went down though was finding the difference between the primes, which is of course curious to see since it's random but not really.  And what I initially wondered was, how far up the prime number scale will the difference be less than 256?  Because for all of those numbers, you could just use a precalculated U8 array to store the difference and add them all up, which technically is keeping with the rules of not storing the prime numbers themselves.  And then the next question of course was, where you would have to flip over to using a U16 array to store the differences (assuming you're concerned about array size so as not to have a large VI--otherwise just store them all as U32!!).  My initial plots showed that the difference between primes was less than 256 for a pretty long time, but my slow prime generation VI didn't let me ever run it to completion.  In fact, I really don't have the time to compete and work on it, which is why I'm just posting my thoughts here instead of trying to go off and implement them myself.  I am still pretty curious as to the break even # for a U8 array (the highest prime it would be able to generate from a difference array).
0 Kudos
Message 80 of 186
(2,556 Views)