LabVIEW
Project Euler Problem 14 Memory Problem
Solved!
@TheStrangeQuark wrote:
Is this correct that it only compares the last bit of the int to 1?
AND is a "masking" operation, and since 1 has only the least bit set (all others are zero), ANDing will only leave the single bit that is either set (odd) or not (even). So while the equal operation still compares all bits, almost all are zero. Bit-wise operations on integers are very fast.
A few things to speed your code up:
- You can wire the result of the ANDing operation directly to the case structure. Make one case 1 and and one case 0 (and make one the default).
- In the while loop, you don't need to do a +1 with every iteration of the loop. Even if you don't do that, you'll see what's larger. You can add 2 at the very end, after the FOR loop (See my code picture). The length should be defined including the start element and the 1 as last element, so you would need to add 2. Rename the output of the subVI as "Collatz length - 2" for clarity.
- If you are testing for speed, you need to make sure that the subVI front panels are closed. If they are open, LabVIEW will update the indicators, which is extra work and slows you down.
- You can gain even more speed by disabling debugging of the subVI and inlining them (execute options). This will eliminate the debugging and calling overhead.
- ...
See how far you get. I'll post my code later for comparison.
What's the model of your CPU?
Mine is an older dual Xeon (2x E5-2687W) running at 3.1GHz. Since nothing is parallelized here, it is of course only using one core. I expect a modern I7 to be faster.
OK, here's my version.
(Note that you only need to do the =1 check for even inputs. (3n+1 can never be 1.)
An here's my typical timing result:
There are probably faster ways to do all that. 😄
@TheStrangeQuark wrote:
Would you mind saving it for LabVIEW 2015? I'm a bit ol' fashioned
Try this...
Of course I made a few quick and simple modifications and it gets the same result now in well under 50ms. 😮
There is still a lot of slack left. Try it! 😄
For completeness, here's my faster versions. See if you figure out the code. It is very simple! 😉
(Note that it also works correctly if you delete the 1D array from the toplevel code and leave the array inputs/outputs unwired at the subVI, it is just slower :))
It does 1M in under 50ms, 20M in about a second, and 100M in about 5 seconds on my slow laptop.(I7-5600U CPU @ 2.60GHz)
(If you try to go much higher (e.g. 1G), you'll run out of memory in 32bit LabVIEW)
(It does not use any parallelization. See if you can improve it significantly, i.e. more than 5% :D)
For reference, I wonder if some of you could get speed results on various other CPU models, e.g. for 20M or 100M. For example, I would be curious about AMD vs Intel, for example.
