¿Las matemáticas de punto flotante son consistentes en C #? ¿Puede ser?

No, esta no es otra pregunta “¿Por qué es (1 / 3.0) * 3! = 1” .

He estado leyendo sobre puntos flotantes mucho últimamente; específicamente, cómo el mismo cálculo puede dar resultados diferentes en diferentes architectures o configuraciones de optimización.

Este es un problema para los videojuegos que almacenan repeticiones, o son redes peer-to-peer (en oposición al servidor-cliente), que confían en que todos los clientes generan exactamente los mismos resultados cada vez que ejecutan el progtwig: una pequeña discrepancia en uno el cálculo de punto flotante puede conducir a un estado de juego drásticamente diferente en diferentes máquinas (¡o incluso en la misma máquina! )

Esto sucede incluso entre los procesadores que “siguen” a IEEE-754 , principalmente porque algunos procesadores (a saber, x86) usan una precisión extendida doble . Es decir, usan registros de 80 bits para hacer todos los cálculos, luego truncan a 64 o 32 bits, lo que lleva a resultados de redondeo diferentes a los de las máquinas que usan 64 o 32 bits para los cálculos.

He visto varias soluciones a este problema en línea, pero todas para C ++, no C #:

  • Deshabilite el modo doble de precisión extendida (para que todos los cálculos double utilicen 64 bits IEEE-754) usando _controlfp_s (Windows), _FPU_SETCW (Linux?) O fpsetprec (BSD).
  • Ejecute siempre el mismo comstackdor con la misma configuración de optimización y exija que todos los usuarios tengan la misma architecture de CPU (sin reproducción multiplataforma). Debido a que mi “comstackdor” es realmente el JIT, que se puede optimizar de forma diferente cada vez que se ejecuta el progtwig , no creo que esto sea posible.
  • Use la aritmética de punto fijo y evite float y double total. decimal funcionaría para este propósito, pero sería mucho más lento y ninguna de las funciones de la biblioteca System.Math admite.

Entonces, ¿esto es incluso un problema en C #? ¿Qué pasa si solo bash soportar Windows (no Mono)?

Si es así, ¿hay alguna manera de forzar a mi progtwig a funcionar con una doble precisión normal?

Si no, ¿hay alguna biblioteca que ayude a mantener los cálculos de coma flotante consistentes?

No conozco ninguna manera de hacer que los puntos flotantes normales sean deterministas en .net. JITter puede crear código que se comporte de manera diferente en diferentes plataformas (o entre diferentes versiones de .net). Por lo tanto, no es posible usar float normales en el código .net determinista.

Las soluciones alternativas que consideré:

  1. Implementar FixedPoint32 en C #. Si bien esto no es demasiado difícil (tengo una implementación a medio terminar), el rango muy pequeño de valores hace que sea molesto de usar. Debe tener cuidado en todo momento para que no se desborde ni pierda demasiada precisión. Al final, encontré que esto no es más fácil que usar números enteros directamente.
  2. Implementar FixedPoint64 en C #. Encontré esto bastante difícil de hacer. Para algunas operaciones, serían útiles enteros intermedios de 128 bits. Pero .net no ofrece ese tipo.
  3. Implemente un punto flotante personalizado de 32 bits. La falta de un BitScanReverse intrínseco provoca algunas molestias al implementar esto. Pero actualmente creo que este es el camino más prometedor.
  4. Use código nativo para las operaciones matemáticas. Incurre en la sobrecarga de una llamada de delegado en cada operación matemática.

Acabo de comenzar una implementación de software de matemática de coma flotante de 32 bits. Puede hacer aproximadamente 70 millones de adiciones / multiplicaciones por segundo en mi 2.66 GHz i3. https://github.com/CodesInChaos/SoftFloat . Obviamente todavía es muy incompleto y con errores.

La especificación C # (§4.1.6 Tipos de punto flotante) permite específicamente que los cálculos en coma flotante se realicen con una precisión superior a la del resultado. Entonces, no, no creo que puedas hacer esos cálculos deterministas directamente en .Net. Otros sugirieron varias soluciones, para que pueda probarlas.

La siguiente página puede ser útil en caso de que necesite la portabilidad absoluta de tales operaciones. Discute el software para probar implementaciones del estándar IEEE 754, incluido el software para emular operaciones de punto flotante. Sin embargo, la mayoría de la información es probablemente específica de C o C ++.

http://www.math.utah.edu/~beebe/software/ieee/

Una nota sobre el punto fijo

Los números binarios de puntos fijos también pueden funcionar bien como un sustituto del punto flotante, como es evidente a partir de las cuatro operaciones aritméticas básicas:

  • La sum y la resta son triviales. Funcionan de la misma manera que los enteros. Solo agrega o resta!
  • Para multiplicar dos números de punto fijo, multiplica los dos números y luego cambia a la derecha el número definido de bits fraccionarios.
  • Para dividir dos números de punto fijo, cambie el dividendo a la izquierda del número definido de bits fraccionarios, luego divida por el divisor.
  • El capítulo cuatro de este documento contiene instrucciones adicionales para implementar números de punto fijo binarios.

Los números binarios de punto fijo se pueden implementar en cualquier tipo de datos enteros como int, long y BigInteger, y los tipos no compatibles con CLS uint y ulong.

Como se sugiere en otra respuesta, puede usar tablas de búsqueda, donde cada elemento de la tabla es un número de punto fijo binario, para ayudar a implementar funciones complejas como seno, coseno, raíz cuadrada, etc. Si la tabla de búsqueda es menos granular que el número de punto fijo, se sugiere redondear la entrada agregando la mitad de la granularidad de la tabla de búsqueda a la entrada:

 // Assume each number has a 12 bit fractional part. (1/4096) // Each entry in the lookup table corresponds to a fixed point number // with an 8-bit fractional part (1/256) input+=(1<<3); // Add 2^3 for rounding purposes input>>=4; // Shift right by 4 (to get 8-bit fractional part) // --- clamp or restrict input here -- // Look up value. return lookupTable[input]; 

¿Es esto un problema para C #?

Sí. Diferentes architectures son la menor de sus preocupaciones, diferentes tasas de cuadros, etc. pueden provocar desviaciones debido a imprecisiones en las representaciones flotantes, incluso si son las mismas inexactitudes (por ejemplo, la misma architecture, excepto una GPU más lenta en una máquina).

¿Puedo usar System.Decimal?

No hay ninguna razón por la que no puedas, sin embargo, es un perro lento.

¿Hay alguna manera de forzar mi progtwig para que funcione con doble precisión?

Sí. Aloje el tiempo de ejecución de CLR usted mismo ; y comstackr en todas las llamadas / indicadores nessecary (que cambian el comportamiento de la aritmética de coma flotante) en la aplicación C ++ antes de llamar a CorBindToRuntimeEx.

¿Hay bibliotecas que ayuden a mantener los cálculos de coma flotante consistentes?

No que yo sepa.

¿Hay alguna otra forma de resolver esto?

He abordado este problema antes, la idea es usar QNumbers . Son una forma de reales que son punto fijo; pero no el punto fijo en base-10 (decimal) – sino base-2 (binario); debido a esto las primitivas matemáticas sobre ellos (add, sub, mul, div) son mucho más rápidas que los puntos fijos naive base-10; especialmente si n es el mismo para ambos valores (que en su caso sería). Además, debido a que son integrales, tienen resultados bien definidos en cada plataforma.

Tenga en cuenta que la velocidad de fotogtwigs todavía puede afectar a estos, pero no es tan mala y se puede corregir fácilmente con los puntos de sincronización.

¿Puedo usar más funciones matemáticas con QNumbers?

Sí, ida y vuelta un decimal para hacer esto. Además, realmente deberías estar usando tablas de búsqueda para las funciones trig (sin, cos); como esos realmente pueden dar resultados diferentes en diferentes plataformas, y si los codifica correctamente, pueden usar QNumbers directamente.

De acuerdo con esta entrada de blog de MSDN ligeramente antigua, el JIT no usará SSE / SSE2 para coma flotante, es todo x87. Por eso, como mencionaste, debes preocuparte por los modos y las banderas, y en C # eso no es posible de controlar. Por lo tanto, el uso de operaciones de coma flotante normales no garantizará el mismo resultado exacto en cada máquina para su progtwig.

Para obtener una reproducibilidad precisa de doble precisión, tendrá que hacer una emulación de punto flotante (o punto fijo) de software. No sé de las bibliotecas de C # para hacer esto.

Dependiendo de las operaciones que necesite, es posible que pueda salirse con una sola precisión. Aquí está la idea:

  • almacene todos los valores que le interesan con una sola precisión
  • para realizar una operación:
    • expandir las entradas a doble precisión
    • hacer la operación en doble precisión
    • convertir el resultado a una sola precisión

El gran problema con x87 es que los cálculos se pueden hacer con una precisión de 53 o 64 bits dependiendo de la bandera de precisión y si el registro se derramó a la memoria. Pero para muchas operaciones, realizar la operación en alta precisión y redondear a una precisión menor garantizará la respuesta correcta, lo que implica que se garantizará que la respuesta sea la misma en todos los sistemas. No importa si obtiene la precisión extra, ya que tiene la precisión suficiente para garantizar la respuesta correcta en ambos casos.

Operaciones que deberían funcionar en este esquema: sum, resta, multiplicación, división, raíz cuadrada. Cosas como sin, exp, etc. no funcionarán (los resultados generalmente coincidirán pero no hay garantía). “¿Cuándo el doble redondeo es inocuo?” Referencia ACM (registro pagado req.)

¡Espero que esto ayude!

Como ya se ha dicho en otras respuestas: Sí, este es un problema en C #, incluso cuando se trata de Windows puro.

En cuanto a una solución: puede reducir (y con un poco de esfuerzo / rendimiento) evitar el problema completamente si usa una clase BigInteger incorporada y escala todos los cálculos a una precisión definida mediante el uso de un denominador común para cualquier cálculo / almacenamiento de dichos números .

Según lo solicitado por OP – con respecto al rendimiento:

System.Decimal representa el número con 1 bit para un signo y un entero de 96 bits y una “escala” (que representa dónde está el punto decimal). Para todos los cálculos que realice, debe operar en esta estructura de datos y no puede usar instrucciones flotantes integradas en la CPU.

La “solución” de BigInteger hace algo similar, solo que puede definir la cantidad de dígitos que necesita / desea … quizás solo desee 80 bits o 240 bits de precisión.

La lentitud viene siempre de tener que simular todas las operaciones en estos números a través de instrucciones enteras solamente sin usar las instrucciones incorporadas de CPU / FPU que a su vez conducen a muchas más instrucciones por operación matemática.

Para disminuir el rendimiento, hay varias estrategias, como QNumbers (ver respuesta de Jonathan Dickinson, ¿las matemáticas de coma flotante son consistentes en C #? ¿Puede ser? ) Y / o almacenamiento en caché (por ejemplo, cálculos trigonométricos …), etc.

Bueno, aquí sería mi primer bash sobre cómo hacer esto :

  1. Cree un proyecto ATL.dll que tenga un objeto simple para utilizarlo en sus operaciones críticas de punto flotante. asegúrese de comstackrlo con indicadores que deshabiliten el uso de hardware no xx87 para hacer punto flotante.
  2. Cree funciones que llamen a operaciones de coma flotante y devuelva los resultados; Comience de manera simple y luego, si funciona para usted, siempre puede boost la complejidad para satisfacer sus necesidades de rendimiento más adelante si es necesario.
  3. Ponga las llamadas control_fp alrededor de las matemáticas reales para asegurarse de que se haga de la misma manera en todas las máquinas.
  4. Haga referencia a su nueva biblioteca y realice pruebas para asegurarse de que funciona como se espera.

(Creo que puede comstackr a un .dll de 32 bits y luego usarlo con x86 o AnyCpu [o probablemente solo tenga como objective x86 en un sistema de 64 bits; vea el comentario a continuación].)

Entonces, suponiendo que funcione, si desea usar Mono, imagino que debería poder replicar la biblioteca en otras plataformas x86 de una manera similar (no COM por supuesto, aunque, tal vez, con vino? Un poco fuera de mi área una vez) vamos allí aunque …).

Suponiendo que pueda hacer que funcione, debería poder configurar funciones personalizadas que puedan realizar varias operaciones a la vez para solucionar cualquier problema de rendimiento, y tendrá matemática de punto flotante que le permite obtener resultados consistentes en todas las plataformas con una cantidad mínima de código escrito en C ++, y dejando el rest de tu código en C #.

No soy un desarrollador de juegos, aunque tengo mucha experiencia con problemas computacionalmente difíciles … así que haré lo mejor que pueda.

La estrategia que adoptaría es esencialmente esta:

  • Utilice un método más lento (si es necesario, si hay una manera más rápida, ¡excelente!), Pero predecible para obtener resultados reproducibles
  • Use doble para todo lo demás (por ejemplo, renderizado)

El corto plazo de esto es: necesitas encontrar un equilibrio. Si está gastando 30ms de renderizado (~ 33fps) y solo 1ms realizando detección de colisión (o inserta alguna otra operación altamente sensible), incluso si triplica el tiempo que lleva hacer la aritmética crítica, el impacto que tiene en su velocidad de fotogtwigs es caes de 33.3 fps a 30.3 fps

Le sugiero que haga un perfil de todo, tenga en cuenta cuánto tiempo se dedica a cada uno de los cálculos notablemente costosos, luego repita las mediciones con uno o más métodos para resolver este problema y vea cuál es el impacto.

Verificando los enlaces en las otras respuestas deja en claro que nunca tendrás la garantía de si el punto flotante se implementa “correctamente” o si siempre recibirás cierta precisión para un cálculo dado, pero quizás podrías hacer un mejor esfuerzo al (1) truncar todos los cálculos a un mínimo común (por ejemplo, si diferentes implementaciones le darán 32 a 80 bits de precisión, truncar siempre cada operación a 30 o 31 bits), (2) tener una tabla de algunos casos de prueba al inicio (Casos límite de sumr, restar, multiplicar, dividir, sqrt, coseno, etc.) y si la implementación calcula los valores que coinciden con la tabla, entonces no se moleste en hacer ningún ajuste.

Tu pregunta en cosas bastante difíciles y técnicas O_o. Sin embargo, puedo tener una idea.

Seguramente sabe que la CPU realiza algunos ajustes después de cualquier operación flotante. Y la CPU ofrece varias instrucciones diferentes que realizan diferentes operaciones de redondeo.

Entonces, para una expresión, su comstackdor elegirá un conjunto de instrucciones que lo guiarán a un resultado. Pero cualquier otro flujo de trabajo de instrucciones, incluso si tienen la intención de calcular la misma expresión, puede proporcionar otro resultado.

Los “errores” cometidos por un ajuste de redondeo crecerán con cada instrucción adicional.

Como ejemplo, podemos decir que a nivel de conjunto: a * b * c no es equivalente a a * c * b.

No estoy del todo seguro de eso, tendrás que pedirle a alguien que conozca la architecture de CPU mucho más que yo: p

Sin embargo, para responder a su pregunta: en C o C ++ puede resolver su problema porque tiene algún control sobre el código máquina generado por su comstackdor, sin embargo, en .NET no tiene ninguno. Por lo tanto, siempre que su código de máquina pueda ser diferente, nunca estará seguro del resultado exacto.

Tengo curiosidad de qué manera esto puede ser un problema porque la variación parece muy mínima, pero si necesitas una operación realmente precisa, la única solución que puedo pensar será boost el tamaño de tus registros flotantes. Use doble precisión o incluso doble larga si puede (no estoy seguro de que sea posible usando CLI).

Espero haber sido lo suficientemente claro, no soy perfecto en inglés (… en absoluto: s)