Re: How do you bitwise operations in Ada '83 and '95

["jimmaureenrogers@worldnet.att.net" <jimmaureenrogers@worldnet.att.net>]

Jeffrey R. Carter wrote:
> jimmaureenrogers@worldnet.att.net wrote:
> >
> > Actually it does not work exactly the same. The algorithm is
> > exactly the same, and the same numbers are produced, but the
> > packed array of bits executes faster on my machine by a factor
> > of 3 and uses significantly less space (by a factor of 8).
>
> "The algorithm is the same and the same numbers are produced" = "works
> the same". Performance may differ, but behavior is the same. Since
> performance is a function of many things in addition to the SW, only
> behavior is a meaningful comparison. No doubt there is a
> platform/OS/compiler combination such that the unpacked version would
> run faster than the packed version does on your machine.
>
> > Your definition of bit-wise appears to me to be based upon the
> > desire to use a low level abstraction to access the bits. My
> > definition includes all abstractions that allow access to
> > individual bits.  When I only programmed in C, I only
> > thought of bit-wise access in low level abstractions. Since I
> > have programmed in Ada I think of bit-wise operations in
> > many abstraction levels.
>
> "Bitwise operations" is an inherently low-level concept. At a high
> level, your abstraction is a set. If we treat that as a high-level
> abstraction, then we hide the implementation, and neither bits nor
> Booleans appear in the handling of sets in the main program. An array of
> Booleans, packed or not, is only one possible implementation of a set.
> We could rewrite your program using the ordered-set package from the
> Ada-0X data-structures library and get the same behavior. It would not
> involve any bit-level access, though.

My example was a contribution to the Computer Language Shootout.
The corresponding C code was:

/*
 * The Great Computer Language Shootout
 * http://shootout.alioth.debian.org/
 *
 * Written by Dima Dorfman, 2004
 * Compile: gcc -std=c99 -O2 -o nsieve_bits_gcc nsieve_bits.c
 */

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

typedef uint_fast8_t bits;
#define	NBITS	(CHAR_BIT * sizeof(bits))

static uintmax_t
nsieve(uintmax_t m)
{
	uintmax_t count, i, j;
	bits a[m / NBITS];

	memset(a, (1 << CHAR_BIT) - 1, sizeof(a));
	count = 0;
	for (i = 2; i < m; ++i)
		if (a[i / NBITS] & (1 << i % NBITS)) {
			for (j = i + i; j < m; j += i)
				a[j / NBITS] &= ~(1 << j % NBITS);
			++count;
		}
	return (count);
}

static void
test(unsigned long n)
{
	uintmax_t count, m;

	m = (1 << n) * 10000;
	count = nsieve(m);
	printf("Primes up to %8ju %8ju\n", m, count);
}

int
main(int ac, char **av)
{
	unsigned long n;
	char *cp;

	if (ac < 2) {
usage:		fprintf(stderr, "usage: nsieve N\n");
		exit(2);
	}
	n = strtoul(av[1], &cp, 10);
	if (*av[1] == '\0' || *cp != '\0' || n == ULONG_MAX)
		goto usage;
	test(n);
	if (n >= 1)
		test(n - 1);
	if (n >= 2)
		test(n - 2);
	exit(0);
}

Here you will note that the algorithm is the same as the
Ada version. The bit-wise operations in the nsieve function
are expressed in the manner you described. According to
your analysis, if the algorithm is the same and the results
are the same, the programs are the same. Logic tells me,
therefore, that accessing individual bits of
contiguous storage through an array of boolean in Ada is
a bit-wise operation just as the combination of AND, OR and
shift operations used in the C program.

Jim Rogers