Exponenta Banner
exponenta event banner

GCD

Наибольший общий делитель

свернуть все на странице

Синтаксис

G = gcd (A, B)
[G, U, V] = gcd (A, B)

Описание

пример

G = gcd(A,B) возвращает наибольшие общие делители элементов A и B. Элементы в G всегда неотрицательны, и gcd(0,0) прибыль 0. Этот синтаксис поддерживает входы любого числового типа.

пример

[G,U,V] = gcd(A,B) также возвращает коэффициенты Безо, U и V, которые удовлетворяют: A.*U + B.*V = G. Коэффициенты Безо полезны для решения диофантовых уравнений. Этот синтаксис поддерживает двойные, одинарные и значащие целочисленные входы.

Примеры

свернуть все

Открыть сценарий в реальном времени
A = [-5 17; 10 0];
B = [-15 3; 100 0];
G = gcd(A,B)
G = 2×2

     5     1
    10     0

gcd возвращает положительные значения, даже если входные значения отрицательны.

Открыть сценарий в реальном времени
A = uint16([255 511 15]);
B = uint16([15 127 1023]);
G = gcd(A,B)
G = 1x3 uint16 row vector

   15    1    3
Открыть сценарий в реальном времени

Решите уравнение Диофантина, 30x + 56y = 8 для x и y.

Найти наибольший общий делитель и пару коэффициентов Bézout для 30 и 56.

[g,u,v] = gcd(30,56)
g = 2

u = -13

v = 7

u и v удовлетворить личность Безоута, (30*u) + (56*v) = g.

Перепишите идентичность Безаута так, чтобы она больше походила на исходное уравнение. Сделайте это, умножив на 4. Использовать == для проверки того, что обе стороны уравнения равны.

(30*u*4) + (56*v*4) == g*4
ans = logical
   1

Вычислите значения x и y, которые решают проблему. 

x = u*4
x = -52

y = v*4
y = 28

Входные аргументы

свернуть все

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

  • Если A или B имеет тип single, то другой может быть типа single или double.

  • Если A или B принадлежит целому классу, то другой должен принадлежать к тому же классу или он должен быть double скалярное значение.

A и B должен быть одного размера или скаляра.

Пример: [20 -3 13],[10 6 7]

Пример: int16([100 -30 200]),int16([20 15 9])

Пример: int16([100 -30 200]),20

Типы данных: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

Выходные аргументы

свернуть все

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

Коэффициенты Безо, возвращаемые как массивы вещественных целых значений, удовлетворяющих уравнению, A.*U + B.*V = G. Тип данных U и V является тем же типом, что и тип A и B. Если A и B бывают разных типов, то U и V возвращаются в виде неразрушающего типа.

Алгоритмы

g = gcd(A,B) вычисляется с использованием евклидова алгоритма. [1]

[g,u,v] = gcd(A,B) вычисляется с использованием расширенного евклидова алгоритма. [1]

Ссылки

[1] Кнут, Д. «Алгоритмы A и X». Искусство компьютерного программирования, том 2, раздел 4.5.2. Рединг, Массачусетс: Эддисон-Уэсли, 1973.

Расширенные возможности

Создание кода C/C + +
Создайте код C и C++ с помощью MATLAB ® Coder™

.

См. также

Представлен до R2006a

Документация MATLAB

Поддержка