C-Sharp-Algorithms/Algorithms/Numeric/GreatestCommonDivisor.cs at master · aalhour/C-Sharp-Algorithms · GitHub

Name: C-Sharp-Algorithms/Algorithms/Numeric/GreatestCommonDivisor.cs at master · aalhour/C-Sharp-Algorithms · GitHub
Rating: 4.6 (3630 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
usingSystem;

namespaceAlgorithms.Numeric
{
publicstaticclassGreatestCommonDivisor
{
/// <summary>
/// Returns the greatest common divisor of two numbers using Euclidean Algorithm.
/// </summary>
publicstaticintFindGCDEuclidean(inta,intb)
{
intt=0;

a=Math.Abs(a);
b=Math.Abs(b);

if(a==0)
returnb;
if(b==0)
returna;

while(a%b!=0){
t=b;
b=a%b;
a=t;
}
returnb;
}

/// <summary>
/// Returns the greatest common divisor of two numbers using Stein Algorithm.
/// </summary>
publicstaticintFindGCDStein(inta,intb)
{
a=Math.Abs(a);
b=Math.Abs(b);

returnStein(a,b);
}

privatestaticintStein(inta,intb)
{
if(a==0)
returnb;
if(b==0)
returna;
if(a==b)
returna;

if((~a&1)==1)
{
if((b&1)==1)
{
returnStein(a>>1,b);
}
else
{
returnStein(a>>1,b>>1)<<1;
}
}

if((~b&1)==1)
{
returnStein(a,b>>1);
}

returna>b?Stein((a-b)>>1,b):Stein(a,(b-a)>>1);
}
}
}