LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

gcd of more than 2 numbers

hi there,
 
does anybody knows a way to calculate the gcd ("greatest common divider") of more than 2 numbers?
 
thanks in advance
Best regards
chris

CL(A)Dly bending G-Force with LabVIEW

famous last words: "oh my god, it is full of stars!"
0 Kudos
Message 1 of 15
(6,020 Views)
Hi chris,

one way would be to do a factorization of all numbers.
After having a list of all prime factors you only have to look for common factors of all numbers 🙂

Best regards,
GerdW


using LV2016/2019/2021 on Win10/11+cRIO, TestStand2016/2019
Message 2 of 15
(6,010 Views)

Hi Gerd,

well, ok...:-) there has been a coding challenge "prime factors" some time ago, i'll take a look at the code i can found there.

Best regards
chris

CL(A)Dly bending G-Force with LabVIEW

famous last words: "oh my god, it is full of stars!"
0 Kudos
Message 3 of 15
(6,007 Views)

hi there

i found something useful at http://zone.ni.com/devzone/cda/epd/p/id/1005

based on Ben Buhrows code i could find a solution for my needs (I32, value < 1.000.000). see attachment (sorry, no valid zipper round here...). 

Best regards
chris

CL(A)Dly bending G-Force with LabVIEW

famous last words: "oh my god, it is full of stars!"
0 Kudos
Message 4 of 15
(5,998 Views)

For anyone coming across this now, this is a much more performant and easier to understand solution:

 

GCD of N Numbers.png

 

It recursively uses the shipping GCD VI instead of using the prime factor method.  (I suspect that the GCD VI didn't exist back in 2006 when this post was originally made.)  VI is attached.

Message 5 of 15
(4,831 Views)

@croohcifer wrote:

For anyone coming across this now, this is a much more performant and easier to understand solution:


(Be careful with the wording, this has nothing to do with recursion. I am also not sure what "much more performant" means. Do you have relevant benchmarks?)

 

In any case. Your version still seems overly complicated. You only need exactly one instance of GCD.

 

Here is equivalent, but arguably simpler code. 😄

 

GCDArray.png

 

0 Kudos
Message 6 of 15
(4,772 Views)

Thanks for calling out my sloppy use of "recursion" and for providing the simplified code!  Yes, I did benchmark it per Darren's brainless LabVIEW benchmarking best practices to be multiple orders of magnitude faster than the original solution.  Here's the snippet for those looking:

 

snip.png

0 Kudos
Message 7 of 15
(4,730 Views)

We could make a recursive version, if that is a requirent or goal of some sort (homework?).

 

We could make a VI that calculates the GCD of a number and an array. If the array >1 element, strip a number and call the VI.

 

Altough that would be pointless, overcomplicated and wasteful, it will be recursion. Smiley Wink.

0 Kudos
Message 8 of 15
(4,728 Views)

@croohcifer wrote:

Yes, I did benchmark it per Darren's brainless LabVIEW benchmarking best practices to be multiple orders of magnitude faster than the original solution.


Most likely things could be improved even further by taking advantage of the fact that we are dealing with an array. For example if we would sort the array in a certain way first and then use code tailored to that fact. I have not tried.

0 Kudos
Message 9 of 15
(4,724 Views)

I don't doubt that.  In my case, I was just trying to find the GCD of the sample rates of data sets captured across several (5-10) different instruments running at various rates.  I used this post as a starting point, spent about 15 minutes improving it, saw massive gains, and moved on.  For much larger data sets where performance is critical, I'm sure more mathematically capable folks than me could come up with something stellar 🙂

0 Kudos
Message 10 of 15
(4,718 Views)