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

Question

Псевдокод расширенного алгоритма Евклида:

НА ВХОДЕ: два неотрицательных числа $%a$% и $%b$%: $%a\geq b$%
НА ВЫХОДЕ: $%d=НОД(a,b)$% и целые $%x$%, $%y$%: $%ax + by = d$%.

Если $%b=0$% положить $%d:=a$%, $%x:=1$%, $%y:=0$% и возвратить ($%d,x,y$%).
Положить $%x_2:=1$%, $%x_1:=0$%, $%y_2:=0$%, $%y_1:=1$%.
Пока $%b>0$%:
3.1. $%q:=[a/b]$%, $%r:=a-qb$%, $%x:=x_2-qx_1$%, $%y:=y_2-qy_1$%;
3.2. $%a:=b$%, $%b:=r$%, $%x_2:=x_1$%, $%x_1:=x$%, $%y_2:=y_1$%, $%y_1:=y$%.
Положить $%d:=a$%, $%x:=x_2$%, $%y:=y_2$% и возвратить ($%d,x,y$%).

А что такое "с усеченными остатками" какой алгоритм? Никак не пойму. Спасибо.

------------------------Правка---------------------- На C# набросал программу которая реализовывает "Расширенный алгоритм Евклида с усеченными остатками"

 static void ras_o(BigInteger a, BigInteger b)
        {
            if (b == 0)
            {
                Console.WriteLine("d = " + a + " x = " + 1 + " y = " + 0);
                return;
            }
            BigInteger r = 0, x2 = 1, x1 = 0, y2 = 0, y1 = 1, x = 0, y = 0, count = 0;
            while (b > 0)
            {
                BigInteger q = BigInteger.Abs(a / b);
                if(q>b/2) q = b - q;
                r = a - q * b;
                x = x2 - q * x1; y = y2 - q * y1;
                a = b; b = r; x2 = x1; x1 = x; y2 = y1; y1 = y;
                count++;
            }
            Console.WriteLine("d = " + a + " x = " + x2 + " y = " + y2 + " s = " + count );
        }

Но проблема в том что у него количество итераций равно количеству итераций с обычным "Расширенный алгоритм Евклида", может я опять что то не понял? вроди все ок добавил if(q>b/2) q = b - q;

asddsa 9●1●6 · Answer 1

0

Если можно, добавьте в ответы:

    if (b == 0)
            {
Console.WriteLine("a = " + a + " x = " + 1 + " y = " + 0);
return;
}
BigInteger r = 0, x2 = 1, x1 = 0, y2 = 0, y1 = 1, x = 0, y = 0, count = 0;
while (b > 0)
{
   BigInteger q = BigInteger.Abs(a / b);
   r = a - q * b;
   if (r > b / 2) r = b - r;
   x = x2 - q * x1; y = y2 - q * y1;
   a = b; b = r; x2 = x1; x1 = x; y2 = y1; y1 = y;
   count++;
            }
  Console.WriteLine("a = " + a + "\nb = " + b + "\nx = " + x2 + "\ny = " + y2 + "\ns = " + count); вдруг кому пригодится, код на C#

ссылка

отвечен 19 Ноя '14 0:39

asddsa
9●1●6

изменен 21 Ноя '14 23:11

Виталина
99●1●7

@falcao есть одна помарка, у нас тут НОД это число "а", но при расчете коэффициентов X и Y тоже надо как то учитывать их при условии r > b/2.? Иначе у меня при умножении ax + by <> НОД.

(22 Ноя '14 12:54) asddsa

@asddsa: нахождение множителей -- это отдельная задача. Вообще, это довольно естественно делается в обратном порядке. По идее, надо запоминать промежуточные числа, и тогда это просто. Если не запоминать, то формулы перехода там тоже можно выписать, но они более "хитрые". Мне вникать в текст программы не хочется, но я могу всё как бы "с нуля" объяснить -- это проще.

(22 Ноя '14 17:06) falcao

@falcao понял, спасибо, хочу еще помучится. :) Отпишусь, если получится. :)

(23 Ноя '14 14:24) asddsa

@falcao, извиняюсь, но я не смог рассчитать множители. (

(23 Ноя '14 17:45) asddsa

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

1 ответ

Здравствуйте

Связанные вопросы

Отслеживать вопрос