Сумма и умножение по модулю

Question

У меня большие числа K, C[1], C[2], C[3] и т. Д., И я должен вычислить b:

b = C[1]*C[2]+C[3]*C[4]+... (mod K)

Теперь я вычисляю полную сумму, а затем делаю что-то вроде

b = SUM % K.

Но это не работает, когда SUM становится больше, чем беззнаковый длинный лимит, поэтому я должен использовать что-то вроде

b = (C[1]*C[2] %K + C[3]*C[4] %K ) %K

Но это отнимает много времени. Я пытался использовать unsigned long long, кроме unsigned long, и это тоже отнимает много времени. Есть ли лучший способ?

UPD:

  C = (unsigned long long int *) malloc(N*sizeof(unsigned long long int));
  unsigned long int i, j, l;
  C[0] = 1;
  for (i=1; i<=N; i++) {
    C[i] = 0;
    l = (unsigned long int) i/2;
    for (j=0; j<l; j++) {
      C[i] += C[j]*C[i-j-1];
      C[i] = C[i] % K;
    }
    C[i] = C[i]*2;
    C[i] = C[i] % K;
    if (i - l*2 == 1) {
      C[i] += C[l]*C[l];
    }
    C[i] = C[i] % K;
  }

Answer 1

по модулю m арифметика - гомоморфизм колец.

скажем, f (x) = x% P, тогда

f (a + b) = f (a) + f (b), а также

f (a * b) = f (a) * f (b).

http://en.wikipedia.org/wiki/Modular_arithmetic

это означает, что вы можете делать мод P после каждого шага.

Answer 2

Для расчета

b = ( C[1]*C[2]+C[3]*C[4]+... ) % P 

вы можете сделать вместо:

b = ( ( (C[1] % P) * (C[2] % P) % P )
    + ( (C[3] % P) * (C[4] % P) % P )
    + ...
    ) % P

Поскольку все операции не будут иметь результатов, превышающих (P-1)^2, я ожидаю, что это будет быстрее, если вы сохраните все промежуточные результаты в переменных с типами как можно меньше.

---

Если число P является какой-то особой формой, например степенью 2, то существуют более быстрые методы.

---

В этом вопросе SO: большие числа в c вы найдете ссылку на GNU Multi-Precision Арифметическая библиотека . Если вам не разрешено использовать такую ​​библиотеку, я думаю, что лучший выбор - это реализовать (подмножество) такую ​​собственную библиотеку.

Вы можете хранить целые числа (больше 2 ^ 64) в массивах и определять функции сложения, умножения, деления и по модулю для таких чисел.

Answer 3

Если вы можете разложить K на попарно относительно простых чисел K ₁ , ..., K _n , то вы можете выполнить вычисления для каждого K _i и объединить результаты в результат для K с помощью китайской теоремы об остатках .Это обычно намного быстрее, особенно если K _i вписывается в машинное слово.