Re: As the Crow flies.

On Sun, 19 Oct 2008 09:07:43 -0700 (PDT), Garamond Lethe
<cartographical@xxxxxxxxx> wrote:

On Oct 19, 11:39 am, r norman <r_s_norman@xxxxxxxxxxxx> wrote:
On Sun, 19 Oct 2008 07:53:00 -0700 (PDT), Garamond Lethe

<cartographi...@xxxxxxxxx> wrote:

Something is very strange. Here is my (your) code copied exactly as
compiled.

unsigned long int count_primes(unsigned long int x){
// Uses S. of E. algo to return the number of primes p < x.
unsigned long int p=0, i, j;
char *n = (char*)calloc(x, sizeof(char));
if(!n) return 0;
for(i=2; i<x; i++){
if(!n[i]) for(j=i, p++; i*j<x; n[i*j++]=1);
}
free(n);
return p;

}

int main(void)
{
for (unsigned long int n = 100000; n<=10000000; n *=10)
printf("number of primes below %9ld is %9ld\n",
n, count_primes(n));
return 0;

}

here is my output

number of primes below 100000 is 9592
number of primes below 1000000 is 78493
number of primes below 10000000 is 664214

The first value is correct. The second and third are wrong.

What compiler are you using? Is it C or C++? None of that should
matter but mine is Microsoft Visual Studio 2005 Professional compiling
as C++.

Here's my candidate for the bug:

n[i*j++]=1

If i*j can't fit into a long unsigned int on a 32-bit machine, it'll
wrap to an unexpected value.

Adding

#include <stdint.h>

and changing

unsigned long int p=0, i, j;

to

uint64_t p=0, i, j;

fixes the problem on my 32-bit laptop.

Could you test this on your box? This is a C99-ism (if I remember
correctly). I don't know how to turn that on in Visual Studio.

Thanks for checking this.


That takes care of it. You only need to change i and j; p can remain.

Incidentally, my compiler uses 'unsigned long long' or 'unsigned
__int64'

.

Relevant Pages

  • Re: As the Crow flies.
    ... unsigned long int count_primes{ ... What compiler are you using? ... 32-bit PowerPC, GCC ... number of primes below 100000 is 9592 ...
    (talk.origins)
  • Re: It Pays to Enrich Your C Skills
    ... Check if you can score a perfect 10 (without using a compiler). ... int main{ ... struct bitfield { ... out if it is a negative integer constant or a constant expression ...
    (comp.lang.c.moderated)
  • OT: Re: Perl Peeves
    ... I see the result of a test being used as an int. ... the compiler just assumed you knew what you were doing ... introduced to the language later, so void * was unheard of in most code. ... This didn't mean bool was special, declaring it just signaled to the ...
    (comp.lang.perl.misc)
  • Re: OT: Re: Perl Peeves
    ... when I see the result of a test being used as an int. ... compiler just assumed you knew what you were doing and would ... This didn't mean bool was special, declaring it just signaled to the ... What "normalization of bool results is built into the compiler"? ...
    (comp.lang.perl.misc)
  • Re: [CodeGallery] MFC MD5 Calculator
    ... Then when they added types, internally, the compiler still thought they were int values, ... ANSI standard began to emerge that the language design ...
    (microsoft.public.vc.mfc)