0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What kinds of operation do you allow? For example, do you have multiply-high? $\endgroup$ – harold Oct 17 '18 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$ – gnasher729 Oct 17 '18 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 Zoidberg Oct 17 '18 at 15:35
  • $\begingroup$ I also have min and max, as well as comparisons. $\endgroup$ – Dr. John A Zoidberg Oct 17 '18 at 15:41
1
$\begingroup$

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.)

$\endgroup$
  • $\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$ – Apass.Jack Oct 17 '18 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$ – Dr. John A Zoidberg Oct 17 '18 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$ – Apass.Jack Oct 17 '18 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$ – Dr. John A Zoidberg Oct 17 '18 at 16:57
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.