Implemente un número de punto flotante binario IEEE 754 de 64 bits a través de la manipulación de enteros

12

(Por el momento he etiquetado la pregunta "C", pero si conoce otro lenguaje que admita los sindicatos, también puede usarlo).

Su tarea es construir los cuatro operadores matemáticos estándar + - * /para la siguiente estructura:

union intfloat{
    double f;
    uint8_t h[8];
    uint16_t i[4];
    uint32_t j[2]; 
    uint64_t k;
    intfloat(double g){f = g;}
    intfloat(){k = 0;}
}

de modo que las operaciones en sí mismas solo manipulen o accedan a la parte entera (por lo que tampoco se compara con el doble en cualquier momento durante la operación), y el resultado es exactamente el mismo (o funcionalmente equivalente, en el caso de resultados no numéricos como NaN) como si la operación matemática correspondiente se hubiera aplicado directamente al doublelugar.

Puede elegir qué parte entera manipular, tal vez incluso usando diferentes entre diferentes operadores. (También puede optar por eliminar el "sin firmar" de cualquiera de los campos de la unión, aunque no estoy seguro de si desea hacer eso).

Su puntaje es la suma de la longitud del código en caracteres para cada uno de los cuatro operadores. La puntuación más baja gana.

Para aquellos de nosotros que no estamos familiarizados con la especificación IEEE 754, aquí hay un artículo al respecto en Wikipedia.


Ediciones:

06/03 08:47 Se agregaron constructores a la estructura intfloat. Puede usarlos para probar, en lugar de configurar manualmente el doble / etc.

Joe Z.
fuente
1
¡Ay! Dime que tienes una solución.
dmckee --- ex gatito moderador el
44
Hmmm ... tal vez sería mejor definirlo intstructen términos de uint8_8, uint16_tetc., ya que los tamaños absolutos de short, inty así sucesivamente, no están definidos por el estándar (cada tipo tiene un tamaño mínimo y hay un orden estricto de tamaño, pero Eso es).
dmckee --- ex gatito moderador el
1
Supongo que esta es una gran práctica (y desafiante) incluso si no es un golfista
John Dvorak
3
Esta pregunta podría usar documentación de cómo se maneja el redondeo y un buen conjunto de pruebas.
Peter Taylor
44
Estoy seguro de que está en la especificación, pero la especificación real costará unos pocos cientos de dólares. Probablemente hay descripciones que están disponibles de forma gratuita, pero la OMI debe recaer en el interrogador para incluir ese tipo de detalles (o al menos un enlace a un sitio que probablemente seguirá existiendo en un par de años) dentro de la pregunta en lugar de que los respondedores busquen los materiales necesarios para saber qué es lo que realmente quiere la pregunta.
Peter Taylor

Respuestas:

11

C ++, ~ 1500 caracteres

Expande los flotadores en una representación de punto fijo de 8000 dígitos binarios, realiza las operaciones sobre eso y luego los vuelve a convertir.

// an "expanded" float.                                                                                                         
// n is nan, i is infinity, z is zero, s is sign.                                                                               
// nan overrides inf, inf overrides zero, zero overrides digits.                                                                
// sign is valid unless nan.                                                                                                    
// We store the number in fixed-point, little-endian.  Binary point is                                                          
// at N/2.  So 1.0 is N/2 zeros, one, N/2-1 zeros.                                                                              
#define N 8000
struct E {
  int n;
  int i;
  int z;
  long s;
  long d[N];
};
#define V if(r.n|r.i|r.z)return r
// Converts a regular floating-point number to an expanded one.                                                                 
E R(F x){
  long i,e=x.k<<1>>53,m=x.k<<12>>12;
  E r={e==2047&&m!=0,e==2047,e+m==0,x.k>>63};
  if(e)m+=1L<<52;else e++;
  for(i=0;i<53;i++)r.d[2925+e+i]=m>>i&1;
  return r;
}
E A(E x,E y){
  int i,c,v;
  if(x.s>y.s)return A(y,x);
  E r={x.n|y.n|x.i&y.i&(x.s^y.s),x.i|y.i,x.z&y.z,x.i&x.s|y.i&y.s|~x.i&~y.i&x.s&y.s};V;
  if(x.s^y.s){
    c=0;
    r.z=1;
    for(i=0;i<N;i++){
      v=x.d[i]-y.d[i]-c;
      r.d[i]=v&1;c=v<0;
      r.z&=~v&1;
    }
    if(c){x.s=1;y.s=0;r=A(y,x);r.s=1;}
  }else{
    c=0;
    for(i=0;i<N;i++){
      v=x.d[i]+y.d[i]+c;
      r.d[i]=v&1;c=v>1;
    }
  }
  return r;
}
E M(E x, E y){
  int i;
  E r={x.n|y.n|x.i&y.z|x.z&y.i,x.i|y.i,x.z|y.z,x.s^y.s};V;
  E s={0,0,1};
  for(i=0;i<6000;i++)y.d[i]=y.d[i+2000];
  for(i=0;i<4000;i++){
    if(x.d[i+2000])s=A(s,y);
    y=A(y,y);
  }
  s.s^=x.s;
  return s;
}
// 1/d using Newton-Raphson:                                                                                                    
// x <- x * (2 - d*x)                                                                                                           
E I(E d){
  int i;
  E r={d.n,d.z,d.i,d.s};V;
  E t={};t.d[4001]=1;
  for(i=N-1;i>0;i--)if(d.d[i])break;
  E x={0,0,0,d.s};x.d[N-i]=1;
  d.s^=1;
  for(i=0;i<10;i++)x=M(x,A(t,M(d,x)));
  return x;
}
// Convert expanded number back to regular floating point.                                                                      
F C(E x){
  long i,j,e,m=0;
  for(i=N-1;i>=0;i--)if(x.d[i])break;
  for(j=0;j<N;j++)if(x.d[j])break;
  if(i>0&x.d[i-53]&(j<i-53|x.d[i-52])){E y={0,0,0,x.s};y.d[i-53]=1;return C(A(x,y));}
  if(i<2978){e=0;for(j=0;j<52;j++)m+=x.d[j+2926]<<j;}
  else if(i<5024){e=i-2977;for(j=0;j<52;j++)m+=x.d[i+j-52]<<j;}
  else x.i=1;
  if(x.z)e=m=0;
  if(x.i){e=2047;m=0;}
  if(x.n)e=m=2047;
  F y;y.k=x.s<<63|e<<52|m;return y;
}
// expand, do op, unexpand                                                                                                      
F A(F x,F y){return C(A(R(x),R(y)));}
F S(F x,F y){y.k^=1L<<63;return A(x,y);}
F M(F x,F y){return C(M(R(x),R(y)));}
F D(F x,F y){return C(M(R(x),I(R(y))));}

Soy demasiado vago para eliminar todos los espacios y líneas nuevas para obtener un conteo exacto de golf, pero son aproximadamente 1500 caracteres.

Keith Randall
fuente