how - call c from c++

La forma más segura y eficiente de calcular una operación de entero que puede desbordar

Question

Supongamos que tenemos 2 constantes A y B y una variable i , todos los enteros de 64 bits. Y queremos calcular una simple operación aritmética común como:

i * A / B (1)

Para simplificar el problema, supongamos que la variable i siempre está en el rango [INT64_MIN*B/A, INT64_MAX*B/A] , de modo que el resultado final de la operación aritmética (1) no se desborda (es decir, encaja en el rango [INT64_MIN, INT64_MAX] ).

Además, se supone que i es más probable en el rango amigable Rango 1 = [INT64_MIN/A, INT64_MAX/A] (es decir, cerca de 0), sin embargo, puedo (menos probable) estar fuera de este rango. En el primer caso, un cálculo de enteros trivial de i * A no se desbordaría (por eso llamamos el rango amigable ); y en el último caso, se desbordaría un cálculo trivial de enteros de i * A , lo que llevaría a un resultado erróneo en el cálculo de (1).

¿Cuál sería la forma "más segura" y "más eficiente" de computar la operación (1) (donde "más seguro" significa: preservar la exactitud o al menos una precisión decente, y donde "más eficiente" significa: el tiempo de cálculo promedio más bajo), siempre que i es más probable en el rango amistoso Range1 .

En este momento, la solución actualmente implementada en el código es la siguiente:

(int64_t)((double)A / B * i)

La solución es bastante segura (sin desbordamiento), aunque inexacta (pérdida de precisión debida a una doble significación de 53 bits) y bastante rápida porque la división (double)A / B se calcula previamente en tiempo de compilación, lo que permite calcular solo una multiplicación doble en tiempo de ejecución .

Answer 1

Algunas implementaciones permiten __int128_t . Verifique si su implementación lo permite, para que pueda usarlo como marcador de posición en lugar de double . Consulte la siguiente publicación:
¿Por qué no hay int128_t?

Si no estoy muy preocupado por la "rapidez", entonces para una buena portabilidad sugeriría usar la biblioteca de C ++ "InfInt" solo para el encabezado.

Es bastante sencillo utilizar la biblioteca. Simplemente cree una instancia de la clase InfInt y comience a usarla:

InfInt myint1 = "15432154865413186646848435184100510168404641560358";
InfInt myint2 = 156341300544608LL;
myint1 *= --myint2 - 3;
std::cout << myint1 << std::endl;

Answer 2

Con el fin de proporcionar una respuesta cuantificada a la pregunta, hice un punto de referencia de diferentes soluciones como parte de las propuestas aquí en este post (gracias a los comentarios y respuestas).

El punto de referencia mide el tiempo de cálculo de diferentes implementaciones, cuando i está dentro del rango amigable Range1 = [INT64_MIN/A, INT64_MAX/A] , y cuando i está fuera del rango amigable (aún dentro del rango seguro Range2 = [INT64_MIN*B/A, INT64_MAX*B/A] ).

Cada implementación realiza un cálculo "seguro" (es decir, sin desbordamiento) de la operación: i * A / B (excepto la primera implementación, dada como tiempo de cálculo de referencia). Sin embargo, algunas implementaciones pueden devolver resultados de cálculo inexactos poco frecuentes (comportamiento que se notifica).

Algunas soluciones propuestas no se han probado o no se enumeran a continuación; estos son: la solución que usa __int128 (no compatible con el compilador ms vc), pero en su int128_t se ha utilizado el impulso int128_t ; soluciones que utilizan long double bit extendido de 80 bits (no compatible con el compilador ms vc); solución utilizando InfInt (funciona y se prueba, aunque es demasiado lento para ser un competidor decente).

Las mediciones de tiempo se especifican en ps / op (picosegundos por operación). La plataforma Benchmark es un Intel Q6600 @ 3GHz bajo Windows 7 x64, ejecutable compilado con MS vc14, x64 / Release target. Las variables, constantes y funciones a las que se hace referencia a continuación se definen como:

int64_t i;
const int64_t A = 1234567891;
const int64_t B = 4321987;
inline bool in_safe_range(int64_t i) { return (INT64_MIN/A <= i) && (i <= INT64_MAX/A); }

1. (i * A / B) [referencia]
   i en Range1 : 1469 ps / op , i fuera de Range1 : irrelevante (desbordamientos)
   
2. ((int64_t)((double)i * A / B))
   i en Range1 : 10613 ps / op , i fuera de Range1 : 10606 ps / op
   Nota: resultado impreciso poco frecuente (error máximo = 1 bit) en todo el rango Rango2
   
3. ((int64_t)((double)A / B * i))
   i en Range1 : 1073 ps / op , i fuera de Range1 : 1071 ps / op
   Nota: resultado impreciso poco frecuente (error máximo = 1 bit) en todo el rango Rango2
   Nota: es probable que el compilador precomputa (double)A / B resulta en el aumento de rendimiento observado frente a la solución anterior.
   
4. (!in_safe_range(i) ? (int64_t)((double)A / B * i) : (i * A / B))
   i en Range1 : 2009 ps / op , i fuera de Range1 : 1606 ps / op
   Nota: raro resultado inexacto (error máximo = 1 bit) fuera de Rango1
   
5. ((int64_t)((int128_t)i * A / B)) [boost int128_t ]
   i en Range1 : 89924 ps / op , i fuera de Range1 : 89289 ps / op
   Nota: boost int128_t tiene un int128_t espectacular en la plataforma del banco (no tengo idea de por qué)
   
6. ((i / B) * A + ((i % B) * A) / B)
   i en Range1 : 5876 ps / op , i fuera de Range1 : 5879 ps / op
   
7. (!in_safe_range(i) ? ((i / B) * A + ((i % B) * A) / B) : (i * A / B))
   i en Range1 : 1999 ps / op , i fuera de Range1 : 6135 ps / op
   

Conclusión
a) Si los errores de cálculo leves son aceptables en todo el rango Rango 2 , entonces la solución (3) es la más rápida, incluso más rápida que el cálculo de entero directo dado como referencia.
b) Si los errores de cálculo son inaceptables en el rango amigable Rango 1 , pero son aceptables fuera de este rango, entonces la solución (4) es la más rápida.
c) Si los errores de cálculo son inaceptables en todo el rango Rango2 , entonces la solución (7) funciona tan bien como la solución (4) en el rango amigable Rango 1 , y permanece bastante rápido fuera de este rango.

Answer 3

Creo que puedes detectar el desbordamiento antes de que suceda. En su caso de i * A / B , solo le preocupa la parte i * A porque la división no puede desbordarse.

Puede detectar el desbordamiento realizando una prueba de bool overflow = i > INT64_MAX / A Tendrá que modificar esto según el signo de los operandos y el resultado.

Answer 4

No estoy seguro de los límites de valor, ¿ayudará (i / B) * A + (i % B) * A / B ?

Answer 5

Si no puede obtener mejores límites en los rangos involucrados, es mejor seguir los consejos de __int128 para usar __int128 .

La razón es que, de lo contrario, tendría que implementar la lógica completa de la palabra en la multiplicación de palabras dobles y en la división de palabra por palabra. Los manuales de los procesadores Intel y AMD contienen información útil y código ya hecho, pero se involucran bastante, y el uso de C / C ++ en lugar de en ensamblador hace que las cosas sean doblemente complicadas.

Todos los buenos compiladores exponen a los primitivos útiles como intrínsecos. La lista de Microsoft no parece incluir una primitiva similar a muldiv, pero el intrínseco __mul128 le da las dos mitades del producto de 128 bits como dos enteros de 64 bits. En base a eso, puede realizar una división larga de dos dígitos por un dígito, donde un ''dígito'' sería un entero de 64 bits (generalmente denominado ''extremidad'' porque es más grande que un dígito pero aún es solo una parte del todo). Todavía muy involucrado, pero mucho mejor que usar C / C ++ puro. Sin embargo, en cuanto a la portabilidad, no es mejor que usar __int128 directamente. Al menos de esa manera, los implementadores del compilador ya han hecho todo el trabajo duro por usted.

Si su dominio de aplicación le puede dar límites útiles, así (u % d) * v no se desbordará, entonces puede usar la identidad

(u * v) / d = (u / d) * v + ((u % d) * v) / d

donde / significa división entera, siempre y cuando u no sea negativo yd sea positivo (de lo contrario, podría estar en conflicto con el margen de maniobra permitido para la semántica del operador % ).

En cualquier caso, es posible que tenga que separar los signos de los operandos y utilizar operaciones no firmadas para encontrar mecanismos más útiles que pueda explotar, o para evitar el sabotaje del compilador, como la multiplicación de saturación que mencionó. El desbordamiento de operaciones enteras con signo invoca un comportamiento indefinido, los compiladores son libres de hacer lo que quieran. Por el contrario, el desbordamiento para tipos sin firma está bien definido.

Además, con los tipos sin firma puede recurrir a reglas como la que con s = a (+) b (donde (+) es una adición sin signo posiblemente desbordante) tendrá s == a + b o s < a && s < b , que le permite detectar el desbordamiento después del hecho con operaciones baratas.

Sin embargo, es poco probable que vaya mucho más lejos en este camino porque el esfuerzo requerido se acerca rápidamente, o incluso supera, al esfuerzo de implementar las operaciones de doble extremidad a las que aludí anteriormente. Solo un análisis exhaustivo del dominio de la aplicación podría proporcionar la información necesaria para planificar / implementar dichos accesos directos. En el caso general y con los límites que has dado, estás fuera de suerte.