HDTenEightyP/NetNews huggingface dataset:
From: amichail@cayley.waterloo.edu (Amir Michail)
Subject: finding 1st one in integer
Organization: University of Waterloo
Date: Tue, 21 Jul 1992 14:40:26 GMT

I need a very efficient way of finding the first bit set ( doesn't matter
which side ) in a 32 bit integer. 

For example:

  binary  -> position
  	1 -> 0
    10000 -> 4
     1000 -> 3

One can make the simplifying assumption that only 1 bit will be
set in the 32 bit integer (if that helps).

Amir

P.S.  Please do not tell me to use a large lookup table.  I know about that.
      I also know that the 68020 and 80386 have instructions to do this; I want
      portable C code though.
Newsgroups: comp.programming
From: berlin@is.morgan.com (Alexander Berlin)
Subject: Re: finding 1st one in integer
Organization: Morgan Stanley - IS
Date: Tue, 21 Jul 1992 20:57:26 GMT

In article <14hsk4INNke@rodan.UU.NET>, avg@rodan.UU.NET (Vadim Antonov) writes:
|> inline int highbitpos(register int i)
|> {
|> 	register int bitpos = 0;
|> 
|> 	if( i & 0xffff0000 ) {
|> 		i >>= 16;
|> 		bitpos = 16;
|> 	}
|> 	if( i & 0xff00 ) {
|> 		i >>= 8;
|> 		bitpos += 8;
|> 	}
|> 	if( i & 0xf0 ) {
|> 		i >>= 4;
|> 		bitpos += 4;
|> 	}
|> 	bitpos += "\377\0\1\1\2\2\2\2\3\3\3\3\3\3\3\3"[i];
|> 	return bitpos;
|> }
|> 
|> You can speed it up by sacrificing some data space and removing the
|> last _if_. There are variants which do not requre additional register
|> variable or addition at the end (the first makes the code bigger, the
|> second requires replicating the bit tables). All those trade-offs are
|> up to you :-)
|> 
|> --vadim

Vadim, you are assuming Big Endian, aren't you?
The original article asked for PORTABLE code. ">>=" depends on byte order.
---
Alex Berlin                     
berlin@is.morgan.com
Newsgroups: comp.programming
From: pk@cs.tut.fi (Kellom{ki Pertti)
Subject: Spreadsheet data structures
Organization: Tampere Univ. of Technology, Finland.
Distribution: comp
Date: Thu, 30 Jul 1992 07:54:58 GMT

Does anyone know what kind of data structures are used for storing
spreadsheet data? A naive table implementation would have at least two
problems: 

   * either the size of the table is fixed, or you have to do some
     extra work when the user gets outside of the table, and

   * insertion and deletion of rows and columns is costly, partly because of
     copying and partly because of adjusting the formulas.

At least some spreadsheets do seem to work quite a bit when inserting
or deleting.

I've thought about a linked representation like the one used for
sparse matrices. This would allow easy insertion and deletion, and if
you store cell references in formulas as direct references (pointers),
you do not pay extra cost for fetching values from them. The size of
the spreadsheet would also not be fixed.

Any ideas?
--
Pertti Kellom\"aki (TeX format)  #       These opinions are mine, 
  Tampere Univ. of TeXnology     #              ALL MINE !
      Software Systems Lab       #  (but go ahead and use them, if you like)


-- 
Newsgroups: comp.programming
From: ppc1@cec2.wustl.edu (Peter Pui Tak Chiu)
Subject: MAZE
Organization: Washington University, St. Louis Mo.
Date: Thu, 23 Jul 1992 14:57:51 GMT



Hi everyone,

I am trying to write a 3D maze in which the player can move around as if
he/she is "inside" the maze.  (something like the adventure game ULTIMA
when you are inside a dungeon...)

I wrote a version but it is extremely slow.  First I transform the 2D maze
into 3D coordinates.  Then for every move, I redraw the maze with appropriate
transformation, rotations and hidden surface eliminations...  and as you can
tell it takes a lot of TIME!!!

I feel like there MUST be some simple way to do such a thing since when I
played ULTIMA on an APPLE computer a long time ago, it ran pretty fast...

can anyone out there give me a hand???

thank you so much in advance!

Peter
From: peterk@public.sub.org (Peter Kittel)
Newsgroups: comp.programming
Subject: Re: finding 1st one in integer
Date: 22 Jul 92 12:18:59 GMT
Organization: Public News & Mailserver, Commodore Germany PM UNIX, Frankfurt

berlin@is.morgan.com (Alexander Berlin) writes:
>In article <1992Jul21.173805.12045@bcrka451.bnr.ca>, sjm@bcrki65.bnr.ca (Stuart MacMartin) writes:
>|> In article <Brqu3F.1J4@undergrad.math.waterloo.edu>,
>|> amichail@cayley.waterloo.edu (Amir Michail) writes:
>|> > I need a very efficient way of finding the first bit set ( doesn't matter
>|> > which side ) in a 32 bit integer. 
>|> > 
>|> >   binary  -> position
>|> >   	1 -> 0
>|> >     10000 -> 4
>|> >      1000 -> 3
>|> > 
>|> > One can make the simplifying assumption that only 1 bit will be
>|> > set in the 32 bit integer (if that helps).
>|> 
>|> Check a byte at a time for non-zero (being careful not to assume byte
>|> ordering or behaviour of shifting signed values if you want to be portable).

Sounds like a good advice. This makes 4 comparisons in the outer loop.
 
>|> Either use a lookup table of 256 values, or split the byte into two
>|> so that your table is only 16 long.

Why tables? We *have* bit operators in C!
 
>|> If you often have numbers with the 2 lowest bytes clear, you might want to
>|> start by checking 2-byte values against 0.

Or even simpler, as very first action, compare with 65536.
 
>how about this one line solution:

It's a bit slow, I fear, he asked for an *efficient* way.

>unsigned int i;  /* given integer */
>unsigned int j;  /* working variable */
>int          bitset;  /* result */

>   for(j=1, bitset=1; ; bitset++, j+=j) if (i==j) break; /* sets bitset */

And you run the loop from the wrong side, he searches the first bit from
left! So how about this:

if (i>65535)  /* upper or lower 16 bits? */
  { for (bitset=31; bitset>15; bitset--) if (i & (1<<bitset)) break; }
      else
  { for (bitset=15; bitset>=0; bitset--) if (i & (1<<bitset)) break; }

For gaining even more speed you could do more outer if's for bytes and
nibbles and so on, building a binary tree (but can't imagine a simple
loop statement to do this sort of binary search).

-- 
Best regards, Dr. Peter Kittel  // E-Mail to  \\  Only my personal opinions... 
Commodore Frankfurt, Germany  \X/ {uunet|pyramid|rutgers}!cbmvax!cbmger!peterk
                                   or  peterk@public.sub.org
From: dave@cs.arizona.edu (Dave Schaumann)
Newsgroups: comp.programming
Subject: Re: MAZE
Date: 23 Jul 92 21:45:26 GMT
Reply-To: dave@cs.arizona.edu (Dave Schaumann)
Organization: University of Arizona

In article <1992Jul23.145751.29068@wuecl.wustl.edu>, ppc1@cec2 (Peter Pui Tak Chiu) writes:
>I am trying to write a 3D maze in which the player can move around as if
>he/she is "inside" the maze.
>
>I wrote a version but it is extremely slow.  First I transform the 2D maze
>into 3D coordinates.  Then for every move, I redraw the maze with appropriate
>transformation, rotations and hidden surface eliminations...  and as you can
>tell it takes a lot of TIME!!!

From the sound of it, you are processing a lot of information that is never
displayed.  If you think about it, for a reasonable maze, most of it will be
invisible to an internal viewer from any particular viewpoint.  Thus, the
first thing you should do is figure out a quick way to eliminate any structure
that can't possibly be in the view.

A simple algorithm might be:

  Draw the room/segment/whatever that the viewer is in.
  Add any visible doorways/connections to the "door" list

  For each door in the door list
    draw that room, and add its visible doors to the door list

You'll still have to calculate the transformation matrix, but I believe this
algorithm will yield a significant savings over trying to transform &
draw the whole maze.

>thank you so much in advance!

Hope this helps...

-- 
You're traveling through another dimension -- a dimension not only of sight and
sound but of mind. A journey into a wonderous land whose boundaries are that of
imagination.  That's a signpost up ahead: your next stop: the Twilight Zone!
From: rjbodkin@theory.lcs.mit.edu (Ronald Bodkin)
Newsgroups: comp.programming
Subject: Re: 400% makes sense
Date: 25 Jul 92 21:25:46 GMT
Organization: MIT Lab for Computer Science

In article <1992Jul25.184259.20358@a.cs.okstate.edu> norman@a.cs.okstate.edu (Norman Graham) writes:
   Not exactly. 400% is a nonsensical term. Percent (%) means 'per hundred' or
   'of each hundred', and thus is only meaningful for values between 0 and
   100 (inclusive). Percent is best used for absolute measurements, rather
   than relative comparisons such as the above example.

	Rational numbers are defined for values greater than one.
This "argument" is as silly as saying 7/3 makes no sense, because it
is seven thirds, and you cannot have more than three thirds of a
whole.
		Ron
Newsgroups: comp.programming,comp.unix.programmer,alt.msdos.programmer,comp.databases.theory,comp.databases
From: Marc@cbnews.cb.att.com
Subject: Soundex algorithms, database indexing
Organization: AT&T
Date: Wed, 22 Jul 1992 12:28:31 GMT
Followup-To: poster
Keywords: soundex, databases, indexing

Hello programmers/researchers,


	I am going to write a database for a friend of mine who owns a Compact
	disk shop.  This database will contain CD's in stock, minimum stock etc 	etc. Ofcourse it will contain the artist/performers name etc.

	For the latter one I want to set up a soundex key as well.  I have heard	of the soundex algorithm but never seen any pratical applications.

	I would like to get info/ a 'C' program (function) that makes use of
	the Soundex algorithm.

	Also any information on using index files (for fast searching) or
	'C' code would be greatly appreciated.


	Any pointers to soundex/indexing are also welcome.

Erick Otto
AT&T Network Systems
eotto@hvlpa.att.com
eotto@cbnews.att.com

	
Newsgroups: comp.programming
From: atbowler@thinkage.on.ca (Alan Bowler)
Subject: Re: Calculating a cube root
Organization: /etc/organization
Date: Wed, 22 Jul 1992 21:30:49 GMT

The easy way to go is clearly to use the exp + log library routines.
If that is not quite accurate enough for you, run the answer through
a single Newton iteration.   If this is not fast enough, then you
will have to resort to a customized routine.  You may find something
published on cube roots explicitly, or you can certainly look up how to
do a Chebyshev fit of a rational function ( P(x)/Q(x) where P and Q are
polynomials (Remez'z algorithm?)).   In any case the speed will vary
with the machine.  A number of the IEEE standard implementations have
hardware support for exp and log, and it may be impossible to
outperform that.
From: bkottmann@falcon.aamrl.wpafb.af.mil (Brett Kottmann)
Newsgroups: comp.programming
Subject: Algorithm
Date: 20 Jul 92 16:17:03 EST
Organization: Logicon Technical Services, Inc.
Summary: ain't got no soul, either!
Reply-To: exit

	Algorithm has no rhythm.

Brett--------------------------------------------------------------------------
	"Why the courts don't tell a husband who has been living off his wife
to go out and get a job is beyond my comprehension."--Joan Lunden
-------------------------------------------------------------------------------
From: dik@cwi.nl (Dik T. Winter)
Newsgroups: comp.programming
Subject: Re: floating point routines with double precision
Date: 25 Jul 92 02:17:33 GMT
Organization: CWI, Amsterdam

In article <6778@charon.cwi.nl> I wrote:
 >                   IEEE and Cray fall under the conditions,
This was wrong of course.  Due to the bizarre way that the Cray does rounding
they probably do not fall under the condition; but that would require an
extended case study.
-- 
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland
home: bovenover 215, 1025 jn  amsterdam, nederland
dik@cwi.nl
Newsgroups: comp.programming
From: atbowler@thinkage.on.ca (Alan Bowler)
Subject: Re: cleanup on exit (Was Re: Chasing memory leaks: tools, procedures?)
Organization: /etc/organization
Date: Thu, 23 Jul 1992 21:40:34 GMT

In article <NICKEL.92Jul22200234@desaster.cs.tu-berlin.de> nickel@cs.tu-berlin.de writes:
>In article <9220400.530@mulga.cs.mu.OZ.AU> fjh@munta.cs.mu.OZ.AU
>(Fergus James HENDERSON) writes:
>
>> Why not just use at_exit() to install an error handler if necessary?
>
>I would really *like* to use it, but it's not portable. SunOS has a
>function
>
>    int on_exit(procp, arg)
>
>POSIX doesn't define something like this, SysV.3, BSD 4.3, and Ultrix
>don't seem to have somthing like that.
>

ANSI does define atexit().  By induction it is required by POSIX.

Since ANSI and near ANSI systems are becoming very common, this means
use of atexit() is quite portable.  On many older non-ANSI
implementations without atexit() as defined by ANSI, there frequently
is a function like Sun's on_exit(), and in porting to those
environments you can build your own atexit() using on_exit().
Newsgroups: comp.programming
From: sjm@bcrki65.bnr.ca (Stuart MacMartin)
Subject: Re: finding 1st one in integer
Reply-To: sjm@bcrki65.bnr.ca (Stuart MacMartin)
Organization: Bell-Northern Research, Ottawa, Canada
Date: Wed, 22 Jul 1992 14:09:38 GMT

In article <LOWRY.92Jul21165844@rotor.watson.ibm.com>,
lowry@watson.ibm.com (Andy Lowry) writes:
> In article <Brqu3F.1J4@undergrad.math.waterloo.edu>
amichail@cayley.waterloo.edu (Amir Michail) writes:
> 
>  > I need a very efficient way of finding the first bit set ( doesn't matter
>  > which side ) in a 32 bit integer. 
> 
>  > One can make the simplifying assumption that only 1 bit will be
>  > set in the 32 bit integer (if that helps).
> 
> This seems to work nicely:
> 
> int firstone(x)
> unsigned int x;
> {
>   static int keys[] = {
>     -1,  0,  1, 26,  2, 23, 27, -1,  3, 16,
>     24, 30, 28, 11, -1, 13,  4,  7, 17, -1,
>     25, 22, 31, 15, 29, 10, 12,  6, -1, 21,
>     14,  9,  5, 20,  8, 19, 18 };
> 
>   return keys[x % 37];
> }
> 

Very nice.  

The difference between this and the one I (and another) suggested
is that this one relies on only one bit being set, whereas my solution was
more general and did not use the simplifying assumption.  This one ought to
be faster, although the % is slow on some machines.  So the choice really 
comes down to:  do you want to make the simplifying assumption, or are you
going to want to use the same routine later in a case that has more than
one bit set?  This example is so trivial that you would implement both when
needed, but sometimes it is better to write routines slightly more general
than you need if this does not make a *noticeable* difference in performance.

About >>=:   Yes this is portable *if* the value is unsigned.  If the value
is signed, then this might do either logical or arithmetic shifting.

Stuart

: Stuart MacMartin                                    email: sjm@bnr.ca      :
: Bell-Northern Research                              phone: (613) 763-5625  :
: PO Box 3511, Stn C, Ottawa, K1Y-4H7, CANADA    Standard disclaimers apply. :
Newsgroups: comp.programming
From: berlin@is.morgan.com (Alexander Berlin)
Subject: Re: finding 1st one in integer
Organization: Morgan Stanley - IS
Date: Wed, 22 Jul 1992 13:11:51 GMT

In article <1992Jul21.165726@is.morgan.com>, berlin@is.morgan.com (Alexander Berlin) writes:
|> 
|> Vadim, you are assuming Big Endian, aren't you?
|> The original article asked for PORTABLE code. ">>=" depends on byte order.
|> ---
|> Alex Berlin                     
|> berlin@is.morgan.com

As several people pointed, I was wrong here and Vadim's idea will 
perfectly work regardless of byte order for all 32 bit integers.
---
Alex Berlin                     
berlin@is.morgan.com
From: bevan@cs.man.ac.uk (Stephen J Bevan)
Newsgroups: comp.programming
Subject: Re: Chasing memory leaks: tools, procedures?
Date: 21 Jul 92 18:16:07 GMT
	<1992Jul18.203518.14496@murdoch.acc.Virginia.EDU>
	<1992Jul19.160323.8820@organpipe.uug.arizona.edu>
	<NICKEL.92Jul19184631@desaster.cs.tu-berlin.de>
Organization: Department of Computer Science, University of Manchester
In-reply-to: nickel@cs.tu-berlin.de's message of 19 Jul 92 17:46:31 GMT

In article <NICKEL.92Jul19184631@desaster.cs.tu-berlin.de> nickel@cs.tu-berlin.de (Juergen Nickelsen) writes:
   In article <1992Jul19.160323.8820@organpipe.uug.arizona.edu>
   dave@cs.arizona.edu (Dave Schaumann) writes:

   > The definition of new is
   > 
   > #define new(type)  ( (type *)must_alloc(sizeof(type)) )
   > 
   > and must_alloc() is just a function that calls malloc and aborts if malloc
   > returns NULL.

   To make this more useful, must_alloc() should also call some
   cleanup-function. For some application it is a must to have control of
   their termination, e.g. to remove temporary files, re-rename
   temporarily renamed files etc.

Assuming you quit must_malloc with "exit", how about just registering
your procedures with "atexit"?  Alternately, if you really want to
keep the things separate, how about having a malloc specific "atexit"
and allow multiple procedures to be registered?  It seems much more
flexible to me.  Of course then you can have another function which
allows you to remove registered routines (or at least the last defined
one).  And then you can ....  anyone get the feeling exception
handling is being reinvented for the nth time :-)

I've implemented some of the above in my own "must_malloc" variant,
though I didn't go as far as a specific "atexit".  It has a few other
niceties like creating a log file of all (de)allocations so you can
check for leaks in your program.  I can make it available (by mail) if
anybody is interested.

bevan
Newsgroups: comp.programming
From: stumpf@Informatik.TU-Muenchen.DE (Markus Stumpf)
Subject: Re: MAZE
Originator: stumpf@hphalle0.informatik.tu-muenchen.de
Organization: Technische Universitaet Muenchen, Germany
Date: Tue, 28 Jul 1992 16:07:21 GMT


In article <1992Jul23.145751.29068@wuecl.wustl.edu>, ppc1@cec2.wustl.edu (Peter Pui Tak Chiu) writes:
|> I am trying to write a 3D maze in which the player can move around as if
|> he/she is "inside" the maze.  (something like the adventure game ULTIMA
|> when you are inside a dungeon...)
|> 
|> I wrote a version but it is extremely slow.  First I transform the 2D maze
|> into 3D coordinates.  Then for every move, I redraw the maze with appropriate
|> transformation, rotations and hidden surface eliminations...  and as you can
|> tell it takes a lot of TIME!!!

Hmmm, did this in BASIC on a TRS-80 Model I some years ago!
Thats how I solved it:

asume maze is  m * n squares;
the maze layout is saved as a m * n matrix
the values of the single cells are bitwise OR of the following values:
    1 = exit to east
    2 = exit to north
    4 = exit to west
    8 = exit to south

(a way without corners or crossing would eg. have values of 5 (east-west
passage or 10 north-south passage)

Calculate the next square that can be seen by adding/subtracting 1 to the
row/column, depending on which is the current direction the player is looking.

Have some graphics for a way to the left in distance one/two/three/four/...
same for right, wall left, wall right.

Draw the appropiate graphics for each distance.
Stop as soon as row (resp. column) is < 0 or is > m (resp. n),
as soon as you encounter a wall in the direction the player looks or as
soon as you have reached the max distance the player can look (usually
5 cells in Ultima, if I can remember correctly)

Whether there is an exit or a wall to be drawn can be determined by bitwise
ANDing the value of the matrix cell with EAST/NORTH/WEST, that is
(draw exit for xxx if xxx_exit is TRUE, draw a wall for xxx otherwise)

(in C notation:)
left_exit = maze[player_x + distance_x, player_y + distance_y] & EAST;
ahead_exit = maze[player_x + distance_x, player_y + distance_y] & NORTH;
right_exit = maze[player_x + distance_x, player_y + distance_y] & WEST;
/* do not need backward_exit as it can't be seen */

where EAST, WEST, NORTH are set according to

player looks east:
    EAST=8;  NORTH=1;  WEST=2;
player looks north:
    EAST=1;  NORTH=2;  WEST=4;
player looks west:
    EAST=2;  NORTH=4;  WEST=8;
player looks south:
    EAST=4;  NORTH=8;  WEST=1;

Hope that helps and was what you where looking for.

	\Maex

P.S. you can use the values 16, 32, 64 and 128 bitwise to the maxtrix cell
     to indicated something special for that position (trapdoors, boxes ...)
-- 
______________________________________________________________________________
 Markus Stumpf                        Markus.Stumpf@Informatik.TU-Muenchen.DE 
Newsgroups: comp.programming
From: rissel@iscp.bellcore.com (Ron Rissel)
Subject: OCCAM compiler
Reply-To: user@machine.domain
Organization: UC Berkeley XRN Design Team
Distribution: usa
Date: Thu, 23 Jul 92 18:53:23 GMT

Anyone know where to obtain an OCCAM compiler and what operating system it
runs on?
Are there any other OCCAM compilers available and by whom?

Ron
Newsgroups: comp.programming
From: dfs@doe.carleton.ca (David F. Skoll)
Subject: Re: MAZE
Organization: Dept. of Electronics, Carleton University
Date: Thu, 23 Jul 1992 18:11:57 GMT

In <1992Jul23.145751.29068@wuecl.wustl.edu> ppc1@cec2.wustl.edu (Peter
Pui Tak Chiu) writes:

>I am trying to write a 3D maze in which the player can move around as if
>he/she is "inside" the maze.  (something like the adventure game ULTIMA
>when you are inside a dungeon...)

>I wrote a version but it is extremely slow.  First I transform the 2D maze
>into 3D coordinates.  Then for every move, I redraw the maze with appropriate
>transformation, rotations and hidden surface eliminations...  and as you can
>tell it takes a lot of TIME!!!

I assume you mean that the maze itself is 2-D, but you want to see "walls"
as if you're inside the maze.

One technique with which I had great success divided the maze into
grids.  A person occupied a particular grid point.  Then, I did this:

current-grid = player's grid
size = full-screen
blocked = FALSE
shrink-factor = 1.2

while (not blocked)
   draw-view(size, current-grid, player-direction)
   size = size / shrink-factor
   {move one grid in the direction that the player is facing.}
   current-grid = current-grid -> player-direction
   {If you can't move in that direction, stop}
   if (not current-grid) blocked = TRUE
endwhile

The draw-view function simply draws the view of the current cell as
seen from the player's position, leaving a "hole" for the next cell along,
unless the current cell is blocked by a wall.  In that case, draw the wall.

The basic idea is to draw a single cell's view, shrink the size down, and keep
drawing successive cells until a wall blocks the view.  You can also terminate
after a fixed number of cells to limit the distance a player can see.

I hope that's clear!  I implemented this in BASIC on a TRS-80 Color
Computer :-) many moons ago, and it ran very quickly.

--
David F. Skoll
Newsgroups: comp.programming
From: amichail@cayley.waterloo.edu (Amir Michail)
Subject: Re: finding 1st one in integer
Organization: University of Waterloo
Date: Wed, 22 Jul 1992 13:47:38 GMT

In article <LOWRY.92Jul21165844@rotor.watson.ibm.com>, lowry@watson.ibm.com (Andy Lowry) writes:
> This seems to work nicely:
> 
> int firstone(x)
> unsigned int x;
> {
>   static int keys[] = {
>     -1,  0,  1, 26,  2, 23, 27, -1,  3, 16,
>     24, 30, 28, 11, -1, 13,  4,  7, 17, -1,
>     25, 22, 31, 15, 29, 10, 12,  6, -1, 21,
>     14,  9,  5, 20,  8, 19, 18 };
> 
>   return keys[x % 37];
> }
> 

Yes, I thought of this method initially.  The only problem is that the
modulus operation is *VERY* slow on some architectures such as the sparc.
Perhaps there is a simpler hashing function?  I have not been successful
in finding one.

Amir