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
(1,793 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
CLAD expired, using LV2011SP1 + LV2017 (+LV2019 sometimes) on Win7+cRIO
Kudos are welcome Smiley Wink

Message 2 of 15
(1,783 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
(1,780 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
(1,771 Views)
Highlighted

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
(604 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

 


LabVIEW Champion. It all comes together in GCentral GCentral
0 Kudos
Message 6 of 15
(545 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
(503 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
(501 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.


LabVIEW Champion. It all comes together in GCentral GCentral
0 Kudos
Message 9 of 15
(497 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
(491 Views)