closed form solution?

[Erik Demaine]

Dear Gabriel,

As I understand it, you're asking for the number of most significant bits
that match between a and b.  To do this in constant time, lookup tables
of size O(U^epsilon) for any epsilon > 0 (e.g., O(sqrt U)) are the best
I know how to do.  If you'll settle for a lg lg U solution, you could
binary search on i.  It's also conceivable that you could do it in time
proportional to the number of 1 bits that match between a and b, which would
be fast if you expect to have more 0's than 1's.

Hope this helps,
Erik
-- 
Erik Demaine  |  edemaine at mit.edu  |  http://db.uwaterloo.ca/~eddemain/

On Thu, 22 Nov 2001, Gabriel Zachmann wrote:

> Dear all,
> 
> does anybody know a closed form solution for the following equation?
> 
>     floor( a * 2^i/U ) = floor( b * 2^i/U )
> 
> where
> 
>     U = 2^d
>     a,b in [0,U-1]
> 
> I am looking for a closed form solution which would return the largest i
> solving the above equation.
> I know of 2 ways which both use some kind of lookup table of hash table,
> but I would prefer the closed form.
> 
> (Remark: you probably have already seen that i is a common ancestor
> of a and b in a binary tree.)
> 
> Thanks a lot in advance for any thoughts, hints, and pointers.
> Gabriel Zachmann.


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.