Необычный метод вычисления НОД

[int13]

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

У меня есть вопрос, который мучает меня довольно давно, надеюсь получить помощи по нему. Все что у меня сохранилось по нему, это бумага в котором в результате неких преобразований, производится шаг некого алгоритма, в результате которого, НОД полученных чисел равен НОД изначальных двух. Это не алгоритм Евклида, не бинарный и не алгоритм Лемера (хотя возможно имеет что-то общее с ними).

У меня нет точной информации об этом методе (если честно, нет вообще никакой информации), но насколько я знаю - так делать можно, т.е. это должно работать и у этого метода есть свои преимущества (насколько я понял, этот метод обладает субквадратичной трудоемкостью и его выгодно использовать для вычисления НОД двух очень больших чисел (насколько больших?))

Все что я о нем знаю, я прикрепил к теме в виде фотографии. Т.е. взяв два числа, над ними можно произвести примерно такие преобразования, и полученные в результате два числа будут иметь тот же НОД что и изначальные, т.е. этот способ можно использовать в качестве "редукции".

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

Можно ли где-нибудь почитать про этот метод? Буду благодарен за любые детали относительно его использования и применения. В идеале, мне хотелось бы иметь четкое представление обо всех возможных случаях, которые могут возникнуть в ходе этого метода, для того чтобы иметь возможность четко реализовать его на каком-нибудь языке программирования.

Ссылка на описанный метод: http://oi39.tinypic.com/2z4gzko.jpg

[ИСН]

У меня есть некий предмет. Он железный (частично), полукруглый, хотя в то же время довольно угловатый, ну и сбоку такая рукоятка, как у лопаты, но совсем не такая. Не даёт покоя вопрос: что надо делать этим предметом, и как?

[arseniiv]

int13, если вы понимаете этот алгоритм, постарайтесь всё-таки изложить его, а не прогонку на одном примере. Обилие цифр и разных преобразований только сбивает с толку.

[int13]

К сожалению, я не могу сказать что я его понимаю, все что я могу это прогонять один шаг этого метода для набора данных из двух чисел состоящих из восьми разрядов :(.
(Я надеялся, что это какой-нибудь очевидный и широкоизвестный метод который можно опознать методом исключения..)
С математическим аппаратом как и с математикой у меня все довольно слабо...
Все же попробую изложить суть метода своими словами, как я его понимаю...

Для того, чтобы сделать предположение о НОД двух больших чисел, достаточно знать их ведущие разряды.
Чем больше разрядов, тем точнее оценка. В моем способе, почему-то изначально берут первые два разряда (возможно сначала числа делят пополам, потом еще пополам; теоретически, можно брать сколько угодно но от этого должна зависеть эффективность алгоритма).

Далее, к этим двум числам приписывают единичную матрицу (как это делается в расширенном алгоритме евклида), и находятся элементы матрицы (кажется, их еще называют коэффициенты Безу, поправьте если не прав). Необходимо чтобы эти элементы матрицы не превышали некоторого порядка (в моем случае 10, потому что берется два разряда). Если числа матрицы будут больше 10, то это как-то влияет на точность вычислений, и в этом случае гарантировать точность метода уже нельзя.

Далее, применяется некая процедура восстановления (я так и не понял ее смысл, это не совсем умножение матриц), когда мы умножаем полученную матрицу коэффициентов на изначально-взятые разряды, плюс берем следующие несколько. После вычислений, получаем два числа такие что, хотя бы одно из этих чисел будет хотя бы на один разряд меньше изначальных (обычно сразу оба), - мы можем заменить изначально взятые разряды полученными числами - и в этом и заключается суть метода.

После первого прохода (первая часть метода), применяется та же последовательность действий к уже полученным числам, в результате мы получаем два новых числа (еще меньше разрядов чем предыдущие) - и еще одну матрицу. Получается, что нам удалось сделать из двух 8-разрядных чисел, два 6-разрядных - но при этом, нам нужно хранить две матрицы из предыдущих результатов вычислений. Для того чтобы завершить шаг алгоритма, описанная выше последовательность применяется еще раз, но на этот раз ко всем оставшимся разрядам с учетом первых двух матриц. Теперь, после того как метод полностью завершен, нам уже не нужны матрицы коэффициентов и мы можем заменить начальные два числа (8-разрядных), полученными новыми двумя (6-разрядными)...

Таким образом, нужно повторять этот алгоритм в цикле, до тех пор пока числа не станут достаточно малыми - и тогда оставшиеся вычисления можно будет добить обычным алгоритмом Евклида.

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

[iifat]

Такое чувство, что идея примерно в том, что берём всё тот же алгоритм Евклида, но делаем все операции со старшим куском; когда числа уменьшатся, добавляем следующий кусок, пересчитываем числа (мы хитрые и храним накопленные коэффициенты) и продолжаем с прерванного места. Вот только не уверен, что работать будет быстрее даже на арифметике многократьной точности.

ИСН в сообщении #728780 писал(а):

Не даёт покоя вопрос: что надо делать этим предметом, и как?

Ну, вообще-то, по описанию несколько напоминает топор. Вы можете копать им землю, только выработать несколько другую технику.

[int13]

Трудоемкость этого метода должна быть $O(n \log n)$.
Существуют ли вообще какие-нибудь методы нахождения НОД с трудоемкостью $O(n \log n)$?
Если да, то это должно быть как раз то, что я ищу.