Как я могу сделать цикл с> 10 ^ 11 итераций быстрее? - PullRequest
Новая
       23

Как я могу сделать цикл с> 10 ^ 11 итераций быстрее?

0 голосов
/ 15 января 2019

Я пытаюсь реализовать 2 математические функции в JS, однако мне также нужно вызвать S(10**11) % 10**9, что занимает ОЧЕНЬ много времени. Эти функции основаны на двух математических функциях: d(k) S(N) Я попытался просто записать это в свой калькулятор (ti nspire), однако, у него недостаточно памяти, поэтому я написал этот скрипт.

Я действительно не уверен, как я могу оптимизировать это, кроме того, что я уже сделал, или, возможно, решить суммирование, но я не уверен, как это сделать с помощью функции пола. 

function d(k){
    var a = 0;
    for(l=1;l<=k;l++){
        a += Math.floor(1/(1+k%l))*l;
    }
    return a;
}

function S(N){
    var a = 0;
    for(i=1;i<=N;i++){
        for(j=1;j<=N;j++){
            a += d(i*j);
        }
    }
    return a;
}

1 Ответ

0 голосов
/ 16 января 2019

Уравнения могут быть немного упрощены, чтобы облегчить вычисления.

Сначала вам нужно сохранить результаты вашего d (i), чтобы вам никогда не приходилось пересчитывать их. Найти d (i + 1) из d (i) легко, просто используйте

Вторая пара циклов может быть значительно упрощена. Давайте рассмотрим S (5) 

           i
       1     2     3     4     5
    1  d(1) d(2)  d(3)  d(4)   d(5)
    2  d(2) d(4)  d(6)  d(8)  d(10)
  j 3  d(3) d(6)  d(9)  d(12) d(15)
    4  d(4) d(8)  d(12) d(16) d(20)
    5  d(5) d(10) d(15) d(20) d(25)

Мы видим, сколько значений пересчитано. Во-первых, обратите внимание, как матрица симметрична относительно диагонали, давая экономию половины. Есть много других значений, пересчитанных.

Теперь, если мы посмотрим на отдельные члены в d (k). Сначала посмотрите на результаты для mod (k, i) для разных k и i 

        i
     123456789
     ---------
 1 | 0
 2 | 00
 3 | 010
k4 | 0010
 5 | 01210
 6 | 000210
 7 | 0113210
 8 | 00203210
 9 | 010143210

Снова поможет кеширование значений. Деление является относительно дорогой операцией, поэтому определите функцию 

f(m) = floor( 1 / ( 1 + m ) )

и используйте эту функцию с кэшированными результатами при расчете d (k). Собственно давайте посчитаем значения f (m). Теперь f (0) = floor (1/1) = 1. f (1) = floor (1/2) = 0 и для любого m> 1 f (m) = 0.

Это значительно упрощает расчет. Нас в основном интересуют только случаи, когда mod (k, i) = 0. Это время, когда k кратно i.

Таким образом, d (k) - это просто сумма факторов k.

Вместо того, чтобы пытаться найти факторы k, проще взглянуть на множители i. 

for(i=1;i<N;++i) {
    // find multiples of i
    for(j=1;j<???;++j) {
       m = i * j;
       d(m) += i;
    }
 }

Теперь мы выяснили, что d (k) - это сумма факторов k, мы можем упростить вычисления S (N).

В сущности, для данного фактора m мы хотим найти все случаи, когда m является фактором i * j.

Очевидно, 1 является фактором каждого числа, поэтому 1 встречается N N раз. 2 является фактором, если либо i, либо j четно. Произведение i j нечетное N / 2 * N / 2 раза, поэтому четное 3/4 N * N раз. (Я предположил, что N четно)

Для 3, если мы рисуем умножение 

*  1  2  3  4  5  6
1        3        6
2        6       12
3  3  6  9 12 15 18
4       12       24
5       15       30
6  6 12 18 24 30 36

и просто заполните кратные 3. Мы видим, что есть (1 - 2/3 * 2/3) N * N кратных.

Аналогично, с 4 есть (1 - 3/4 * 3/4) N * N кратных.

Таким образом, все становится намного проще, если мы думаем о суммировании числа магазинов.

...