memset and bool

So, I was trying a primality test program using good old C to have some retro feeling. Got burnt very bad with the memset.

Jut to jog your memory, memset accepts following parameters:
ptr -Pointer to the block of memory to fill.
value -Value to be set. The value is passed as an int, but the function fills the block of memory using the unsigned char conversion of this value.
num -Number of bytes to be set to the value.

More details here: http://www.cplusplus.com/reference/cstring/memset/

What I wanted to do is set an array with true. As you might be aware that C standards earlier to C98 (C89 etc.) didn’t had any bool type. So I created an enum version of it.

typedef enum
{
false,
true=!false
} bool;

What I forgot, is that enum by default using storage space equivalent to int. So when I tried to initialize my array as following:

memset(prime, true, sizeof(prime));

It bombed!
What the array contained 16843009 for all its element.
Now,  16843009 = (01010101)16. So clearly, what memset did was to copy 1 repeatedly to each byte of the integer array element (which was of 4 bytes on my machine).

Is using C98 with stdbool header the right answer?
It mostly is. But, like other data types, C doesn’t set an upper bound to bool’s size. All it guarantees it to be not smaller than byte (GCC defies_Bool as 1 byte). But it could be anything larger. So, the GERD continues.
*Note: Safest way is to loop through the array to set it’s value.

Primality test using 6k-1/6k+1 and sieve of eratosthenes

Had some fun in re-trying few methods of finding primes numbers after long time.

(uses C98)

Github: https://github.com/dheerajsuthar/revisitingc

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdbool.h>

// If bool not present (pre C98). 
// Warning: causes issue with memset as default enum size is int.
// typedef enum
// {
//     false,
//     true = !false
// } bool;
bool isPrime(int n);
void sieve_of_eratoshenes(int n);

int main()
{
    int MAX = 10;
    printf("Primes upto %d using 6k+1/6k-1 method:\n", MAX);
    for (int i = 0; i <= MAX; i++)
    {
        if (isPrime(i))
            printf("%d\n", i);
    }
    printf("Primes upto %d using sieve of eratosthenes method:\n", MAX);
    sieve_of_eratoshenes(MAX);
}

bool isPrime(int n)
{
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    int i = 5;
    while (i * i <= n)
    {
        assert(i < n);
        // because we started from 5
        // so its 5,7, 11, 13 ...
        // note: 6k+1/6k-1 method is not inverse, all primes are of this type but
        // inverse is not true. e.g. 35,25
        if (n % i == 0 || n % (i + 2) == 0)
        {
            return false;
        }
        i += 6;
    }
}

void sieve_of_eratoshenes(int n)
{
    if (n <= 1)
        return;
    bool prime[n + 1];
    // be careful with it. For anything else than byte it gives burn (1-> 16843009)
    memset(prime, true, sizeof(prime));

    for (int i = 2; i * i <= n; i++)
    {
        if (prime[i] == true)
        {
            for (int j = 2*i; j <= n; j += i)
            {
                prime[j] = false;
            }
        }
    }

    for (int i = 2; i <= n; i++)
    {
        if (prime[i])
            printf("%d\n", i);
    }
}

 

 

Hello Blog!

Get the blog running

Tools Used:

Google Compute Engine
Wordpress
Awesome Free SSL service provided by www.sslforfree.com
TODO: Quick tutorial on forwarding domain from Goddady to Google Cloud.