Расширенный бинарный алгоритм

[Анти]

Поделитесь, пожалуйста, расширенным бинарным алгоритмом для поиска НОД целых чисел. Нигде не могу его отыскать.

[bot]

Это тот при котором ищется не только НОД, но коэффициенты линейной комбинации ax+by=d ?
Хм, признаться не в курсе, где это изложено. Считал, что это фольклор и по сути это просто алгоритм Евклида. Вкратце это выглядит так:
составляем матрицу (a >b):
1 0 a
0 1 b
и начинаем гауссовыми преобразованиями строк уменьшать сначала a, потом b и т.д.
Будет получаться:
1 0 a
0 1 b
* * c
* * e
....
* * f
x y d
Обрываем процесс, когда d делит f, и потому следующим преобазованием мы получаем строчку с 0 на последнем месте.
Тогда d - это НОД (a,b) и ax + by = d.
Пример: ищем НОД(69, 48):
1 0 69
0 1 48
1 -1 21 (из первой строчки вычли вторую)
-2 3 6 (из второй строчки вычли удвоенную третью)
7 -10 3 (из третьей строчки вычли утроенную четвёртую)
Так как 6 делится на 3, то END.
Ответ: 7*69 - 10*48 = 3
Видимо это где-то и запрограммировано, но я не в курсе.

[Анти]

На мой взгляд, то, что ты описал больше напоминает расширенный алгоритм Евклида. Он, по сути, должен отличаться от расширенного бинарного, хотя делает то же самое.
Слышал, что расширенный бинарный алгоритм встречается в трудах С.А. Абрамова и С.И. Рыбина, но материалов найти не смог.
Не уверен, но, возможно, там нужно брать один вектор что-то типа (0,b/2^k, -a/2^k) и в процессе работы как-то делить и умножать. В итоге должен получиться НОД и коэффициенты для чисел.
У кого-нибудь есть литература, посвящённая расширенному бинарному алгоритму?

[nworm]

Тут вроде есть
http://services.eliteral.com/digital-certificate-mumbai/chap14.php

[Анти]

Спасибо!
Кажется, вот это:

14.61 Algorithm Binary extended gcd algorithm
INPUT: two positive integers x and y.
OUTPUT: integers a, b, and v such that ax + by = v, where v = gcd(x, y).
1. g 1.
2. While x and y are both even, do the following: x x/2, y y/2, g 2g.
3. u x, v y, A 1, B 0, C 0, D 1.
4. While u is even do the following:
4.1 u u/2.
4.2 If A B 0 (mod 2) then A A/2, B B/2; otherwise, A (A + y)/2,
B (B - x)/2.
5. While v is even do the following:
5.1 v v/2.
5.2 If C D 0 (mod 2) then C C/2, D D/2; otherwise, C (C + y)/2,
D (D - x)/2.
6. If u v then u u - v, A A - C, B B - D;
otherwise, v v - u, C C - A, D D - B.
7. If u = 0, then a C, b D, and return(a, b, g · v); otherwise, go to step 4.

[InterceptorTSK]

Люди, вы гоните) От вас просят БИНАРНЫЙ алгоритм) Так, для справки сообщаю, что любой высокопроизводительный бинарный алгоритм имеет в своем арсенале ТОЛЬКО операции битового сдвига и логические операции (and, or, xor, not), и все) для тех кто в танке сообщаю, что даже использование конструкций if-else не допустимо, либо применяется в крайних случаях. Разумные итерации конечно допустимы. Как пример приведу "студента", который искал знак произведения серии целых цисел (3x), и писал следующую строчку: sign = Math.Sign(a) * Math.Sign(b) * Math.Sign(c). Я как это увидел - просто ужаснулся))) Этож до чего надо быть кретином, чтобы из такого порно программки ляпать) Говорю - ну получается у тебя из сигнов набор из +/- единиц, ну используй битовые операции, нахрена это все чудовищно перемножать? Далее задался конкретно этим вопросом, ну и получилось вполне разумное решение: sign = ((a ^ b ^ c) >> 31) | 1 (это при условии, конечно же, если a b c типа int). При прогоне тупого "студенческого" метода миллиард раз и вышеприведенного бинарного разница составила более 1000%!!!! Прекратите уже бредить, и писать всякую чушь, типа поделить это на то, и называть ЭТО высоким словом БИНАРНЫЙ АЛГОРИТМ))) Ну и, разумеется, бинарный алгоритм нахождения НОД есть. Там нет ни одной операции деления, умножения, нет ни одного if-else и прочей тугой бредятины. Все просто, ищите и обрящите)

[venco]

InterceptorTSK, во первых, успокойтесь.
Во вторых, ознакомьтесь с темой, прежде чем отвечать. Слово "бинарный" не обязательно связано с битами. Кроме бинарного алгоритма вычисления НОД, могу предложить ещё бинарный поиск и бинарные деревья.
Ну и в третьих, кому вы отвечаете? Автор темы уже 4 года не появляется на форуме.

[InterceptorTSK]

Спокоен как слон) Простите, дату не заметил. Если слово "бинарный" не связано с битовыми операциями, тогда мне похоже в филологи надо уходить) Вообще, по определению "бинарный алгоритм" - любое действие, где есть явное манипулирование битами. Извините, Вы видите здесь признаки манипулирования битами?) Ну кроме как неявное x/2?)) Или же в бинарном поиске и бинарных деревьях не манипулируют битами?)))) Ну тогда я Римский Папа)

[12d3]

InterceptorTSK в сообщении #325450 писал(а):

Или же в бинарном поиске и бинарных деревьях не манипулируют битами?

Ну и покажите, где тут манипулируют битами?

[InterceptorTSK]

Нигде) Именно по-этому это не есть "бинарный алгоритм" в нормальном смысле этого слова))) Ну кто пришет int middle = i + (j - i) / 2??? Руки вырвать по самые ноги((( Операция деления ну крайне медленно работает( Быстрее будет, если писать int middle = i + (j - i) >> 1. Вообще, приведенный по ссылке алгоритм крайне убогий и медленноработающий((

[Cave]

InterceptorTSK
Вы свои домыслы выдаёте за истину, а она не такова. Если бы в промышленном коде, над которым работает одновременно целая группа программистов, все писали в стиле sign = ((a ^ b ^ c) >> 31) | 1, то пополнения кадрами ждать не стоило бы: никто в здравом уме не согласится с нуля разбираться в этом. То, что вы пишете, может иметь место, если разрабатывается глобальная библиотека, крайне требовательная к вычислительной сложности. И то, её разработчики сначала напишут множество тестов, проверят разные варианты и только потом выберут один. Но там сидят люди, которые в этом профессионально разбираются, и там речь идёт не просто об экономии на операции деления пополам. В типичном же случае нужно писать именно так, чтобы по коду было понятно, что он делает. И только если профайлеры докажут, что это место является "тяжёлым" по времени, а нужно работать быстрее, то можно проводить оптимизацию, снабдив её солидным комментарием.
А middle, вообще-то, находится как (i + j) / 2, а не так, как вы написали.

[12d3]

Cave в сообщении #325514 писал(а):

А middle, вообще-то, находится как (i + j) / 2, а не так, как вы написали.

Можно и так, но в случае особо больших массивов будет переполнение, а с i + (j - i)/2 не будет.

[Cave]

12d3 в сообщении #325520 писал(а):

Можно и так, но в случае особо больших массивов будет переполнение, а с i + (j - i)/2 не будет.

Это верно, однако, опять же, это преждевременная оптимизация: массивы должны быть действительно особо большие.
Правда, нужно отметить, что если i, j - итераторы с произвольным доступом, то работать будет только вариант с вычитанием. Впрочем, пока задачи не стоит, нельзя рассуждать, какой способ годится, а какой - нет.

[InterceptorTSK]

О боже, куда я попал((((( (i + j) / 2 есть (i >> 1) + (j >> 1) две атомарных и сумматор работают явно быстрее чем три сумматора и деление((( Ну и пресловутое переполнение исчезает, при условии, конечно же, если сами i, j не переполнены. Как это преждевременная оптимизация? Вы пробовали искать где переполнения?? Мдаааа....
Господа, вопрос стоит конкретный: дайте функцию, которая считает бинарный НОД быстро и качественно. Г-н Cave, я крайне сомневаюсь, что куски высокопроизводительного кода типа нахождения НОД пишет группа "высококвалифицированных" программистов враз, при этом путаясь в собственном коде) Невозможно написать высокопроизводительный код толпой, это факт) Нормальный код пишется в-одного, либо параллельно, но по-сути все равно в-одного.
Затем выбирается лучший вариант. Никто никогда не лезет в чужие строчки, и даже не пытается в них разобраться) Народ пишущий толпой оконный интерфейс - это корректный пример где никогда не будет (global::System.Windows.Forms.Form)obj << 1. Далее, что хитрого в записи sign = ((a ^ b ^ c) >> 31) | 1?? Это есть начальная школа любого нормального и думающего университета. Проблемы с булевкой?) Четыре атомарных операции, выполняющиеся чуть ли не за такт - конечно же это плохо)) Пачка джампов не понять куда летящих несомненно лучше) Есть целая система сокращения записей бинарных операций, коих, заметьте, не так много. Напишите sign = ((a ^ b ^ c) >> 31) | 1, поставьте коммент по типу макроассемблера // MulSgn, ну т.е. MultiSign и будет Вам понимание. (i + j) >> 1 есть коммент Div2. Плюс ко всему, учитывая вышесказанное это понимание нужно только Вам, и никому более) Кто будет читать нутро вашего метода нахождения НОД?))) Высокоскоростных битовых операций, коими несомненно нужно оперировать у меня набралось не более 200, и их не так и много, как хотелось бы. Начните с простого, типа бинарного сравнения, проверки четности, нахождения модуля числа наконец. Это проще чем Вам кажется, уверяю. Получаете производительность крайне близкую к ассемблерной, и при этом ООП остается Вам в полном объеме. При всем при этом не стоит высказывать предположение, что мой код - это мега набор битовых сдвигов) Вовсе нет, пишу как все люди и даже делю на 2) После оптимизирую все что только можно. Про выигрыш в производительности - молчу) Именно оптимизированный бинарный быстрый короткий (уж не знаю уже какие слова подобрать) алгоритм здесь хотели давно, но не получили( Вот и поражает меня ситуация того, что просят одно, а подсовывают другое - вот я о чем(((

[venco]

InterceptorTSK в сообщении #325450 писал(а):

Если слово "бинарный" не связано с битовыми операциями, тогда мне похоже в филологи надо уходить)

Если вы считаете, что каждое слово имеет только одно значение, то вас в филологи точно не возьмут.

InterceptorTSK в сообщении #325450 писал(а):

Вообще, по определению "бинарный алгоритм" - любое действие, где есть явное манипулирование битами.

Нет такого определения.

InterceptorTSK в сообщении #325450 писал(а):

Или же в бинарном поиске и бинарных деревьях не манипулируют битами?))))

Не манипулируют явно. Т.е., в процессоре, конечно, всё - биты, но вы ведь не это имели в виду?

InterceptorTSK в сообщении #325494 писал(а):

Ну кто пришет int middle = i + (j - i) / 2??? Руки вырвать по самые ноги((( Операция деления ну крайне медленно работает(

Вы отстали от прогресса. Современные компиляторы умеют сами использовать сдвиги для умножения и деления на степени двойки.

InterceptorTSK в сообщении #325494 писал(а):

Быстрее будет, если писать int middle = i + (j - i) >> 1.

Быстрее, но неправильней.

InterceptorTSK в сообщении #325539 писал(а):

О боже, куда я попал((((( (i + j) / 2 есть (i >> 1) + (j >> 1)

Мда... Учиться вам ещё и учиться...