closed form solution?

Gabriel Zachmann zach at
Thu Nov 22 12:27:13 PST 2001

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.

| Wovon man nicht sprechen kann,                                      |
| darueber muss man schweigen.     (Ludwig Wittgenstein)              |
|                                                                     |
| zach at                 __@/'  Gabriel.Zachmann at |
|    __@/' |

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list