• Зарегистрирован: 2010-01-14
  • Сообщений: 3

Тема: вопрос расширенный алгоритм евклида

Здравствуйте! Помогите - Как будет выглядеть расширенный алгоритм Евклида в нерекурсивной форме?
в коде на сайте указан пример реализации на с++ - рекурсивный с использованием указателей.
а мне нужно реализовать это на java с BigIntrger (реализую RSA) - там ведь указателей нет.

int gcd (int a, int b, int & x, int & y)
{
    if (a == 0)
    {
        x = 0; y = 1;
        return b;
    }
    int x1, y1;
    int d = gcd (b%a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

вообще меня интересует - какой в конце будет y(int & y), а не само d

2 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: вопрос расширенный алгоритм евклида

Мне кажется, что гораздо проще будет оставить рекурсивный вариант. Просто x и y возвращать не с помощью переменных по ссылке, а как результат функции.

Т.е. сделать класс gcd_return, содержащий три поля: g, x, y - соответственно наименьший общий делитель, и x и y. И возвращать его.

Сайтe-maxx

3 Ответ от brainail

  • brainail
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-22
  • Сообщений: 165

Re: вопрос расширенный алгоритм евклида

Нерекурсивный метод почти точно такой же,во первых его можно найти в интернете или во многих книжках там он делается с помощью обычного цикла,во вторых можно и любой рекурсивный самому перевести в нерекурсивный,просто что не так удобно..

4 Ответ от Матвей

  • Зарегистрирован: 2010-01-14
  • Сообщений: 3

Re: вопрос расширенный алгоритм евклида

Спасибо. Я разобрался. вот код на java

class triplBig
{
    triplBig(BigInteger one, BigInteger two,BigInteger three)
    {
        d=one;
        x=two;
        y=three;
    }

    triplBig()
    {
        ;
    }

    BigInteger d;
    BigInteger x;
    BigInteger y;
}

triplBig gcdWide(BigInteger a, BigInteger b)
{
    triplBig temphere = new triplBig(a,BigInteger.ONE,BigInteger.ZERO);
    triplBig temphere2 = new triplBig();

    if(b == BigInteger.ZERO)
    {
        return temphere;
    }

    temphere2 = gcdWide(b, a.mod(b));
    temphere = new triplBig();

    temphere.d=  temphere2.d;
    temphere.x = temphere2.y;
    temphere.y = temphere2.x.subtract(a.divide(b).multiply(temphere2.y));

    return temphere;
}

5 Ответ от winger

  • winger
  • Участник
  • Неактивен
  • Откуда: Санкт-Петербург
  • Зарегистрирован: 2009-06-17
  • Сообщений: 25

Re: вопрос расширенный алгоритм евклида

В java есть реализованный алгоритм Евклида для BigInteger - метод gcd. Он в данном случае будет намного эффективнее обычного, т.к. там реализован двоичный алгоритм Евклида, работающий быстрее обычного в размерность чисел раз быстрее

6 Ответ от brainail

  • brainail
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-22
  • Сообщений: 165

Re: вопрос расширенный алгоритм евклида

Эх,такое бы в Паскаль smile

7 Ответ от Матвей

  • Зарегистрирован: 2010-01-14
  • Сообщений: 3

Re: вопрос расширенный алгоритм евклида

winger пишет:

В java есть реализованный алгоритм Евклида для BigInteger - метод gcd. Он в данном случае будет намного эффективнее обычного, т.к. там реализован двоичный алгоритм Евклида, работающий быстрее обычного в размерность чисел раз быстрее

да gcd есть. но РАСШИРЕННЫЙ алгоритм Евклида, метода которого я не нашел, дает не только НОД, но и ещё кое-какие числа, которые мне и были нужны для реализации RSA.