Matrix chain multiplication problem:- Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. This problem is solved using dynamic programming.
GCD chain operation is defined as:- Given a set of $ n$ integers, what is the most efficient way to find the gcd of all the elements?
The cost is the number of GCD(x,y) invocations done by a binary GCD algorithm.
Basic attempt at solving the problem is:- GCD$ (a_1,a_2,a_3,a_4,\ldots a_n)$
$ k=GCD(a_1,a_2)$ .
if ($ k=1$ )
return $ GCD(k,a_3,a_4\ldots a_n)$ ;
In simple terms, it keeps finding the gcd of the smallest two among all the $ n$ elements and then recurse, by replacing the two elements with their gcd which is at most the smallest element in the input.
Make suitable assumptions if necessary. For example you can assume that the integers are given in sorted order.
Assume GCD is computed using a binary GCD algorithm (other GCD algorithm is also fine) aka
$ GCD(a,b)= GCD(a-b,b)$
and $ GCD(a,2b)=GCD(a,b)$ (if $ a$ is odd)
Number of steps is 3
Number of steps is 4
Number of steps is 6
A heuristic strategy mentioned in the basic attempt above is not optimal for the following example
= GCD(GCD(25,75),125,179,181,225) (3 steps)
=GCD(GCD(25,125),179,181,225) (4 steps)
=GCD(GCD(25,179),181,225) (6 steps)
This required 13 invocations of GCD(x,y) function.
But the optimal strategy would be to see that 179 and 181 have gcd 1 and therefore the solution is 1, which requires computing only 1 bivariate gcd.
which takes 3 invocations of GCD(x,y) only
I am not sure if there exists an optimal way to do it, or maybe it is NP hard to find a solution which makes the least number of GCD(x,y) calls.