# Given $0 <(x, y) < z < 2^{64}$, How can I compute $\lfloor \frac{xy}{z} \rfloor$ using only 64-bit arithmetic operations?

I can compute this easily in the case that $$xy < 2^{64}$$. But I'm not sure how to do this if $$xy \geq 2^{64}$$.

I know that $$\lfloor \frac{xy}{z} \rfloor = \frac{xy - (xy\ \text{mod} \ z)}{z}$$, but I'm not sure where to go from there.

• What kinds of operation do you allow? For example, do you have multiply-high? – harold Oct 17 '18 at 13:33
• Many processors have an instruction to perform a 64x64 bit multiplication, and a 128 / 64 bit division if the result is less than 2^64. – gnasher729 Oct 17 '18 at 14:46
• I don't have multiply-high. I have multiplication,addition, and subtraction (mod $2^{64}$), flooring division, and modulus. – Dr. John A Zoidberg Oct 17 '18 at 15:35
• I also have min and max, as well as comparisons. – Dr. John A Zoidberg Oct 17 '18 at 15:41

Use two integers to represent one integer. Assume you are using c/c++. You can use a struct that has two long long unsigned integers to represent $$x$$, $$y$$ and $$z$$. So you can express $$x = 2^{32}x_1+x_2$$ with $$x_1$$ being a nonnegative integer smaller than $$2^{32}$$ and $$x_2$$ being a nonnegative integer not greater than $$2^{32}$$. I would assume you will know the rest.

Or you can choose to use some libraries or built-in classes. For example, you can use BigInteger class in Java.

(It goes without saying that you will not have these problems if you were using Python, Ruby, etc.)

• It looks like I was writing too fast. I cannot assume that I know the rest except the most stupid way! I am looking at cs.stackexchange.com/questions/69636/…, gmplib.org/~tege/division-paper.pdf and Java's implementation of BigInteger division. – Apass.Jack Oct 17 '18 at 15:00
• I'm not looking to give my own implementation of larger width integers. I only have the one computation to do, and I'm sure that there's an efficient way to do it with only simple operations. – Dr. John A Zoidberg Oct 17 '18 at 15:37
• Thanks for the clarification. If you have only one computation like that to do for no more than 100 times for a second, then the most stupid way should work fine for you. By the most stupid way, I mean just check whether $2^{127} z<xy$. If yes, subtract that from xy. Then check $2^{126}z <xy$, etc. – Apass.Jack Oct 17 '18 at 16:30
• I don't have a way to compute $xy$ if $xy \geq 2^{64}$. I only have multiplication modulo $2^{64}$. – Dr. John A Zoidberg Oct 17 '18 at 16:57

Split $$x = 2^{32} \cdot x_{hi} + x_{lo}$$, $$y = 2^{32} \cdot y_{hi} + y_{lo}$$. Then

$$x \cdot y = 2^{64} \cdot x_{hi}\cdot y_{hi} + 2^{32} \cdot x_{hi}\cdot y_{lo} + 2^{32} \cdot x_{lo}\cdot y_{hi} + x_{lo}\cdot y_{lo}$$. You can easily calculate each of these products except for the factor $$2^{32}$$ or $$2^{64}$$.

You split the products $$x_{hi}\cdot y_{lo}$$ and $$x_{lo}\cdot y_{hi}$$ into higher and lower 32 bits and add up the components.