优化MATLAB代码

此代码需要很长时间才能运行（超过10分钟）。有什么方法可以优化它，以便在不到一分钟内完成？优化MATLAB代码

clear all; 
for i = 1:1000000 
    harmonicsum = 0; 
    lhs = 0; 
    for j = 1:i 
     % compute harmonic sum 
     harmonicsum = harmonicsum + 1/j; 
     % find sum of factors 
     if (mod(i,j)==0) 
      lhs = lhs + j; 
     end 
    end 
    %define right hand side (rhs) of Riemann Hypothesis 
    rhs = harmonicsum + log(harmonicsum) * exp(harmonicsum); 

    if lhs > rhs 
     disp('Hypothesis violated') 
    end 
end

来源

2011-10-03 icobes

关键是不要问“ N“的因素是什么，但是”什么数字有'j作为因素“，这更容易。 –

@b3 has a great vectorization of rhs.

一个错字，就更加需要使用times，而不是mtimes：

harmonicsum = cumsum(1 ./ (1:1e6)); 
rhs = harmonicsum + log(harmonicsum) .* exp(harmonicsum);

对于lhs，我提出以下建议，松散的基础上埃拉托色尼筛：

lhs = 1 + [1:1e6]; 
lhs(1) = 1; 
for iii = 2:numel(lhs)/2 
    lhs(2*iii:iii:end) = lhs(2*iii:iii:end) + iii; 
end;

执行时间只是2.45秒（这个一半的问题）。包括计算rhs和find在内的总计在3秒以内。

我目前正在运行其他版本以确保结果相同。

编辑：发现了一个错误用lhs(1)和特例，它（它是一种特殊的情况下，唯一的自然数，其中1和N是不显着的因素）

来源

2011-10-03 21:29:56

感谢您的错字。在'lhs'计算上干得不错。我认为你需要的只是给整个向量加1。 –

对于谐波总和，我需要把它放在循环内吗？我不遵循你的代码如何为我的每个值做一个和谐总和？ – icobes

@icobes：这是'cumsum'的魔力。请注意'harmonicsum（i）= harmonicsum（i-1）+ 1/i'。 –

内循环执行大约1000000 *（1000000 + 1）/ 2 = 500000500000次！难怪它很慢。也许你应该尝试一种不同的近似方法。

来源

2011-10-03 20:08:25

我不知道如何测试因素，并测试1,000,000数字中的每一个，而不使用双循环。 – icobes

向量化你的算法，我可以将执行时间稍微缩短到〜8.5分钟。计算所有谐波款项在一个声明：

 
harmonicsum = cumsum(1 ./ (1:1e6));

现在可以计算出右侧在一个声明：

 
rhs = harmonicsum + log(harmonicsum) .* exp(harmonicsum);

我无法向量化的因素决定，所以这是我可以用最快的方式来总结它们。 MATLAB的FACTOR命令允许您为每次迭代生成所有素数因子。然后我们使用UNIQUE和NCHOOSEK来计算所有可能组合的唯一产品组。这避免了测试每个整数作为一个因素。

 
lhs = zeros(1e6, 1); 
for ii = 1:1e6 
    primeFactor = factor(ii); 
    numFactor = length(primeFactor); 
    allFactor = []; 
    for jj = 1:numFactor-1 
     allFactor = [allFactor; unique(prod(nchoosek(primeFactor, jj), 2))]; 
    end 
    lhs(ii) = sum(allFactor) + 1 + ii; 
end 
lhs(1) = 1;

寻找在这黎曼假设是违反了指数：

 
isViolated = find(lhs > rhs);

来源

2011-10-03 21:05:23

据我所知，你会得到'lhs（1）'，'lhs（2）'，'lhs（3）'的错误结果，也可能是所有其他的结果。 –

冉从问题的原始代码找到'lhs（1:10）'，我现在匹配，你的不是，不是一个单一的元素:( –

我认为这个问题（除了'ii == 1' case）是'jj == numFactor'产生'ii'本身，这是你分别计算的。将循环改为'jj = 1：numFactor'并且应该更好。 –

优化MATLAB代码

回答

相关问题