DDE C Example

Hello,

I’m a budding RISC OS enthusiast, coming to it after searching for a snappy desktop on the Raspberry Pi 1. Raspian’s desktop is just too slow for my hardware.

I bought DDE28 the other day and went through the “Worked Examples.”
I noticed something odd about the Sieve of Erastosthenes C example.

It claims there are 1899 primes below 8190.
But there are only 1027, according to other sources.

So I tried with only 10 primes, and the program gave the wrong answer.
I tried printing out the primes it found, and they seemed to be wrong.

I adjusted the example thusly, and it seems to give the right answer.

#include <stdio.h>

/*
 * Sieve of Erastosthenes.
 */

#define TRUE        1
#define FALSE       0
#define SIZE     8190

static char flags[SIZE+1];

int main(int argc, char *argv[])
{
    unsigned int i, k, count, iter;

    printf("Sieve of Erastosthenes - 100 iterations...");

    for (iter = 1; iter <= 100; iter++) {
        count = 0;

        // Anything more than 1 is a candidate.
        flags[0] = FALSE;
        flags[1] = FALSE;
        for (i = 2; i < SIZE; i++) {
           flags[i] = TRUE;
        }

        // Remove multiples of prime candidates.
        for (i = 0; i < SIZE; i++) {
            if (flags[i]) {
                for (k = i + i; k <= SIZE; k += i) {
                    flags[k] = FALSE;
                }
            }
        }
                 
        // Count the found primes.
        for (i=0; i < SIZE; i++) {
            if (flags[i]) {
                count++;
            }
        }
    }
    printf("\nThere are %u primes less than %u\n", count, SIZE);
    return 0;
}

As this is a benchmark, I left out an apparently well-known optimization:
You only have to go up to sqrt(SIZE) on the second for loop.

Of course, I could be misunderstanding something. But if this is right, I suppose there’s a bug database somewhere. Perhaps best to get a second pair of eyes on it, first. Googling a bit more, I see the original source is also here:

https://www.pcorner.com/list/C/MC212.ZIP/MC-VS-SC.DOC/

… and this also claims 1899 as the correct answer. It says the source came from BYTE, January 1983.

But then there is this, which agrees with my code:
https://primes.utm.edu/nthprime/

Math is not my strong suit, I’m afraid. I see examples claiming each answer is right. The thing that makes me doubt the original is when you actually print out the primes found, or you reduce the SIZE to 10.

If you can shed light on the difference above, I’d appreciate it.

On an unrelated note, the CAPTCHA that is part of signing up for these forums does not work in NetSurf on RISC OS.

But if this is right, I suppose there’s a bug database somewhere.

Firstly, welcome. Always good to see someone new.
Bugs database is at this link

Reporting things here for discussion is always a good idea – it’s what the Bugs forum is for after all.

Math is not my strong suit

+=1, and neither is C. However …

Cribbing from here I derived this, which does “appear” to give right answers for 8190 and 10.

#include <stdio.h>

/*
* Sieve of Erastosthenes - a standard C benchmark.
* Try timing the 100 iterations of counting all primes less than 8190.
* To compile this, use "cc c.sieve"; to run it, just type "sieve".
*/

#define TRUE        1
#define FALSE       0
#define SIZE     8190

static int flags[SIZE+1];

int main(int argc, char *argv[])
{
  unsigned int i, k, count;
  
  printf("Sieve of Erastosthenes");
  
  count = 0;
  for (i = 0; i <= SIZE; i++) flags[i] = TRUE;
  for (i = 2; i <= SIZE; i++) {
    if (flags[i]) {
      for (k = i*i; k <= SIZE; k += i)
      flags[k] = FALSE;
      count++;
    }
  }
  
  printf("\nThere are %u primes less than %u\n", count, SIZE);
  return 0;
}

It returns 1027 primes less than 8190.

To get a second opinion on that being the right answer I tried a Linux tool called primesieve on Ubuntu 18.04

djp@ubuntu:~$ sudo apt-get install primesieve
djp@ubuntu:~$ primesieve 8190
Sieve size = 256 kilobytes
Threads = 1
100%
Primes: 1027
Seconds: 0.000
djp@ubuntu:~$ 

HTH.

Hello.
Whilst I can’t answer the original question I would like to point out that most RISC OS software does not have any test suites to confirm the correctness of the code.

Whilst it takes longer to produce, I now try to develop tests that confirm the code is still correct after I make changes to it.

RISCOS is unfortunately in the dark ages with coding tools.

Ron

Thanks for the replies. To close the loop, I have since found some confirmation that the original program was wrong. Because it was used as a benchmark, few cared that it wasn’t actually an accurate Sieve of Eratosthenes implementation and did not produce an accurate count of primes.

http://www.ziegenbalg.ph-karlsruhe.de/materialien-homepage-jzbg/materials-in-english/Sieve-of-Eratosthenes/The-Sieve-of-Eratosthenes-Text.pdf

Specifically, this:

For years, the renowned computer magazine BYTE used a procedure based on the Sieve of Eratosthenes for so-called benchmark tests, i.e. for testing the speed of hard- and software. Thus, the Sieve of Eratosthenes can be called “classic” in a twofold sense: First, in the original sense of Eratosthenes for generating primes and second, as a benchmark test. The program used by BYTE can easily be implemented in various programming languages. Since BYTE’s version was slightly incorrect as far as the final printout is concerned, it was useful for nothing else but for measuring the run-time on various computer systems.

Guess we’d best leave it, for consistency with the other systems on which it has traditionally been run.

       // Remove multiples of prime candidates.
        for (i = 0; i < SIZE; i++) {
            if (flags[i]) {
                for (k = i + i; k <= SIZE; k += i) {
                    flags[k] = FALSE;
                }
            }
        }

Is C optimising the for loops as it looks correct to me.

The lack of optimisation is on purpose as the intention was to create a slow piece of code that tested memory access speed. David’s example has some optimisation as the inner loop starts at k = i * i, not k = i + i that BYTE uses.

This has me intrigued as I coded up the BYTE suite as a benchmark test in !Si back in ‘89/’90, I’ll have to look at my code to see if its identical.

Hi, Jon.

I didn’t mean to be unclear, the code I posted at the start was my corrected version. The code later posted by David also works.

The code I was saying had a problem was the DDE example at ROOL_DDE28c-FTQC/zip’s Sources.DDE-Examples.C/C++.Sieve.c.Sieve.

That is the code apparently copied from Byte, and has the error.

That code is below. It incorrectly claims there are 1899 primes below 8190, rather than 1027.

#include <stdio.h>

/*
 * Sieve of Erastosthenes - a standard C benchmark.
 * Try timing the 100 iterations of counting all primes less than 8190.
 * To compile this, use "cc c.sieve"; to run it, just type "sieve".
 */

#define TRUE        1
#define FALSE       0
#define SIZE     8190

static char flags[SIZE+1];

int main(int argc, char *argv[])
{
    unsigned int i, prime, k, count, iter;

    printf("Sieve of Erastosthenes - 100 iterations...");

    for (iter = 1; iter <= 100; iter++)
    {   count = 0;
        for (i = 0; i <= SIZE; i++) flags[i] = TRUE;
        for (i = 0; i <= SIZE; i++)
        {   if (flags[i])
            {   prime = i + i + 3;
                for (k = i+prime; k <= SIZE; k += prime)
                    flags[k] = FALSE;
                count++;
            }
        }
    }
    printf("\nThere are %u primes less than %u\n", count, SIZE);
    return 0;
}