# How to Compare two multiplications without multiplying?

How to check if two multiplications are equal to each other or greater or lesser without actually multiplying them?
For example, compare (254)(847) and (383)(536)

EDIT:
While trying to find a rule i got one
(5)(11) < (6)(10)
or
(x)(y) < (x+1)(y-1) when y > x > 0
and another rule is that if adding and subtracting 1 equates them the difference is one
(3)(5) + 1 = (4)(4)
(x)(y) + 1 = (x+1)(y-1) when y + 2 = x , y > x >= 0

-
I'd say add up their logarithms and compare, but that's "mosquito-nuking" territory... –  Ｊ. Ｍ. Dec 14 '10 at 9:01
Approximate each factor with the nearest round number that you can easily perform multiplications with: $(254)(847)\approx(250)(850)=212.500$ and $(383)(536)\approx(400)(550)=220.000$. If the approximation is good, the corrections will be many orders smaller than the estimate and can safely be neglected. Now, since the results are pretty close in this case, I think you'll have to compute the corrections anyway. Another trick would be to write them as $AB=((A+B)^2-A^2-B^2)/2$, maybe this can help. –  Raskolnikov Dec 14 '10 at 10:12
Found another trick, instead of comparing the products, compare $847/383$ and $536/254$. –  Raskolnikov Dec 14 '10 at 12:43
I am preparing for GRE test and it includes many questions like that. In GRE there is no time to multiply and check. Easier way should be a rule. –  LifeH2O Dec 15 '10 at 6:24
@LifeH2O: I know you didn't want to multiply, but if you multiply from the left you get the most significant digits first. You can then stop as soon as you can see the difference. Memorizing special rules is the road to madness. –  Ross Millikan Dec 16 '10 at 0:19

Generally such comparisons can be done efficiently via continued fractions, e.g.

$$\rm\displaystyle a = \frac{847}{383}\ =\ 2 + \cfrac{1}{4 + \cfrac{1}{1 + \cdots}}\ \ \Rightarrow\ \ 2+\frac{1}{4+1} < a < 2+\frac{1}4$$

$$\rm\displaystyle b = \frac{536}{254}\ =\ 2 + \cfrac{1}{9 + \cdots}\ \ \Rightarrow\ \ 2 < b < 2 + \frac{1}9 < 2+\frac{1}5 < a$$

The comparison of the continued fraction coefficients can be done in parallel with the computation of the continued fraction. Namely, compare the integer parts. If they are unequal then that will determine the inequality. Otherwise, recurse on the (inverses of) the fractional parts (and note that inversion reverses the inequality). For the above example this yields:

$$\rm\displaystyle\ \frac{847}{383} > \frac{536}{254}\ \iff\ \frac{81}{383}>\frac{28}{254}\ \iff\ \frac{254}{28}>\frac{383}{81}\ \Leftarrow\ \ 9 > 4$$

In words: to test if $\rm\:847/383 > 536/254\:$ we first compare their integer parts (floor). They both have integer part $\:2\:$ so we subtract $\:2\:$ from both and reduce to comparing their fractional parts $\rm\ 81/383,\ \ 28/254\:.$ To do this we invert them and recurse. But since inversion reverses inequalities $\rm\ x < y\ \iff\ 1/y < 1/x\$ (for $\rm\:xy>0\:$), the equivalent inequality to test is if $\rm\ 254/28 > 383/81\:.\$ Comparing their integer parts $\rm\:m,\:n\:$ we see since $\rm\ m > 5 > n\:$ so the inequality is true. This leads to the following simple algorithm that essentially compares any two real numbers via the lex order of their continued fraction coefficients (note: it will not terminate if given two equal reals with infinite continued fraction).

$\rm compare\_reals\:(A,\: B)\ := \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\color{blue}{\ // \ computes\ \ sgn(A - B) }$

$\rm\quad\ let\ [\ n_1\leftarrow \lfloor A\rfloor\:;\ \ \ n_2\leftarrow \lfloor B\rfloor\ ] \ \quad\quad\quad\quad\quad\quad\ \color{blue}{\ //\ compare\ integer\ parts}$

$\rm\quad\quad if\ \ n_1 \ne n_2\ \ then\ \ return\ \ sgn(n_1 - n_2)\:;$

$\rm\quad\quad let\ [\ a \leftarrow A - n_1\:;\ \ \ b \leftarrow B - n_2\ ] \quad\quad\quad\quad \color{blue}{//\ compute\ fractional\ parts\ \ a,\: b }$

$\rm\quad\quad\quad if\ \ a\:b=0\ \ then\ \ return\ \ sgn(a-b)\:;$

$\rm\quad\quad\quad compare\_reals(b^{-1}\:, a^{-1})\:;\ \quad\quad\quad\quad\quad\quad\color{blue}{\ //\ \text{recurse on inverses of fractional parts}}$

Equivalently one can employ Farey fractions and mediants. Generally such approaches will be quite efficient due to the best approximations properties of the algorithm. For a nice example see my post here using continued fractions to solve the old chestnut of comparing $\ 7^\sqrt 8\$ to $\ 8^\sqrt 7\$ and see also this thread where some folks struggled to prove this by calculus.

-
And how do you calculated that continued fraction? –  LifeH2O Dec 15 '10 at 8:15
It's basically the procedure I show in my reply. –  Raskolnikov Dec 15 '10 at 8:40
@Life: I added details on calculations. –  Bill Dubuque Mar 16 '11 at 19:47
@Ras It was not at all clear to me that your answer is based upon any general algorithm. Nor does it mention continued fractions. It deserves emphasis that such comparisons can be efficiently decided by a simple general algorithm for comparing continued fractions, and that the comparison can be executed in parallel with the on-demand (lazy) computation of the continued fraction coefficients. –  Bill Dubuque Aug 17 '11 at 16:02

So, you want to compare (254)(847) and (383)(536) without actually computing the products, look at

$$\frac{847}{383} \; ? \; \frac{536}{254}$$

Multiplying both denominators by 2

$$\frac{847}{766} \; ? \; \frac{536}{508}$$

or

$$1+\frac{81}{766} \; ? \; 1+\frac{28}{508}$$

You are now left with comparing

$$\frac{81}{766} \; ? \; \frac{28}{508}$$

Applying the same trick as before, consider

$$\frac{81}{28} \; ? \; \frac{766}{508}$$

The left hand side is obviously bigger than $2$ while the right hand side is smaller, therefore, you can conclude that the original left hand side product was the bigger one, since none of the operations performed inverted the order of the inequalities.

-
I'm not sure why you doubled the denominators, and technically that was multiplying. But the general idea is a good one. Instead of the doubling, you could go to 2+81/383 and 2+28/254 and so on. –  Ross Millikan Dec 14 '10 at 13:48
It's the same operation. But, I think when the OP said "without multiplying" he actually meant without computing the actual products given in the question. I could always say that to double, you have just to add the number to itself: tadaah!, no multiplications used. ;) –  Raskolnikov Dec 14 '10 at 13:51
"doubling denominators" is technically dividing by two, if we'll be exceedingly nitpicky. ;) –  Ｊ. Ｍ. Dec 14 '10 at 13:58
This solution does have multiplication involved, Rasolnikov is right, i want a solution with minimal or no calculation like multiply or divide. –  LifeH2O Dec 15 '10 at 8:13

In the worst case, where the comparison is close, you will always end up having to do as much work as multiplication. The performance gains from any non-worst-case improvements would have to be pretty good to make the programming effort worthwhile. Why do you need this?

-

Here is a simple example that does the job without any multiplication: $5 \times 12$ vs $6 \times 11$ , rewrite both sides as $5\times(11+1)$ and $(5+1)\times11$, then we get $5\times11+5\times1$ vs $5\times11 + 1 \times 11$ subtracting $5\times11$ from both sides we get : $1\times5 vs 1\times11$ which does not require any multiplication at all. The same technique can be used on (254)(847) and (383)(536). $254 \times 847 vs 383 \times 536$
$254 \times ( 536 + 310 ) vs (254+129)\times536$
$254 \times 310 vs 129\times536$ continuing in similar fashion we end up with
$125\times 80 vs 4 \times 101$ although obvious but just for fun :
$(101+24)\times(76+4) vs 4 \times 101$ where in the next line we get :
$4 \times 101 + 101\times 76 + 24\times76 + 24\times 4 vs 4\times 101$

-

Use Russian peasant multiplication? Which just involves addition and left-shifting. Then you aren't actually doing any multiplication.

-

Let $(a,b,c,d)$ be a quadruple of positive integers, and let us want to check if $ab=cd$, $ab>cd$ or $ab<cd$. The case when some of the numbers $a,b$ equals some of the numbers $c,d$ is trivial, so let us assume that $a\ne c$, $a\ne d$, $b\ne c$, $b\ne d$. If $a>c$ and $b>d$ then the situation is also trivial, and so is it in the case when $a<c$ and $b<d$. If $a>c$, but $b<d$, then $(a-c,b,c,d-b)$ is a quadruple of positive integers whose sum is less than $a+b+c+d$, and the equality $$(a-c)b-c(d-b)=ab-cd$$ holds. If $a<c$, but $b>d$, then $(a,b-d,c-a,d)$ is a quadruple of positive integers whose sum is less than $a+b+c+d$, and the equality $$a(b-d)-(c-a)d=ab-cd$$ holds. This obviously shows a solution of the problem by an algorithm using only comparing of positive integers and subtracting them in the case of positive difference. The algorithm can be somewhat improved by using that the following two cases are also trivial: the one of $a>d$, $b>c$, and the one of $a<d$, $b<c$ (another reduction similar to the above one can be performed if none of these two cases is present).

Example. Having in mind the initial question in this thread, let us apply the above-mentioned algorithm to the quadruple $(254,847,383,536)$. We get consecutively the quadruples $(254,311,129,536)$, $(125,311,129,225)$, $(125,86,4,225)$, $(121,86,4,139)$, $(117,86,4,53)$, and since $117>4$ and $86>53$, it follows that the product of $254$ and $847$ is greater than the product of $383$ and $536$.

Remark. One can get the result in the above example by means of several shorter sequences of quadruples if sometimes the other reduction possibility is used instead of the one which was described above. Here are some of these sequences:
$(254,311,129,536)$, $(125,311,129,225)$, $(125,86,4,225)$, $(125,82,4,100)$;
$(254,311,129,536)$, $(125,311,129,225)$, $(125,182,129,100)$;
$(254,311,129,536)$, $(254,182,129,282)$, $(125,182,129,100)$;
$(254,464,383,282)$, $(254,182,129,282)$, $(254,53,129,28)$.
The first of them would be actually produced by the transformations done in Arjang's answer from Dec 16'10 after the correction of an error made there (it must be 311 instead of 310).

Problem. Is it possible to design an algorithm using the same primitive operations which compares $x_1x_2...x_n$ and $y_1y_2...y_n$, whenever $n,x_1,x_2,...,x_n,y_1,y_2,...,y_n$ are positive integers?

-