Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!rutgers!mcnc!rti!trt
From: trt@rti.UUCP (Thomas Truscott)
Newsgroups: comp.lang.c
Subject: Re: sqroot of a 2**n number ?
Summary: Table look up works well
Message-ID: <2955@rti.UUCP>
Date: 15 May 89 04:04:18 GMT
References: <1906@yunexus.UUCP> <1094@atanasoff.cs.iastate.edu>
Organization: Research Triangle Institute, RTP, NC
Lines: 36

> In article <1906@yunexus.UUCP> oz@yunexus.UUCP (Ozan Yigit) writes:
> >given any number that is an exact power of two, finding the square
> >root: this can be done by counting to the bit position on some
> >architectures. Does anyone know of a really portable version of this ...

I believe the following is portable code:
	/* "n" is type "int", exact positive power of two */
	int i;
	for (i = 0; (1<<i) != n; i++)
		;
	/* "i" is now lg2(n), to get square root we do: */
	sqrt_n = 1 << (i/2);
	if ((i%2) != 0)		/* odd power-of-two */
		sqrt_n *= sqrt(2.0);	/* oops! need sqrt after all */

Portability and performance sometimes clash,
and I think this problem is an example.
Typical C machines only support 31 different exact powers of two
(2^i, 0 <= i <= 30) which suggests a table look up:

unsigned char lg2_hashtable[] = {
	0,0,1,26,2,23,27,0,3,16,24,30,28,11,0,13,4,7,17,
	0,25,22,0,15,29,10,12,6,0,21,14,9,5,20,8,19,18,0,
};
#define lg2(twotoN) lg2_hashtable[(twotoN)%(37)]

I generated this with a simple program.
The problem is: this code is not portable!
We could build a slightly bigger table, to handle "64-bit" ints,
but it would be slightly slower and *still* be unportable
(to a machine with 144-bit integers, for example).
We could generate the table at runtime,
but (a) it would have to be allocated dynamically,
(b) it would be tricky to generate it portably,
and (c) there would be a bigger-yet performance hit.
	Tom Truscott