David Fedor <[EMAIL PROTECTED]> wrote:
>>> Given a value 2 ^ k, does anyone know how to efficiently extract k
>>> (other than a shift loop?)
>>
>>Use a hash table. n % 19 has no collisions on { 2^k: 0 <= k < 16 },
>>and n % 37 similarly for 0 <= k < 32.
>
> I wonder if that's just efficient source code, instead of fast object code.
> Doing a shift loop can't be that bad, and if you "cheat" by testing the low
> 8 or 16 bits to see if they're zero first, well, we're probably fast enough
> to not care any more.
Hey, I wasn't suggesting that he use that particular hash function, only
that there existed suitably compact tables without collisions. :-)
Sorry to inject some facts into this discussion, but here are some timings
(in seconds) for 1.6 million trials uniformly distributed over 0 <= k < 32
on a Palm V:
157.69 n % 37 hash table
104.93 shift loop
70.56 shift loop with 16 bit "cheating"
So it's true that that particular constant time hash table sucks. (Although
my first few tests were pretty exciting and had n%37 beating the cheater by
20%... until I remembered to turn the optimizer on!)
The shift loop solutions are O(number of bits). It's possible to reduce
that to O(log(number of bits)) by recursively applying David's "cheat":
43.05 decision tree
> I always love O(1) algorithms but they're not necessarily the fastest!
But,
YOU CAN STILL DO BETTER WITH A CONSTANT TIME HASH TABLE!
If you're insane enough.
It's true that it's difficult to think of a function other than % to reduce
the size of the table: powers of two are a difficult input set. What you'd
really like is to do it with a big table of random numbers, but you don't
want to store them youself. The solution is to use the ROM! It's easy
enough to find a 64K block in any given ROM where the bytes at offsets
1, 2, 4, 8, ..., 32768 are all different, and use that to index a 256 entry
hash table; effectively you're feeding one hash table to another. (64K is
enough if you use one iteration of "cheating".)
40.45 crazy rom hash table
But I guess for the sake of three seconds it's not really worth it. :-)
John "is it Friday yet?" "where's Bob when you need him? :-)"
--
For information on using the Palm Developer Forums, or to unsubscribe, please see
http://www.palmos.com/dev/tech/support/forums/
