closed form solution?

Erik Demaine edemaine at mit.edu
Mon Nov 26 20:49:18 PST 2001

```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