Длинная Арифметика. Алгоритм Евклида

Длинная арифметика   4 апреля 2013  Автор статьи:  

В данной статье вы увидите алгоритм Евклида для больших чисел. Собственно говоря он ничем не отличается от алгоритма для обычных чисел. Для реализации алгоритма Евклида я буду использовать библиотеку, которую мы написали в цикле уроков Длинная арифметика. Скачать ее можно в последнем уроке. Итак, алгоритм Евклида служит для нахождения НОД двух чисел:

Вход

Длинные числа a и b

Выход

d = НОД(a,b)

public static BigInteger GCD(BigInteger a, BigInteger b)
{
if (b.Equals(Zero))
{
return a;
}
else
{
return GCD(b, a.Mod(b));
}
}

В рамках данной статьи я не буду рассказывать, почему так происходит, если захотите, то вы сможете прочитать теорию.
Тесты:

[TestMethod()]
public void GCDTest()
{
Assert.AreEqual(new BigInteger("11"), BigInteger.GCD(new BigInteger("33"), new BigInteger("121")));
Assert.AreEqual(new BigInteger("1234567890"), BigInteger.GCD(new BigInteger("45679011930"), new BigInteger("28395061470")));
}

Расширенный алгоритм Евклида

Мы уже обсуждали в статье про обратный элемент полезность расширенного алгоритма Евклида, кроме того, что он находит НОД, он также находит u и v, где u * a + v * b = d = НОД(a, b). Асимптотика данного алгоритма равна асимптотике обычного алгоритма Евклида, что делает его особенно привлекательным:

Вход

Длинные числа a и b

Выход

u, v, d,
где u * a + v * b = d = НОД(a, b)

public static BigInteger FullGCD(BigInteger a, BigInteger b, out BigInteger u, out BigInteger v)
{

u = new BigInteger("0");
v = new BigInteger("1");
BigInteger u0 = new BigInteger("1");
BigInteger v0 = new BigInteger("0");
BigInteger u1 = new BigInteger("0");
BigInteger v1 = new BigInteger("1");
BigInteger q = a.Div(b);
BigInteger r = a.Mod(b);
while (!r.Equals(Zero))
{
u = u0.Substract(q.Multiply(u1));
v = v0.Substract(q.Multiply(v1));
u0 = u1;
v0 = v1;
u1 = u;
v1 = v;
a = b;
b = r;
q = a.Div(b);
r = a.Mod(b);
}
return b;
}

Тесты:

[TestMethod()]
public void FullGCDTest()
{
BigInteger u = new BigInteger("0");
BigInteger v = new BigInteger("1");
Assert.AreEqual(new BigInteger("11"), BigInteger.FullGCD(new BigInteger("121"), new BigInteger("33"), out u, out v));
Assert.AreEqual(new BigInteger("11"), (u.Multiply(new BigInteger("121"))).Add(v.Multiply(new BigInteger("33"))));
Assert.AreEqual(new BigInteger("1234567890"), BigInteger.FullGCD(new BigInteger("45679011930"), new BigInteger("28395061470"), out u, out v));
Assert.AreEqual(new BigInteger("1234567890"), (u.Multiply(new BigInteger("45679011930"))).Add(v.Multiply(new BigInteger("28395061470"))));
}

Научиться программировать

  • на Delphi

  • на Java

  • на C++