¿Cómo comparar dos multiplicaciones sin realizar la multiplicación?

Question

¿Cómo verificar si dos multiplicaciones son iguales entre sí o mayores o menores sin multiplicarlas en realidad?
Por ejemplo, compara (254)(847) y (383)(536)

EDICIÓN:
Mientras trataba de encontrar una regla, encontré una
(5)(11) < (6)(10)
o
(x)(y) < (x+1)(y-1) cuando y > x > 0
y otra regla es que si sumar y restar 1 los iguala, la diferencia es uno
(3)(5) + 1 = (4)(4)
(x)(y) + 1 = (x+1)(y-1) cuando y + 2 = x , y > x >= 0

Answer 1

Generalmente, tales comparaciones se pueden hacer eficientemente a través de fracciones continuas, por ejemplo:

$$\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$$

La comparación de los coeficientes de fracciones continuas se puede hacer en paralelo con el cálculo de la fracción continua. Es decir, comparar las partes enteras. Si son desiguales, eso determinará la desigualdad. De lo contrario, se hace una recursión en las partes (inversas de) fraccionarias (y se nota que la inversión invierte la desigualdad). Para el ejemplo anterior, esto da como resultado:

$$\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$$

En palabras: para probar si $\rm\:847/383 > 536/254\: $ primero comparamos sus partes enteras (piso). Ambos tienen parte entera $\:2\:$, por lo que restamos $\:2\:$ de ambos y reducimos a comparar sus partes fraccionarias $\rm\ 81/383,\ \ 28/254\:.$ Para hacer esto, las invertimos y hacemos una recursión. Pero dado que la inversión invierte las desigualdades $\rm\ x < y\ \iff\ 1/y < 1/x\ $ (para $\rm\:xy>0\:$), la desigualdad equivalente a probar es si $\rm\ 254/28 > 383/81\:.\ $ Comparando las partes enteras $\rm\:m,\:n\:$ vemos que como $\rm\ m > 5 > n\:$, la desigualdad es verdadera. Esto lleva al siguiente algoritmo simple que compara cualquier par de números reales a través del orden lex de sus coeficientes de fracción continua (nota: no terminará si se dan dos números reales iguales con fracción continua infinita).

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

$\rm\quad\ let\ [\ n_1\leftarrow \lfloor A\rfloor\:;\ \ \ n_2\leftarrow \lfloor B\rfloor\ ] \ \qquad\qquad\quad \color{blue}{\ //\ compara\ partes\ enteras}$

$\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 \color{blue}{//\ calcula\ partes\ fraccionarias\ \ 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})\:;\qquad\qquad \color{blue}{\ //\ \text{recursión sobre inversos de partes fraccionarias}}$

De manera equivalente, se pueden utilizar fracciones de Farey y mediáticas. Generalmente, tales enfoques serán bastante eficientes debido a las propiedades de las mejores aproximaciones del algoritmo. Para un buen ejemplo, vea mi publicación aquí utilizando fracciones continuas para resolver el viejo problema de comparar $\ 7^\sqrt 8\ $ con $\ 8^\sqrt 7\ $ y también vea este hilo donde algunas personas lucharon por demostrar esto por cálculo.

Answer 2

Entonces, quieres comparar (254)(847) y (383)(536) sin calcular realmente los productos, mira a

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

Multiplicando ambos denominadores por 2

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

o

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

Ahora te queda comparar

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

Aplicando el mismo truco que antes, considera

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

El lado izquierdo es obviamente mayor que $2$ mientras que el lado derecho es más pequeño, por lo tanto, puedes concluir que el producto del lado izquierdo original era el más grande, ya que ninguna de las operaciones realizadas invirtió el orden de las desigualdades.

Answer 3

En el peor de los casos, cuando la comparación es cercana, siempre terminarás teniendo que hacer tanto trabajo como la multiplicación. Las mejoras de rendimiento de cualquier mejora que no sea la peor de los casos tendrían que ser bastante buenas para que el esfuerzo de programación valga la pena. ¿Por qué necesitas esto?

Answer 4

Aquí tienes un ejemplo simple que hace el trabajo sin ninguna multiplicación: $5 \times 12$ vs $6 \times 11$, reescribe ambos lados como $5\times(11+1)$ y $(5+1)\times11$, entonces obtenemos $5\times11+5\times1$ vs $5\times11 + 1 \times 11$ restando $5\times11$ de ambos lados obtenemos: $1\times5 vs 1\times11$ lo cual no requiere ninguna multiplicación en absoluto. La misma técnica se puede usar en (254)(847) y (383)(536). $ 254 \times 847 vs 383 \times 536 $
$ 254 \times (536 + 310 ) vs (254+129)\times536$
$ 254 \times 310 vs 129\times536$ continuando de manera similar terminamos con
$125\times 80 vs 4 \times 101$ aunque es obvio pero solo por diversión:
$ (101+24)\times(76+4) vs 4 \times 101$ donde en la siguiente línea obtenemos:
$ 4 \times 101 + 101\times 76 + 24\times76 + 24\times 4 vs 4\times 101 $

Answer 5

¿Utilizar la multiplicación de campesinos rusos? Lo cual simplemente implica sumar y desplazar a la izquierda. Así que en realidad no estás haciendo ninguna multiplicación.