Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d9/d5d/extended__euclid__algorithm_8cpp.html below:

TheAlgorithms/C++: math/extended_euclid_algorithm.cpp File Reference

Loading...

Searching...

No Matches

GCD using [extended Euclid's algorithm] (https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) More...

#include <algorithm>
#include <iostream>
#include <cstdint>

Go to the source code of this file.

GCD using [extended Euclid's algorithm] (https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm)

Finding coefficients of a and b ie x and y in Bézout's identity

\[\text{gcd}(a, b) = a \times x + b \times y \]

This is also used in finding Modular multiplicative inverse of a number. (A * B)M == 1 Here B is the MMI of A for given M, so extendedEuclid (A, M) gives B.

Definition in file extended_euclid_algorithm.cpp.

template<typename T, typename T2>

Implementation using recursive algorithm

Parameters

[in] A unsigned [in] B unsigned [out] GCD unsigned [in,out] x signed [in,out] y signed

Definition at line 71 of file extended_euclid_algorithm.cpp.

71 {

72 if (B > A)

73 std::swap(A, B);

74

75 if (B == 0) {

76 *GCD = A;

77 *x = 1;

78 *y = 0;

79 } else {

81 T2 temp = *x;

82 *x = *y;

83 *y = temp - (A / B) * (*y);

84 }

85}

void extendedEuclid(T A, T B, T *GCD, T2 *x, T2 *y)

template<typename T1, typename T2>

Implementation using iterative algorithm from Wikipedia

Parameters

[in] A unsigned [in] B unsigned [out] GCD unsigned [out] x signed [out] y signed

Definition at line 42 of file extended_euclid_algorithm.cpp.

42 {

43 if (B > A)

44 std::swap(A, B);

45

46 T2 s = 0, s0 = 1;

47 T2 t = 1, t0 = 0;

48 T1 r = B, r0 = A;

49

50 while (r != 0) {

51 T1 quotient = r0 / r;

55 }

56 *GCD = r0;

57 *x = s0;

58 *y = t0;

59}

void update_step(T *r, T *r0, const T2 quotient)

Main function.

Definition at line 88 of file extended_euclid_algorithm.cpp.

88 {

90 int32_t x, y;

91 std::cin >> a >> b;

std::cout <<

<<

<< x <<

<< y << std::endl;

std::cout <<

<<

<< x <<

<< y << std::endl;

96 return 0;

97}

void extendedEuclid_1(T1 A, T1 B, T1 *GCD, T2 *x, T2 *y)

int gcd(int num1, int num2)

template<typename T, typename T2>

function to update the coefficients per iteration

\[r_0,\,r = r,\, r_0 - \text{quotient}\times r\]

Parameters

[in,out] r signed or unsigned [in,out] r0 signed or unsigned [in] quotient unsigned

Definition at line 25 of file extended_euclid_algorithm.cpp.

25 {

26 T temp = *r;

27 *r = *r0 - (quotient * temp);

28 *r0 = temp;

29}

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4