From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Thread: 103376,553a6b79b2471571
X-Google-Attributes: gid103376,public
X-Google-Language: ENGLISH,ASCII-7-bit
Path: 
 g2news2.google.com!postnews.google.com!75g2000cwc.googlegroups.com!not-for-mail
From: "jimmaureenrogers@worldnet.att.net" <jimmaureenrogers@worldnet.att.net>
Newsgroups: comp.lang.ada
Subject: Re: How do you bitwise operations in Ada '83 and '95
Date: 19 Jul 2006 06:05:04 -0700
Organization: http://groups.google.com
Message-ID: <1153314304.534739.178430@75g2000cwc.googlegroups.com>
References: <1153244316.853254.291560@m79g2000cwm.googlegroups.com>
   <1153248800.834457.183940@p79g2000cwp.googlegroups.com>
   <jyavg.85502$1i1.74539@attbi_s72>
   <1153258362.266358.15200@h48g2000cwc.googlegroups.com>
   <Wbfvg.85833$1i1.47753@attbi_s72>
   <1153281313.491512.88760@75g2000cwc.googlegroups.com>
   <DGivg.844752$084.196149@attbi_s22>
NNTP-Posting-Host: 69.170.65.169
Mime-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
X-Trace: posting.google.com 1153314308 27267 127.0.0.1 (19 Jul 2006 13:05:08
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Wed, 19 Jul 2006 13:05:08 +0000 (UTC)
User-Agent: G2/0.2
X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US;
 rv:1.8.0.4) Gecko/20060508 Firefox/1.5.0.4,gzip(gfe),gzip(gfe)
Complaints-To: groups-abuse@google.com
Injection-Info: 75g2000cwc.googlegroups.com; posting-host=69.170.65.169;
   posting-account=SqOfxAwAAAAkL81YAPGH1JdBwpUXw9ZG
Xref: g2news2.google.com comp.lang.ada:5807
Date: 2006-07-19T06:05:04-07:00
List-Id: <comp.lang.ada>

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