Cómo verificar el producto de dos enteros largos, digamos que ayb es mayor que c, en C ++ eficientemente

Answer 1

Faltan detalles de la pregunta ahora; en mi respuesta, supondré que básicamente estamos teniendo problemas con el producto de dos largos largos que no encajan en largos largos .

Hay bastantes formas de verificarlo bastante rápido. No tengo puntos de referencia para comparar realmente la velocidad de treir, pero en mi práctica nunca me he enfrentado a una tarea para la que sería un cuello de botella 🙂

Una forma posible es verificar el desbordamiento primero usando double. Digamos que a, b, c son <= 1e18. El siguiente código funcionará bien entonces:

bool check_product (largo largo a, largo largo b, largo largo c)
{
doble prod = a;
prod * = b;
si (prod> 2 * c)
volver verdadero;
devuelve a * b> c;
}

Al hacerlo de esta manera, verá claramente cuando el producto es demasiado grande, y de lo contrario puede verificarlo directamente. Esto se vuelve un poco más complicado en el caso de que a, b, c sean más grandes (por ejemplo, hasta 2 ^ 63–1), pero por lo general, incluso puede usar el simple check in doble largo para tales cosas; usar doble suena arriesgado ya que no es muy preciso.

Otra posibilidad es sustituir la multiplicación con la división:

bool check_product (largo largo a, largo largo b, largo largo c)
{
si (a == 0 || b == 0)
falso retorno;
retorno (c / b <a);
}

No se olvide de la división por 0 😉 Y este código también se vuelve un poco complicado en caso de que tenga números negativos permitidos. Está bien para números no negativos, pero tendré que pensar un poco antes de decirle en qué casos funcionará y en qué casos fallará para los negativos 🙂

Otra opción es usar el tipo de datos que puede manejar números aún mayores. En caso de que su compilador admita __int128 , se vuelve realmente simple:

bool check_product (largo largo a, largo largo b, largo largo c)
{
__int128 res = a;
res * = b;
retorno (res> c);
}

Answer 2

Un truco que aprendí mientras hacía programación competitiva, en lugar de hacer una multiplicación como esta:

si (a * b> c) {
// Hacer cosas
}

hacer esto:

si (a> c / b) {
// Hacer cosas
}

cambiando la ecuación a a> c / b . Como a , byc son todos enteros, a pesar de que el lado derecho tenía una división entera, la relación aún se mantendría.

Editar: como señaló Bohdan Pryshchenko, debe verificar b == 0 antes de hacer la verificación, de lo contrario, se producirá un error de tiempo de ejecución.

Answer 3

Para evitar el desbordamiento, deberá usar long long para todos sus cálculos. Pero incluso entonces, potencialmente tendrá problemas si sizeof(long long) no es al menos 2 * sizeof(long).

comparación de bool (largo a, largo b, largo c)
{
largo producto largo = ((largo largo) a) * ((largo largo) b);
producto devuelto> ((largo largo) c);
}

Los lanzamientos pueden parecer excesivos, pero deja la intención extremadamente clara para el compilador (y el lector).

Veo muchos comentarios en la web sobre cómo hay tamaños mínimos para diferentes tipos de enteros (int 16 bits, largo 32 bits, largo largo 64 bits).

No puedes confiar en ellos.

Acabo de volver a escanear la especificación C ++ 11; no existe tal garantía. La única garantía que puedo encontrar es que sizeof(long long) >= sizeof(long).

Si alguien tiene una referencia al estándar que dice lo contrario, agradecería verlo.

Hay una tabla sobre tipos fundamentales que implica tamaños fijos. Pero la discusión de la página deja en claro que sizeof(char) es el único tipo para el que realmente se especifica un número mínimo de bits.

Si necesita estar seguro del desbordamiento, la función anterior debería reescribirse más de esta manera:

#include

comparación de bool (int32_t a, int32_t b, int32_t c)
{
int64_t product = ((int64_t) a) * ((int64_t) b);
devolver producto> ((int64_t) c);
}