closed form solution?
edemaine at mit.edu
Mon Nov 26 20:49:18 PST 2001
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 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 )
> 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
or send mail to compgeom-request at research.bell-labs.com with the line:
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce