Jumpstart 
Author Message
 Jumpstart

Newsgroups: comp.lang.oberon
Subject: Jumpstart this group
Summary:
Expires:
Sender:
Followup-To:
Distribution:
Organization: Oberon Liberation Front, Baltimore, MD  USA
Keywords:

Wow, after a flurry of activity, everyone has gone back to
'hunter-gathering'.  This lull in activity must end!  So, here it is, an
attempt to jumpstart this group.

Let's see who can write the most 1) time efficient, 2) space efficient and
3) time & space efficient procedure to reverse the bits in a byte.  All in
Oberon of course.

To start it off, here is my five-minutes-to-write submission (I lose on all
counts!):

PROCEDURE InvertByte(VAR byte : SYSTEM.BYTE);
VAR s, ts : SET; i : LONGINT;
BEGIN
  ts := SYSTEM.VAL(SET, ORD(SYSTEM.VAL(CHAR, byte))) * {0..7};
  s := {}; i := 0;
  WHILE i < 8 DO
    IF i IN ts THEN
      INCL(s, 8 - (i + 1));
    END;
    INC(i);
  END;
  byte := SYSTEM.VAL(SYSTEM.BYTE, s);
END InvertByte;

Anyone care to take 6 minutes and submit a better version?

Lots of non-existant prizes for the winner!

Hey, that reminds me, the person that won the beer never gave me their
address.  I feel like I have reniged on my promise to give a beer away.
Wherever you are, send me you address and favorite beer name so I can
make good on my wager.

Taylor "Disorganized Gambler" Hutt
We are the priests of the temples of Syrinx. Our great computers fill
these hallowed halls.



Mon, 05 Feb 1996 19:00:56 GMT  
 Jumpstart
: Wow, after a flurry of activity, everyone has gone back to
: 'hunter-gathering'.  This lull in activity must end!  So, here it is, an
: attempt to jumpstart this group.

I guess they are "concentrating on the essentials" rather than on
make work projects.

: Let's see who can write the most 1) time efficient, 2) space efficient and
: 3) time & space efficient procedure to reverse the bits in a byte.  All in
: Oberon of course.

  Use a lookup table :

        byte[0] := {};
        byte[1] := {7};
        byte[2] := {6};
        byte[3] := {7,6};
        ..

Whitney



Tue, 06 Feb 1996 09:01:29 GMT  
 Jumpstart
: Wow, after a flurry of activity, everyone has gone back to
: 'hunter-gathering'.  This lull in activity must end!  So, here it is, an
: attempt to jumpstart this group.

: Let's see who can write the most 1) time efficient, 2) space efficient and
: 3) time & space efficient procedure to reverse the bits in a byte.  All in
: Oberon of course.

I'm not a serious Oberon programmer (unless someone will pay me to do it),
instead I program in C (my "hunter-gathering" activity).  I'll put my attempt
in, though.  The following has not been tested, but should work.  It takes
a middle ground; it won't be quite as fast as a straight lookup table but
it won't take up nearly as much memory.  It basically reverses the nibbles
of the byte.  I thought of a clever way to fill up the array of 16
nibble-reversed nibbles, but it took up 15 lines, so I just filled it in one
at a time.  Not too elegent, but reliable.  This algorithm could probably
be used with things larger than bytes, too.

Hopefully the compiler is smart enough to convert DIVs and MODs by 16 with
shifts and ANDs!

Please excuse any blatent and terrible syntax errors; I had no way to compile
it :-(.  It took me more than 6 minutes, too.  It should meet qualifications
2 and 3, though.

MODULE reverser;
  IMPORT SYSTEM;

  VAR nib_reverse : ARRAY 16 OF SHORTINT;

PROCEDURE InvertByte(VAR byte : SYSTEM.BYTE);
VAR bval : SHORTINT;
BEGIN
   bval := byte;
   bval := (nib_reverse[bval MOD 16] * 16) + nib_reverse[bval DIV 16];
   byte := SYSTEM.VAL(SYSTEM.BYTE, bval);
END InvertByte;

BEGIN
   nib_reverse[0] := 0;
   nib_reverse[1] := 8;
   nib_reverse[2] := 4;
   nib_reverse[3] := 12;
   nib_reverse[4] := 2;
   nib_reverse[5] := 10;
   nib_reverse[6] := 6;
   nib_reverse[7] := 14;
   nib_reverse[8] := 1;
   nib_reverse[9] := 9;
   nib_reverse[10] := 5;
   nib_reverse[11] := 13;
   nib_reverse[12] := 3;
   nib_reverse[13] := 11;
   nib_reverse[14] := 7;
   nib_reverse[15] := 15;
END reverser.

Corey



Tue, 06 Feb 1996 11:55:06 GMT  
 Jumpstart

Quote:

>Let's see who can write the most 1) time efficient, 2) space efficient and
>3) time & space efficient procedure to reverse the bits in a byte.  All in
>Oberon of course.

MODULE inv;

VAR
  i,j: INTEGER;
  table: ARRAY [0..255] OF INTEGER;

PROCEDURE invert* (n: INTEGER): INTEGER;
BEGIN
  RETURN table[n]
END invert;

BEGIN
  table[0] := 0; i := 1;
  REPEAT
     j := i;
     REPEAT
       table[i] = 128 DIV j + table[i-j];
       INC (i);
     UNTIL i=j+j;
  UNTIL i=256;
END inv.

I think it is the best solution from any point of view - memory and speed
(I use this for 2 years)

Please notice that it based on following:
   INV(2^k + a) = INV(2^k) + INV(a) = 256/(2^(k+1)) + INV(a) = 128/(2^k)  +
   INV(a) = 2^(7-k) + INV(a)
where 0 < a < 2^k < 256

To eliminate DIV (which is too havy here and to save 1 msc :-)  you  can
use

  table[i] = SHORT (SYSTEM.ASH (1, 7-j)) + table[i-j];

Quote:
>Anyone care to take 6 minutes and submit a better version?

What do you think about solutions from a C world? :-) :-) Just kidding :-)

Quote:
>Lots of non-existant prizes for the winner!

I'm delighted :-)

--
 ----------------------------------------------------------


 Real Time Associates             CompuServe: 71333,2346
 Canning House, 59 Canning Road   Tel: (+44) (0)81 656 7333
 Croydon, Surrey, CRO 6QF, UK     Fax: (+44) (0)81 655 0401
 ----------------------------------------------------------



Mon, 05 Feb 1996 22:27:33 GMT  
 Jumpstart
Taylor noted my laziness. SET can not be assigned to type byte.

:       byte[0] := {};
:       byte[1] := {7};
:       byte[2] := {6};
:       byte[3] := {7,6};

Worse yet is that depends on the bit order of the machine.
ie. {0} is  [0000 0001] or [1000 0000]

MODULE Inv;

VAR tab : ARRAY 256 OF CHAR;

PROCEDURE Inv*( x : CHAR ): CHAR;
BEGIN
        RETURN tab[x];
END Inv;

(*
PROCEDURE BuildTable;
BEGIN
        tab[0] := 0X;
        tab[1] := 080X;
        tab[2] := 040X;
        tab[3] := 0C0X;
        ..
        tab[255] := 0FFX;
END BuildTable;
*)

(* FFT style bit reversal. *)
PROCEDURE BitRev( j1 : INTEGER ):INTEGER;
VAR i, j2, k : INTEGER;
BEGIN
        k := 0;
        i := 0;
        WHILE i < 256 DO
                j2 := j1 DIV 2;
                k := k*2 + (j1-2*j2);
                j1 := j2;
                INC(i)
        END;    
        RETURN k;
END BitRev;

PROCEDURE BuildTable;
VAR k : INTEGER;
BEGIN
        tab[0] := 0;
        k := 1;
        WHILE k < 256 DO
                tab[k] := CHR(BitRev(k));      
                INC(k)
        END;
END BuildTable;

BEGIN BuildTable;
END Inv.



Tue, 06 Feb 1996 21:57:23 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. Looking for Bill Cole from JumpStart !

2. Employment Opportunities with JumpStart Systems Inc.

3. need a jumpstart

4. tkTable jumpstart

5. JumpStart Systems - Retraction

6. JUMPSTART SYSTEMS - Past or Present Financial Dealings

7. >>> NOV 20 NYSUG - JumpStart <<<

8. Jumpstart your New Year! Lose 10 pounds by January 31st

 

 
Powered by phpBB® Forum Software