Re: Data types (was: Re: Access the neighbors of an element)

[Paul Kienzle]

John,

We can do better than converting to double.

For unsigned add/subtract operations we can get a big speedup using the
following test:

        z = x+y; if (z < x) z = MX;
    z = x-y; if (z > x) z = 0;

For unsigned multiplication of 8, 16 or 32 bits we can use:

    p = (widertype)x * (widertype)y;
    z = (p > MX ? MX : p);

For 64 bit unsigned multiplication we can use:

  #define LO 0xFFFFFFFFUL
  #define HALF 32
  if ((x > LO && (y > LO || (x>>HALF)*y > LO)) || (y>LO && (y>>HALF)*x 
> LO))
    z = MX;
  else z = x * y;

For 8, 16 or 32 bit signed operations we can use:

   p = (widertype)x OP (widertype)y;
   z = (p > MX ? MX : p < MN ? MN : p);

64 bit signed add/subtract operations will be a little more work.  Maybe
something like the following:

   z = x+y;
   if (x>0 && y>0 && z<x) z = MX;
   else if (x<0 && y<0 && z>x) z = MN;
   z = x-y;
   if (x>0 && y<0 && z<x) z = MX;
   else if (x<0 && y>0 && z>x) z = MN;

64 bit signed multiply is harder still.  Maybe:

   absx = x<0?-x:x;
   absy = y<0?-y:y;
   if ((absx > LO && (absy > LO || (absx>>HALF)*absy > LO))
        || (absy>LO && (absy>>HALF)*absx > LO))
      z =  ((absx == x) != (absy == y) ? MN : MX);
   else z = x * y;

Using assembler would be even faster, but then portability and 
maintenance
get much harder.  How much faster does it have to be to be worthwhile?

I'm attaching the test program I used for timing the unsigned ops on 
PPC.

Someone who uses these operations can turn these ideas into a proper
patch for octave.  Do more extensive testing of the saturation
conditions than I did before submitting.

- Paul

uint.c
Description: Text document