September 12th, 2018, 12:13 PM  #1 
Newbie Joined: Apr 2011 Posts: 29 Thanks: 0  Gcd
How do computers evaluate the gcd of two integers?

September 12th, 2018, 01:00 PM  #2 
Global Moderator Joined: Dec 2006 Posts: 19,542 Thanks: 1751 
They could use the Euclidean algorithm.

September 13th, 2018, 03:12 AM  #3 
Newbie Joined: Apr 2011 Posts: 29 Thanks: 0 
You say they could, but do they use Euclidean Algorithm?
Last edited by skipjack; September 13th, 2018 at 03:27 AM. 
September 13th, 2018, 03:41 AM  #4 
Global Moderator Joined: Dec 2006 Posts: 19,542 Thanks: 1751 
It's quite likely that they use the binary gcd algortithm for improved efficiency. However, I haven't checked (and I'm not sure how it could be checked).
