gcd (A1, A2, ...)
вычисляет НОД элементов A1(1), A2(1), ...
. Поскольку элементы хранятся в векторе A
, как вычислить gcd (A)
?
(я имею в виду, что gcd (4, 2, 8) = 2
, gcd ([4, 2, 8]
вызовет ошибку в GNU Octave 4.0.0).
Как вычислить НОД вектора в GNU Octave/Matlab
Ответы (3)
С расширением массива ячеек
Вот однострочный, действительный только в октаве (спасибо nirvana-msu за указание на ограничение Matlab):
A = [10 25 15];
gcd(num2cell(A){:})
# ans = 5
Это использует расширение массива ячеек, которое немного скрыто здесь :
Доступ к нескольким элементам массива ячеек с помощью операторов '{' и '}' приведет к список, разделенный запятыми, всех запрошенных элементов
поэтому здесь A{:}
интерпретируется как A(1), A(2), A(3)
, и, следовательно, gcd(A{:})
как gcd(A(1), A(2), A(3))
Производительность
Еще ниже октавы
A = 3:259;
tic; gcd(num2cell(A){:}); toc
Elapsed time is 0.000228882 seconds.
в то время как с ответом gcd_vect
в @nirvana_msu,
tic; gcd_vect(A); toc
Elapsed time is 0.0184669 seconds.
Это связано с тем, что использование рекурсии подразумевает высокое снижение производительности (по крайней мере, ниже октавы). И на самом деле для более чем 256 элементов в A предел рекурсии исчерпан.
tic; gcd_vect(1:257); toc
<... snipped bunch of errors as ...>
error: evaluating argument list element number 2
error: called from
gcd_vect at line 8 column 13
Это можно значительно улучшить, используя алгоритм "разделяй и властвуй"
В то время как расширение массива ячеек (только октава) хорошо масштабируется:
A = 127:100000;
tic; gcd(num2cell(A){:}); toc
Elapsed time is 0.0537438 seconds.
Алгоритм разделяй и властвуй (лучший)
Этот тоже должен работать под Matlab (хотя и не тестировался. Приветствуются отзывы).
Он также использует рекурсию, как и в других ответах, но с разделяй и властвуй
function g = gcd_array(A)
N = numel(A);
if (mod(N, 2) == 0)
% even number of elements
% separate in two parts of equal length
idx_cut = N / 2;
part1 = A(1:idx_cut);
part2 = A(idx_cut+1:end);
% use standard gcd to compute gcd of pairs
g = gcd(part1(:), part2(:));
if ~ isscalar(g)
% the result was an array, compute its gcd
g = gcd_array(g);
endif
else
% odd number of elements
% separate in one scalar and an array with even number of elements
g = gcd(A(1), gcd_array(A(2:end)));
endif
endfunction
тайминги:
A = 127:100000;
tic; gcd_array(A); toc
Elapsed time is 0.0184278 seconds.
Так что это кажется даже лучше, чем расширение массива ячеек.
gcd
в Matlab требует ровно два входных аргумента.
- person nirvana-msu; 29.05.2016
num2cell(A){:}
не является допустимым синтаксисом Matlab. Matlab не поддерживает динамическое индексирование такого рода, вам придется делать это двумя отдельными вызовами или использовать один из этих уродливые хаки.
- person nirvana-msu; 29.05.2016
octave
.
- person ederag; 29.05.2016
Следующее является грубым, но, похоже, работает на простых примерах.
function g = gcd_array(vals)
if length(vals) == 1
g = vals;
else
g = gcd(vals(1), gcd_array(vals(2:end)));
endif
Обратите внимание, что в отличие от Octave, функция Matlab gcd
требует ровно два входных аргумента. Вы можете использовать рекурсию, чтобы справиться с этим, поскольку gcd(a,b,c) = gcd(a,gcd(b,c))
. Следующая функция принимает оба входных формата — либо один вектор, либо несколько скаляров, и должна работать как в Matlab, так и в Octave:
function divisor = gcd_vect(a, varargin)
if ~isempty(varargin)
a = [a, varargin{:}];
elseif length(a) == 1
divisor = a;
return;
end
divisor = gcd(a(1), gcd_vect(a(2:end)));
end