lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


>> but maybe there is a possibility to silence that warning ?

> Suggestions are welcome.

> -- Roberto

The code at the end of this message compiles into 8 to 10 i386
instructions (not counting function entry and exit), using lcc
and gcc; gcc cheerfully inlines it.

It should work on any integer type (I tried it with long long's
and it seemed to work ok.) On 32-bit integers, the test will be
executed a maximum of four times.

Since it has no particular reliance on the shift amount, there is a
reasonable and simple space/time tradeoff; I'd say reducing the shift
size to 5 or 6 would be quite acceptable, as it would rarely exceed
two or three loops anyway.

Just a suggestion :)

By the way, three quibbles about the hashing of numbers in
Lua5 release:

1) Adding 1 to normalise a floating point number means
   that all smallish numbers will hash to the same thing.
   (abs(x)<2^-52). That wouldn't bother me too much, but...
2) It might not work. ANSI does not require that floating
   point numbers be stored in a normalised format. So a
   decimal or hexadecimal floating-point implementation
   (both legal, and at least the second one exists in
   some vaguely common machine) might generate different
   hash values for the same number; furthermore...
3) It is at least conceivable that there is uninitialised
   storage as part of a floating point number. I can't tell
   from Intel´s documentation, for example, whether or not
   storing an 80-bit long double into memory will also clear
   the following 16 bits but I rather doubt it; it certainly
   should not clear the following 32 bits, but those will
   be part of the value if the compiler has been set to
   eight- or sixteen-byte floating alignment (good for
   performance, lousy for compatibility.)

So maybe a religious solution is better :) Although frexp
is in <math.h>, it is highly likely to have been pulled in
to the executable by sprintf, anyway. My suggestion is to
put all of the numerics stuff in a separate file, including
exponentiation, instead of putting all those conditionals
in luser.h; one could just include an integer or floating
point implementation as prefered.

Anyway, here's log2:

#define number long

int log2(unsigned number x) {
  static const char logtab[256] = {
    0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,
    5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
    6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
    6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
  };
  int i, j;
  for (i = -1; j = x & 0xFF, x >>= 8; i += 8) {};
  return i + logtab[j];
}