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.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ What kinds of operation do you allow? For example, do you have multiply-high? $\endgroup$– user555045Commented Oct 17, 2018 at 13:33
-
$\begingroup$ 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. $\endgroup$– gnasher729Commented Oct 17, 2018 at 14:46
-
$\begingroup$ I don't have multiply-high. I have multiplication,addition, and subtraction (mod $2^{64}$), flooring division, and modulus. $\endgroup$– Dr. John A ZoidbergCommented Oct 17, 2018 at 15:35
-
$\begingroup$ I also have min and max, as well as comparisons. $\endgroup$– Dr. John A ZoidbergCommented Oct 17, 2018 at 15:41
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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.)
-
$\begingroup$ 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. $\endgroup$– John L.Commented Oct 17, 2018 at 15:00
-
$\begingroup$ 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. $\endgroup$ Commented Oct 17, 2018 at 15:37
-
$\begingroup$ 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. $\endgroup$– John L.Commented Oct 17, 2018 at 16:30
-
$\begingroup$ I don't have a way to compute $xy$ if $xy \geq 2^{64}$. I only have multiplication modulo $2^{64}$. $\endgroup$ Commented Oct 17, 2018 at 16:57
$\begingroup$
$\endgroup$
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.
