1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What have you tried so far? What is one big difference between these two problems, and why might it make the GCD problem harder? $\endgroup$ – j_random_hacker Dec 11 '18 at 12:04
  • $\begingroup$ edited the question to the add what I have tried, but still not clear whether my question is a valid question or not $\endgroup$ – Vk1 Dec 11 '18 at 12:11
  • 1
    $\begingroup$ 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. $\endgroup$ – j_random_hacker Dec 11 '18 at 12:15
  • $\begingroup$ Ty... It would be really helpful, if you could upvote the question. $\endgroup$ – Vk1 Dec 11 '18 at 12:28
  • $\begingroup$ 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. $\endgroup$ – gnasher729 Dec 11 '18 at 14:36
0
$\begingroup$

You are saying that you will perform n-1 gcd operations, unless you find k numbers with a gcd of 1 by performing k-1 gcd operations.

Since you don't know which set of numbers has a gcd of 1, you can't pick a set with gcd 1. Your total time depends on the data you have.

You can try to process small numbers first, because the gcd of small numbers tends to be calculated quicker than the gcd of large numbers.

The optimal strategy will not always lead to the best outcome. I put a deck of cards on the table, face down, and ask you to pick the ace of hearts. Do you think "pick the ace of hearts" is the optimal strategy? No, it isn't a strategy that you can enforce since you don't know which one is the ace of hearts.

$\endgroup$
  • $\begingroup$ I have clarified the question now, hopefully it makes more sense now. $\endgroup$ – Vk1 Dec 11 '18 at 15:09
  • $\begingroup$ Let me give you another simple example so that you can understand my point of view. We compute in two different ways GCD(20,35,85). Clearly the gcd is 5 aka not 1. GCD(15,35,85) =GCD(15,20,85) =GCD(10,15,85) =GCD(5,10,85) =GCD(5,5,85) =GCD(5,85) =GCD(5,80) =GCD(5,40) =GCD(5,20) =GCD(5,10) =GCD(5,5) =5 11 invocations. Second way is GCD(15,35,85) =GCD(15,35,50) =GCD(15,15,35) =GCD(15,35) =GCD(15,20) =GCD(5,15) =GCD(5,10) =GCD(5,5) =5; 8 invocations. I hope you see the difference. $\endgroup$ – Vk1 Dec 11 '18 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.