- #1
matqkks
- 285
- 5
Do they use the Euclidean Algorithm?
You still need some sort of division to calculate how much you have to subtract. Simply subtracting the smaller number from the larger number repeatedly has a really bad worst-case runtime if the numbers are very different (exponential, while divisions make the method scale with the input length squared).jedishrfu said:I imagine math software would use this algorithm to compute it as subtractions are relatively cheap compared to multiplications or divisions.
The GCD (Greatest Common Divisor) of two integers is the largest positive integer that divides both numbers without a remainder.
Computers use the Euclidean algorithm to find the GCD of two integers. This algorithm involves repeatedly dividing the larger number by the smaller number until the remainder is zero. The last non-zero remainder is the GCD.
Yes, computers can find the GCD of any two integers, regardless of their size or whether they are positive or negative.
The Euclidean algorithm used by computers to find the GCD is very efficient and has a time complexity of O(log n), where n is the larger of the two input numbers. This means that the time taken to find the GCD increases slowly as the input numbers get larger.
Yes, computers can evaluate the GCD of more than two integers by finding the GCD of two of the numbers and then finding the GCD of that result with the next number, and so on until all numbers have been evaluated.