Распараллеливание факторизации треугольных чисел

Последовательность чисел треугольника генерируется путем сложения натуральных чисел. Таким образом, 7ое число треугольника будет 1+2+3+4+5+6+7 = 28. Первые десять условий будут: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55. Факторы, содержащиеся в первых четырех числах треугольника:

1: 1
3: 1, 3
6: 1, 2, 3, 6
10: 1, 2, 5, 10

Мы видим, что 6 — первое треугольное число, имеющее более четырех делителей.

Чтобы найти первое треугольное число с более чем 500 делителями, я написал следующий код:

s1=0;
s2=0;
A=zeros(1,2);
for i=1:4000
    s1=i+s1;
    s2=0;
    for n=1:s1
        if rem(s1,n)==0
            s2=s2+1;
        end
    end
    if s2>=500
        A=[s1 s2];
        disp(A)
    end
end

Я хотел бы ускорить этот код, используя parfor вместо for во внешнем цикле. Однако я получаю сообщение об ошибке:

Ошибка: переменная s1, возможно, задумана как редукционная переменная, но на самом деле является неинициализированной временной.

См. Parallel for Loops в MATLAB, Временные переменные, предназначенные как переменные сокращения.

Как я могу распараллелить этот код?


matlab performance parallel-processing factors parfor
person KarryMa    schedule 31.07.2019    source источник

Ответы (2)


arrow_upward
6
arrow_downward

Если производительность является проблемой, вы можете использовать этот код:

ii = 1;
while 1
    tn = ii*(ii+1)/2;                  %compute the next triangular number
    fa = factor(tn);                   %prime factorization
    nb = prod(histc(fa,unique(fa))+1); %number of divisor
    if nb > 500
       fprintf('there is %d divisors for %d\n',nb,tn)
       break
    end
    ii = ii+1;
end

И вы обнаружите, что ответ 76576500.

Факторизация простых чисел factor намного быстрее, чем поиск всех делителей с помощью функции divisors.

Таким образом, мы можем вычислить factor(n), который выведет:

x1*n1, x2*n2, x3*n3...

например factor(60) дать:

2 2 3 5

or

2x2,1x3,1x5

  • Существует 3 способа использования простого множителя 2: 2^0, 2^1 или 2^2.
  • Существует 2 способа использования простого множителя 3: 3^0, 3^1
  • Существует 2 способа использования простого множителя 5: 5^0, 5^1

Итак, мы знаем, что 60 имеют 3*2*2 = 12 делителей, потому что простой множитель можно комбинировать 12 различными способами.

person obchardon    schedule 31.07.2019
comment
Я бы добавил к этому ответу время, необходимое для выполнения этого алгоритма (хотя такое время в основном зависит от системы, оно все равно дает некоторое представление). В моей системе это занимает чуть меньше 1 с. - person Dev-iL; 31.07.2019
comment
Хо и я только что обнаружили, что эти составные треугольные числа имеют запись OEIS. - person obchardon; 31.07.2019

arrow_upward
4
arrow_downward

Вы не можете распараллелить это, так как оно рекурсивно: s1 = i + s1.

parfor выполняет ваш цикл в случайном порядке, поэтому неизвестно, какое значение будет иметь s1 на итерации n, так как его значение явно зависит от его значения на итерации n-1.

Вместо того, чтобы выполнять здесь цикл for, я бы выбрал цикл while с условием s2<500. Затем, как только вы преодолеете желаемый порог, ваш цикл остановится, таким образом, вы ограничите количество необходимых итераций до минимума.

Обратите внимание, что parfor — это не волшебная палочка. Накладные расходы на запуск параллельного пула, вероятно, будут больше, чем фактическое время вычисления этого короткого цикла. Прочтите этот вопрос и этот вопрос для получения справочной информации о том, как работает parfor и как написать для него подходящий код.

person Adriaan    schedule 31.07.2019