LabVIEW
Maximum array size
- last edited on by
Content Cleaner
Prime numbers are integers, and numbers below 1E9 fit comfortably into I32 or U32, so You can immedaitely save 50% by using 32 bits/value instead of 64 bits.
An array with 51M elements will thus be a bit over 200MB. If you code it right and don't create unecessary data copies, you should be fine.
Arrays require contiguous memory, so that's another concern.
Let's assume you are using LabVIEW 32bit on a 32 bit OS. The application can use a max of 3GB of ram after some tweaks in boot.ini. How much RAM do you have? On a 64 bit OS, LabVIEW 32 bit can use 4GB of RAM.
Of course if you have a 64bit OS and are using LabVIEW 64 bit, and have plenty of memory, things are even easier. 😉
What have you tried so far? How are you generating the prime numbers? Read them from a file? Some efficient methods to generate prime numbers from scratch use quite a bit or RAM.
If you don't know you probably have 32 bit.
LabVIEW 2009 is the first (I think) available in 64 bit, this will be shown when starting up LabVIEW in the splash screen.
Ton
LabVIEW user groep
- last edited on by
Content Cleaner
Amitai Abramson wrote:
I have been using 12 digits prime numbers for some purpose,
So to verify that they are indeed primes I used an array that contains all the the 6 digits primes or less (square root of 12 digits) (array size=~80,000). and the process worked just fine and fast.
Now I need to use 18 digits primes, that mean I need to assist an array that will contain all the prime numbers with 9 digits or less.
the array size will be ~ 51 million.
You might have a look at our old prime factor challenge (results). The problem was slightly smaller (16 digit prime numbers, factors up to 8 digits), but otherwise quite similar. If I remember right, this was from back in the days where 64 bit integers (U64, I64) were not supported. 64 bit floating point (DBL) cannot support 18 digit primes, thus the limit on 16 digits in the challenge.
Yes, most likely you're on 32bit. What have you tried so far? Did you run into memory issues? (An Inspiron 1525 comes with 2GB of RAM, so that should be fine). My Laptop has only 1.5GB at the moment and I'll try some of my old code to see if there are bottlenecks. 😉 Most likley the memory problems will occur during generations of the primes, not for the final array storage.
What is your LabVIEW version? If you have LabVIEW 2009, you also might look into data value references to keep datacopies to a minimum.
I just dug out my old prime code for up to 8 digit factors. It uses the Sieve of Eratosthenes to generate the table. It takes about 6 seconds to generate all 8 digit primes. For 9 digits, it should take about a minute.
It runs out of memory for 9 digit primes, because my original array is I32, meaning the work array is 2GB, too big for a 32bit environment.
There are probably ways around all this by changing the data structures. I'll try under 64bit too.
altenbach wrote:I just dug out my old prime code for up to 8 digit factors. It takes about 6 seconds to generate all 8 digit primes.
That's fast !!! 😉
I've been trying a lot of code variations to come close to this but I failed 
About 3.5 sec for primes up to 200000
and 41 sec for primes up to 999999
So would you be so kind to point out where I could improve the code?
- Initialize an array of x elements
- Fill the array with numers 0 to x
- Do the "Eratosthenes" trick to eliminate non primes. To avoid redim of the array I replace non primes by -100
- Sort the array to get all -100 at the top of the array
- Remove all equals (-100) with Open G vi
- Remove first three elements (-100, 0 & 1) to keep only real primes.
Note that I don't need this code, i've made this just out of curiosity 🙂
Thanks for helping anyway 😉
Alain S wrote:
altenbach wrote:I just dug out my old prime code for up to 8 digit factors. It takes about 6 seconds to generate all 8 digit primes.
About 3.5 sec for primes up to 200000
and 41 sec for primes up to 999999
My code does 200000 is about 6ms (600x faster) and 999999 in about 32ms. (1200x faster) 🙂
(of course it also depends on hardware ;))
Alain S wrote:
So would you be so kind to point out where I could improve the code?
- Initialize an array of x elements
- Fill the array with numers 0 to x
- Do the "Eratosthenes" trick to eliminate non primes. To avoid redim of the array I replace non primes by -100
- Sort the array to get all -100 at the top of the array
- Remove all equals (-100) with Open G vi
- Remove first three elements (-100, 0 & 1) to keep only real primes.
A FOR loop knows the number of iterations, so generating the values in an autoindexing shift register is equally efficient and simpler. Steps (1&2) can be combined. It is also sufficient to only consider odd values (except "2"), reducing the array by 50%.
You are already touching the element so why not move it down to the next prime slot, reusing the operating array for the prime storage at once. This also eliminates sorting (O(NlogN)) and openG tools. Just truncate at the end after the last prime found. (4&5).
Looking at your code:
General:
Don't use a timeout case to poll the stop button 100x/sec while the program is idle. Use a latch action button to start the code, no need to reset via a value property (if you really want to reset the value, use a local variable instead). Use another event for the stop button.
While loop:
With every iteration of the while loop, you are converting to DBL and taking the square. Keep it blue! There should be no orange wires!
You can precalculate the number of iterations and use a FOR loop, eliminating the termination calculations.
Inner FOR loop:
You don't need to do trial divisions, this is way too much work. (The main reason for the slow performance!). Simply calculate the multiple indices directly. Once you are at half-size, there are no multiples left, don't keep looking for them. (My code runs the inner FOR loop 0 times for large values, eliminating a case structure).
After the loop:
Sorting is not needed if you correctly place the primes as they are calculated.
After sorting, all "-100" are at the beginning. All you need to do is search for the element with "2" and take the subset to the end. No need for fancy openg tools.
You shoud write to the indicator after the sequence. You don't want the timing to be biased by potential indicator updates.
Attached is a simple version of the code (LabVIEW 8.0. I have some others that might be more optimized in other terms (e.g. smaller memory footprint)). Of course there could be bugs. 😉
See if it makes sense. I am sure there are inprovements possible. Of course you want to do this only once if it is part a bigger code, so use the "first run?" primitive and keep the primes in a shift register. No need to use an indicator for them at all.
Amitai Abramson wrote:I need to process something while having all the prime numbers less than 1E9 available.
there are approximately 51 million.
is it ok with LabVIEW? (array of the size 51 million) I will use 64bit array.
OK, back to the original question. Having a 51M I32 array in memory is not such a big deal if done right, but doing the sieve calculation will not work unless you do some tweaks to reduce the storage requirements.
Taking some clues from the code posted above, remember that the work array for the sieve only need half as many elements if we drop the even numbers. Also, for the sieving operation, all we need is a single bit for each position, to be tested if it is set or not and to unset at positions corresponding to multiples of the current prime. Thus the work array only needs to be 1E9--divided by 2 for the odd values---divided by 8 for 8 bits per byte, basically another ~60MB. It looks doable under 32bits. I don't know about performance... 😉
