Вычисление простых чисел с использованием только нечетных делителей происходит медленнее - PullRequest
Новая
       16

Вычисление простых чисел с использованием только нечетных делителей происходит медленнее

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

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

В первой редакции программы я проверял, было ли число четным (по модулю 2), и если это было так, я бы продолжил к следующему номеру.

Во второй ревизии я пытался проверять только нечетные числа на возможные простые числа, увеличивая число, которое я проверял бы, на 2 (поэтому я начинаю с 3, затем проверяю 5, затем 7, затем 9, затем 11 и т. Д. И т. Д.) .

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

Вот код (он содержит изменения, которые я сделал между ревизиями в комментариях, где бы он ни говорил // ИЗМЕНЕНИЕ) 

#include <stdio.h>
#include <stdbool.h>
#include <math.h>

unsigned long i = 3; //CHANGE No 1 - it was i = 2;

bool hasDivisor(unsigned long number)
{
    ///4565857/pochemu-my-proveryaem-kvadratnyi-koren-iz-prostogo-chisla-chtoby-opredelit-yavlyaetsya-li-ono-prostym
    unsigned long squareRoot = floor(sqrt(number));

    //we don't check for even divisors - we want to check only odd divisors
    //CHANGE No 2 - it was (number%2 ==0)
    if(!((squareRoot&1)==0)) //thought this would boost the speed
    {  
        squareRoot += 1;
    }

    for(unsigned long j=3; j <= squareRoot; j+=2)
    {
        //printf("checking number %ld with %ld \n", number, j);
        if(number%j==0)
        {
            return true;
        }
    }
    return false;
}

int main(int argc, char** argv)
{
    printf("Number 2 is a prime!\n");
    printf("Number 3 is a prime!\n");

    while(true)
    {
        //even numbers can't be primes as they are a multiple of 2
        //so we start with 3 which is odd and contiously add 2
        //that we always check an odd number for primality
        i++; //thought this would boost the speed instead of i +=2;
        i++; //CHANGE No 3 - it was a simple i++ so eg 3 would become 4 and we needed an extra if(i%2==0) here

        //search all odd numbers between 3 and the (odd ceiling) sqrt of our number
        //if there is perfect division somewhere it's not a prime
        if(hasDivisor(i))
        {
            continue;
        }        
        printf("Number %ld is a prime!\n", i);
    }
    return 0;
}

Я использую Arch Linux x64 с GCC версии 8.2.1 и компилирую с: 

gcc main.c -lm -O3 -o primesearcher

Хотя я также тестировал с O1 и O2.

Я "бенчмаркинг" с помощью команды ниже: 

./primesearcher & sleep 10; kill $!

, который запускает программу на 10 секунд и выводит простые числа на терминал в течение этого времени, а затем убивает его. Я, очевидно, пытался позволить программе работать дольше (30, 60 и 180 секунд), но результаты примерно в 9/10 случаев в пользу проверки четности номеров версий (версия по модулю 2 нашла большее простое число, прежде чем ее убили) .

Есть идеи, почему это происходит? Может быть, что-то не так с точки зрения кода в конце?

1 Ответ

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

Код медленнее if(!((squareRoot&1)==0)), чем без теста, потому что он редко дает преимущество.

Имейте в виду, что для большинства number предел итерации никогда не достигается из-за раннего возврата из теста number%j. Простые числа, как правило, становятся редкими по мере роста number.

Редкая дополнительная итерация не компенсируется повторяющейся стоимостью теста.

Сравнение !((squareRoot&1)==0) с number%2 ==0 является спор .

Метод тестирования быстродействия OP подвержен ошибкам, когда различия невелики: «в большинстве случаев он работает чуть медленнее», что свидетельствует о несоответствии.

A огромное количество времени в printf(). Чтобы сравнить производительность вычислений, необходимо исключить операции ввода-вывода.

kill тоже не такой точный.

Вместо этого сформируйте цикл, который останавливается, когда i достигает значения, например, 4 000 000 000 и в этот раз.

У кода есть и другие недостатки:

unsigned long squareRoot = floor(sqrt(number)); может создать неправильный корень для большого number из-за округления при преобразовании number в double и неточности подпрограммы sqrt(). Ссылка OP обращается к математическому алгоритму , необходимому. Тем не менее, эта реализация кода C может легко потерпеть неудачу, учитывая ограничения реальных вычислений.

Вместо этого предложите 

// Prime test for all unsigned long number
bool isPrime(unsigned long number) {
  if (number % 2 == 0) {  // This can be eliminated if `number` is always odd.
    return number == 2;
  }

  for (unsigned long j = 3; j <= number/j; j += 2) {
    if (number%j == 0) {
      return false;
    }
  }

  return number > 2;
}

Стоимость number/j часто равна нулю в современных компиляторах, поскольку они видят number%j и эффективно вычисляют как частное, так и остаток одновременно. Таким образом, предел j <= squareRoot достигается 1) без дорогостоящего sqrt() расчета 2) является точным для большого number, в отличие от sqrt() использования.

Использовать совпадающие спецификаторы. u, а не d для неподписанных типов. 

// printf("Number %ld is a prime!\n", i);
printf("Number %lu is a prime!\n", i);

Использование глобального i здесь является слабым стилем кодирования. Предложите перекодировать и передать вместо функции.

Для более существенных улучшений, посмотрите Сито Эратосфена и ведите список ранее найденных простых чисел и проверьте их, а не все нечетные числа.

Первичное тестирование - глубокий предмет с множеством более продвинутых идей.

...