Example Code

least common multiplyer from an array of numbers

Code and Documents

Attachment

Download All

OverView:

This VI shows how to find the least common multiplyer 

 

Description:

When you need to find the least common multiplyer number from an "n" array of integers.

 

Requirements:

  • LabVIEW 2013 (or compatible)

Its a very fast and simple algorithm.

 

 Additional Information or References:

 lcm1.jpg

 

lcm.jpg

 

 fixed cpu use - added delay

removed unneeded local variables to make diagram easy to read

 

 

Example code from the Example Code Exchange in the NI Community is licensed with the MIT license.

Comments
altenbach
Knight of NI Knight of NI
Knight of NI
on

This looks like a literal translation of text code with sequence frames as lines and local variables as variables.

 

I would recommend to place some interesting default values into the controls before saving so we can run it right away.

(You should also include error handling, e.g. if the input array contains zeroes or an overflow occurs.)

 

Bonus task: Try to do it without local variables, orange wires, or stacked sequences. It will be faster, much simpler code and much more in the spirit of LabVIEW.. 😄 Also watch CPU use if it is not doing anything, currently it is polling the "calculate" button millions of times per second.

popobbb
Member
Member
on

fixed cpu use and i mad diagram more simple to read

altenbach
Knight of NI Knight of NI
Knight of NI
on

Thanks. Looks much better but still has way too many local variables for my taste. None are needed!

 

(all your versions seem to be in LabVIEW 2013, so you might want to correct that in the text above. You say 2012).

 

I would also recommend "high resolution relative seconds" for the timing. Much more precise!

 

I posted my version over there (cannot attach code here). Note that your excursion to orange wires severely limits the range of numbers compared to U64. Yours will overflow for integers at ~52bits (mantissa size of DBL) while U64 can handle integers up to 64bits, quite a few orders of magnitude more. As mentioned, there still should be verification and error handling (check for zeroes in the input and check for overflow in the calculation. Both not implemented here).

 

(Also note that this is still exactly your algorithm. I don't know if there are better ones and I have not explored that.)

 

 

 

LCMCA.png

 

popobbb
Member
Member
on

First of all thanks for the time you invest in my post.

im sorry that i dont agree with you on the local variables use, for small code its ok to try to get more wires insted of locals.

but in big codes you will end up with more wires than you can count.

you posted the highresolution vi with password, i cant look how its mad inside, if you can post one with no pass it will be great

 

and the last thing , no that this is a competition , but my VI calculate LCM in half the time .

the "quotient and reminder"  box takes alot of time i dont know why !!! ( i dont use it)

 

compare time.jpg

 

again thank for you time , i learned alot today from you.

altenbach
Knight of NI Knight of NI
Knight of NI
on

Well, as I said, U64 handles significantly more bits, and while slower, can solve harder problems here. Probably worth a factor of two. 😄

 

What kind of CPU are you using? Your numbers seems slow? I get about 0.5ms for these inputs in my code (LabVIEW 2017), and if I switch my code to DBL and do the division (instead of Q&R), it takes about 0.25ms. Also note that your benchmark is somewhat flawed because your final division runs in parallel to the end timing and is thus not counted (makes little difference here, just saying :D).

 

> Im sorry that i dont agree with you on the local variables use, for small code its ok to try to get more wires insted of locals.

but in big codes you will end up with more wires than you can count.

 

Wires are much cleaner than local variables (a 1D object is smaller than a 2D object in area 🐵 and avoid many problems, especially if the code gets big. There are plenty of better ways to avoid many wires (clusters, objects, FGVs, DVRs, etc.)  There are many discussion in the forum about that subject. Local variables break data dependency and thus often need sequence structures to re-establish the correct execution order and avoid race conditions. Two wrongs don't make a right :D. Sequences often prevent compiler optimizations e.g. to rearrange computations to really utilize multiple CPU cores.  With local variables, you never know where the value got modified last. With wires, you know exactly where the data is coming from and where it is going. (This is not my personal opinion, virtually all advanced LabVIEW programmers agree here).

 

> you posted the highresolution vi with password, i cant look how its mad inside, if you can post one with no pass it will be great.

 

This is part of LabVIEW and directly in the palette of newer LabVIEW versions. I did not make it. While it existed in LabVIEW 2013, you had to find it in the guts of the LabVIEW hierarchy. 😄 (See also this idea).

 

Benchmarking can be tricky. For some background, have a look at our NI-Week 2016 presentation.

Blokk
Trusted Enthusiast
Trusted Enthusiast
on

im sorry that i dont agree with you on the local variables use, for small code its ok to try to get more wires insted of locals.

but in big codes you will end up with more wires than you can count.

 

Adding to what altenbach wrote above, I would like to bring your attention to some more explanations why we need to be careful with (over)using local variables, and sequence structures:  http://www.ni.com/newsletter/51735/en/

popobbb
Member
Member
on

all correct and true, i agree with every word, ill take this to consideration. Smiley Happy

altenbach
Knight of NI Knight of NI
Knight of NI
on

Just to wrap this up ....

 

> ... and the last thing , no that this is a competition , but my VI calculate LCM in half the time.

 

Do you want to make it a competition??? 😮 For fun I made a few tweaks using a slightly different approach and gained about 2 orders of magnitude (<<10 microseconds) on the example data. (Same speed improvement and identical result (extensively tested!) for any random input array as long as the data does not overflow the U64 range (both seem to hit the limit at about the same time).

 

FasterLCM.png

 

There is still a lot of slack left and I am sure I can improve further if needed, but first try to beat that one. 😄

 

(I won't post the VI for a while to give others a chance to explore. I guarantee it is real and not photoshop. :))

 

 

popobbb
Member
Member
on

thats very impresive Smiley Frustrated

ill try again !

altenbach
Knight of NI Knight of NI
Knight of NI
on

Sorry, I forgot about this thread, but here's my algorithm that does the LCM calculation for an array of numbers quite fast. (In about 800ns using the default inputs from above when bench-marked correctly).

 

(It even does some extra validation and returns zero if the result is invalid e.g. due to overflow in the computation or the presence of zeroes in the input. This validation costs about 200ns for the default inputs, so the LCM calculation actually takes only about 600ns).

 

Algorithm: Successive reduction by the GCD.

 

LCM-Array-Validate.png

 

 

etfovac
Member
Member
on

can we get this solution in VI form?

altenbach
Knight of NI Knight of NI
Knight of NI
on

> can we get this solution in VI form?

 

Are you talking about my VI right above? It is a simple flat VI (No hidden code or anything). Do you have problems recreating it? Should be trivial to do! What is giving you problems?

 

I probably posted it elsewhere already, but I can try to find it.

etfovac
Member
Member
on

Just to say thank you for sharing your LCM algorithm.

I've reconstructed it as a VI, and it did the trick.

It's much like the NI's one (\vi.lib\gmath\DiscreteMath.llb\Lcm.vi).

 

etfovac
Member
Member
on

And here's the snippet of your code, with additional zero check.

 

LCM (Array).png

altenbach
Knight of NI Knight of NI
Knight of NI
on

Would seem more efficient to just test for the presence of zero, then skip the bulk of the code if it occurs. No need to form (and later process!) two different sub-arrays using external tools many don't have.

 

Here's what I would do to check for zeroes and return a TRUE if at least one zero is found (other case is "default" and only contains a TRUE constant)

 

altenbach_0-1596559947052.png

 

etfovac
Member
Member
on

Oh, it actually filters out the zeros and performs the task with the remaining array elements for debugging purposes.

Before that I think that some code produced NaNs that were replaced with zeros etc.

So I left it there to track which elements were off, and how that affected some other results.

I admit I like to add OpenG stuff everywhere 🙂

altenbach
Knight of NI Knight of NI
Knight of NI
on

> Before that I think that some code produced NaNs that were replaced with zeros etc.

 

U64 does not have NaNs (Of course I have no idea what you mean by "some code". 😉

Pure integer problems should not show any orange anywhere.

 

(personally, I never have any openG stuff installed, so I would not be able to run your code.)

etfovac
Member
Member
on

Well it became an integer problem when I converted the double array that was read from a device.

Which is completely beside the point.

Contributors