Более быстрый способ расчета по модулю, когда у вас есть предыдущий ответ? - PullRequest
Новая
       7

Более быстрый способ расчета по модулю, когда у вас есть предыдущий ответ?

0 голосов
/ 21 мая 2018

У меня есть большое количество вычислений по модулю.Базовый расчет выглядит следующим образом: 

const uint64_t start;       // Some "large" number that does NOT change
uint32_t prime[bigNumber];  // Precalculated sequential prime numbers (generated on the fly from a bit compaction storage method for space reasons).
uint64_t answer[bigNumber]; // The "modulo" answers

for (uint64_t i = 0; i < bigNumber; i++) {
   uint32_t factor = prime[i];
   answer[i] = (factor - 1) - ((start - 1) % factor);
}

Примечание: начало, как правило, намного больше, чем простое число [i].

Существует ли более быстрый способ вычисления "ответа" безвыполняя модуль / деление для каждой итерации (AKA может, зная ответ [i - 1], помочь вам быстрее получить ответ [i])?Будем весьма благодарны за любые другие улучшения или предложения.

1 Ответ

0 голосов
/ 23 мая 2018

Я хотел записать частичный ответ в ответ на некоторые из приведенных выше комментариев.Это помогает, делая несколько модов одновременно. 

  if (start < (1ULL << DBL_MANT_DIG)) {
    __m256d div1 = _mm256_broadcastsd_pd(_mm_cvtsi64_sd(_mm_setzero_pd(), start - 1));
    __m128i one  = _mm_set1_epi32(-1);
    __m128i fact = *(__m128i *)(&prime[i]);

    __m256d div2 = _mm256_cvtepi32_pd(fact);

    __m128i rem = _mm256_cvtpd_epi32(_mm256_fnmadd_pd(
                  _mm256_floor_pd(_mm256_div_pd(div1, div2)), div2, div1));

    *(__m256i *)(&answer[i]) = _mm256_cvtepu32_epi64(_mm_sub_epi32(fact,
                               _mm_sub_epi32(rem, one)));
  }

Пожалуйста, прокомментируйте, если у вас есть улучшение этого частичного ответа.

...