What is the optimal way to perform GCD chain operation?

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.

Similarly

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 1;

else

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)$$

$$GCD(2a,2b)=2GCD(a,b)$$

and $$GCD(a,2b)=GCD(a,b)$$ (if $$a$$ is odd)

GCD(75,25)=GCD(50,25)=GCD(25,25)=25

Number of steps is 3

GCD(125,25)=GCD(100,25)=GCD(50,25)=GCD(25,25)=25

Number of steps is 4

GCD(179,25)= GCD(154,25)=GCD(77,25)=GCD(52,25)=GCD(26,25)=GCD(1,25)=1

Number of steps is 6

A heuristic strategy mentioned in the basic attempt above is not optimal for the following example

GCD(25,75,125,179,181,225)

= 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)

=1

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.

GCD(179,181)=GCD(179,2)=GCD(179,1)=1

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.

• What have you tried so far? What is one big difference between these two problems, and why might it make the GCD problem harder? – j_random_hacker Dec 11 '18 at 12:04
• edited the question to the add what I have tried, but still not clear whether my question is a valid question or not – Vk1 Dec 11 '18 at 12:11
• Thanks for editing, but see if you can fix the formatting. I think your question is valid. I don't know the answer, but suspect there's no "good" one -- the difference I was trying to get you to think about is that with matrix multiplication, we know the dimensions of the matrices up front. With GCD, that would seem to amount to knowing the factorisation of each integer, in which case the problem becomes almost trivial: k-way list merge. – j_random_hacker Dec 11 '18 at 12:15
• Ty... It would be really helpful, if you could upvote the question. – Vk1 Dec 11 '18 at 12:28
• Your cost analysis is wrong. You counted the gcd operations, but gcd(25,75) is found very quickly, while gcd(25, 179) takes a lot longer. – gnasher729 Dec 11 '18 at 14:36