4

What is the time complexity of __gcd(m,n) function? Also, does it use the Euclidean method to calculate gcd?

e.g. code

#include <iostream> 
#include <algorithm> 

using namespace std; 

int main() { 
    cout << "gcd(10, 25) : " << __gcd(6, 20) << endl; 
}
Baran
  • 97
  • 1
  • 11
Amit Srivastava
  • 57
  • 1
  • 1
  • 3
  • 7
    It's non-standard, so you have to check your compiler documentation for that. – Yksisarvinen Jun 11 '19 at 09:47
  • 2
    What compiler are you using? `__gcd` is not in the standard library. [`std::gcd`](https://en.cppreference.com/w/cpp/numeric/gcd) is in the [``](https://en.cppreference.com/w/cpp/numeric) header starting from C++17 though. – ruohola Jun 11 '19 at 10:06

2 Answers2

4

Yes, it use Euclidean method to calculate gcd of two values. It's complexity is (2) algorithm, where n is the upper limit of a and b.

Details : https://www.quora.com/What-is-the-time-complexity-of-Euclids-GCD-algorithm

Faruk Hossain
  • 1,205
  • 5
  • 12
-4

Yes, its using the euclidian (Implementation of the in-built __gcd method in C++)

And the time complexity is O(n) (Time complexity of Euclid's Algorithm)

Narase
  • 490
  • 2
  • 12
  • 1
    you probably refer to the top answer on that question. I have to admit, I dont understand it completely, it seems to argue with the number of digits and denotes `N` as the number of digits. However, note that the number of digits of a number does not scale linear – 463035818_is_not_an_ai Jun 11 '19 at 10:21