- #1

- 285

- 5

Do they use the Euclidean Algorithm?

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

In summary, there are various algorithms that can be used to compute the GCD of two integers, but the most commonly used and efficient one is the Euclidean algorithm. This algorithm involves using repeated subtractions and is relatively cheap compared to other methods. However, there are alternative algorithms that can compute the GCD faster for longer inputs.

- #1

- 285

- 5

Do they use the Euclidean Algorithm?

Mathematics news on Phys.org

- #2

Science Advisor

- 8,140

- 571

- #3

Mentor

- 14,590

- 8,779

- #4

Mentor

- 14,590

- 8,779

https://en.m.wikipedia.org/wiki/Euclidean_algorithm

I imagine math software would use this algorithm to compute it as subtractions are relatively cheap compared to multiplications or divisions.

Another remote possibility is it uses a combination of lookup table and Euclidean algorithm to speed things up although that may take up more memory than necessary and depending on the table size more costly time wise.

- #5

Mentor

- 37,000

- 13,696

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.

There are alternative algorithms that can compute the GCD faster than quadratic runtime for longer inputs.

Share:

- Replies
- 3

- Views
- 806

- Replies
- 26

- Views
- 1K

- Replies
- 13

- Views
- 1K

- Replies
- 1

- Views
- 1K

- Replies
- 1

- Views
- 549

- Replies
- 1

- Views
- 612

- Replies
- 7

- Views
- 840

- Replies
- 1

- Views
- 647

- Replies
- 14

- Views
- 825

- Replies
- 6

- Views
- 685