matlab - 在 MATLAB 中找到矩阵的最大公约数

Question

我正在寻找一种方法来划分某个矩阵元素及其最低公约数。

例如，我有向量

[0,0,0; 2,4,2;-2,0,8]

我可以看出最小公约数是2，所以除法后的矩阵就是

[0,0,0;1,2,1;-1,0,4]

可以计算这个的内置方法是什么？

提前致谢

附注我个人不喜欢在这个计算中使用循环，似乎有内置的计算可以执行矩阵元素除法。

Answer 1

既然不喜欢循环，那递归函数呢？

iif = @(varargin) varargin{2 * find([varargin{1:2:end}], 1, 'first')}();
gcdrec=@(v,gcdr) iif(length(v)==1,v, ...
                     v(1)==1,1, ...
                     length(v)==2,@()gcd(v(1),v(2)), ...
                     true,@()gcdr([gcd(v(1),v(2)),v(3:end)],gcdr));
mygcd=@(v)gcdrec(v(:)',gcdrec);

A=[0,0,0; 2,4,2;-2,0,8];
divisor=mygcd(A);
A=A/divisor;

第一个函数 iif 将定义一个内联条件结构。这允许定义递归函数 gcdrec，以找到数组的最大公约数。这iif工作原理如下:它测试第一个参数是否为 true，如果是，则返回第二个参数。否则它会测试第三个参数，如果 that's true，则返回第四个，依此类推。您需要使用 @() 保护递归函数和有时出现在其中的其他量，否则您可能会出错。

使用 iif 递归函数 gcdrec 的工作原理如下:

• 如果输入向量是标量，则返回它
• 否则如果向量的第一个分量是 1，则没有机会恢复，因此它返回 1(允许快速返回大矩阵)
• 否则，如果输入向量的长度为 2，则通过 gcd 返回最大公约数
• 否则它会用一个缩短的向量调用自己，其中前两个元素用它们的最大公约数代替。

函数 mygcd 只是为了方便起见的前端。

应该很快，而且我猜只有递归深度可能是非常大的问题的问题。我使用 A=randi(100,N,N)-50 和 N=100 进行了快速计时检查，以与 @Adriaan 的循环版本进行比较，N=1000 和 N=5000 和 tic/toc。

1. N=100:
   • 循环 0.008 秒
   • 递归 0.002 秒
2. N=1000:
   • 循环0.46秒
   • 递归0.04秒
3. N=5000:
   • 循环 11.8 秒
   • 递归0.6秒

更新:有趣的是，我没有超出递归限制(默认为 500)的唯一原因是我的数据没有公约数。设置一个随机矩阵并将其加倍将导致达到 N=100 的递归限制。所以对于大矩阵，这是行不通的。再一次，对于小矩阵，@Adriaan 的解决方案非常好。

我还尝试在每个递归步骤中将其重写为输入向量的一半:这确实解决了递归限制问题，但它非常慢(N=100< 2 秒，N=1000 为 261 秒)。某处可能有一个中间地带，其中矩阵大小很大(大概)并且运行时还不错，但我还没有找到它。