仅使用奇数除数来计算素数较慢 [英] Calculating primes using only odd divisors is slower

问题描述

我已经编写了一个小的C程序来计算素数，现在尝试尽可能地优化代码.

在程序的第一版中，我正在检查一个数字是否为偶数(模2)，如果是，我将继续到下一个数字.

在我的第二个修订版中，我尝试通过将要检查的数字增加2来仅检查奇数是否为可能的质数(因此我将从3开始，然后依次检查5、7、9、11等).

我认为这样做会更快，因为我用代码削减了模2的额外检查，并简单地用附加代码代替了它. 但是，令我惊讶的是，仅检查奇数的代码在大多数情况下的运行速度要比实现检查所有数字的实现慢一些.

这是代码(它包含我在注释的修订之间所做的更改，无论它说//CHANGE)

#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)
{
    //https://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-prime-number-to-determine-if-it-is-pr
    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版本在被杀死之前找到了更大的质数)

有人知道为什么会这样吗? 最终在代码方面可能出了什么问题?

解决方案

if(!((squareRoot&1)==0))代码比没有测试要慢，因为它很少有好处.

请记住，对于大多数number，由于number%j测试的较早返回，因此从未达到迭代极限.随着number的增长，素数趋于变得稀有.

罕见的额外迭代并不能抵消测试的重复成本.

将!((squareRoot&1)==0)与number%2 ==0进行比较是讨论.

当差异很小时，OP的测试速度方法很容易出错:大多数情况下运行得稍微慢一些"表明不一致.

巨大的时间在printf()中.为了比较主要的计算性能，需要消除I/O.

kill也不那么精确.

相反，当i达到4,000,000,000的值并计时时，形成一个循环以停止.

---

代码还有其他弱点:

由于将number转换为double时的舍入以及sqrt()例程的不精确性，

unsigned long squareRoot = floor(sqrt(number));可能为大number创建错误的根. OP的

---

这里使用全局i是一种较弱的编码样式.建议重新编码并通过函数传递.

---

要获得更多实质性改进，请查看筛网筛网并保留以前找到的列表质数并测试那些而不是所有奇数.

高级测试是一门深入的主题，其中包含许多更高级的思想.

I've written a small C program to calculate primes and now try to optimize the code as far as I can.

In the first revision of the program I was checking if a number was even (modulo 2) and if it was I would continue to the next number.

In my second revision I tried only checking odd numbers to be possible primes by incrementing the number I would be checking by 2 (so I would start from 3, then check 5, then 7, then 9, then 11 etc etc).

I thought this would be way faster as I had cut an extra check for modulo 2 with my code and simply replaced it with an addition. However, to my surprise the code checking only odd numbers, runs a tad bit slower most of the times then the implementation checking all numbers.

Here is the code(it contains the changes I made between revisions in comments wherever it says //CHANGE)

#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)
{
    //https://stackoverflow.com/questions/5811151/why-do-we-check-up-to-the-square-root-of-a-prime-number-to-determine-if-it-is-pr
    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;
}

I'm using Arch Linux x64 with GCC version 8.2.1 and compiling with:

gcc main.c -lm -O3 -o primesearcher

Although I tested with O1 and O2, as well.

I'm "benchmarking" with the command below:

./primesearcher & sleep 10; kill $! 

which runs the program for 10seconds and outputs primes to the terminal for that time and then kills it. I obviously tried allowing the program to run more (30, 60 and 180 seconds) but the results are about 9/10 of the time in favor of the version checking even numbers (modulo 2 version has found a bigger prime before it got killed).

Any idea why would this be happening? Maybe something wrong in terms of code in the end?

解决方案

Code is slower if(!((squareRoot&1)==0)) than with no test because it rarely has benefit.

Keep in mind that for most number, the iteration limit is never reached due to an early return from the number%j test. Primes tend to become rare as number grows.

An rare extra iteration is not offset by the repetitive cost of the test.

Comparing !((squareRoot&1)==0) to number%2 ==0 is moot.

OP's method of testing speed is error prone when differences are small: "runs a tad bit slower most of the times" shows the inconsistency.

A huge amount of time is in the printf(). To compare prime computation performance, I/O needs to be eliminated.

The kill is not that precise either.

Instead, form a loop to stop when i reaches a value like 4,000,000,000 and time that.

---

Code has other weaknesses:

unsigned long squareRoot = floor(sqrt(number)); can creates the wrong root for large number due to rounding when converting number to double and imprecision of the sqrt() routine. OP's reference addresses the mathematical algorithm need. Yet this C code implementation can readily fail given the limitations of real computations.

Instead, suggest

// 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;
}

The cost of number/j is often nil with modern compilers as they see number%j and effectively compute both quotient and remainder at once. Thus the limit of j <= squareRoot is achieved 1) without expensive sqrt() calculation 2) is accurate for large number, unlike sqrt() usage.

---

Use matching specifiers. u, not d for unsigned types.

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

---

Use of a global i here is a weak coding style. Suggest re-coding and pass by function instead.

---

For more substantial improvements, look to Sieve of Eratosthenes and keeping a list of formerly found primes and test those rather than all odd numbers.

Prime testing is a deep subject with many more advanced ideas.

这篇关于仅使用奇数除数来计算素数较慢的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！