Zaimplementuj 64-bitową binarną liczbę zmiennoprzecinkową IEEE 754 za pomocą operacji na liczbach całkowitych

12

(Na razie oznaczyłem pytanie „C”, ale jeśli znasz inny język, który obsługuje związki, możesz go również użyć).

Twoim zadaniem jest zbudowanie czterech standardowych operatorów matematycznych + - * /dla następującej struktury:

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;}
}

tak, że same operacje zawsze manipulują lub uzyskują dostęp do części całkowitej (więc nie można porównywać z podwójną w dowolnym momencie podczas operacji), a wynik jest dokładnie taki sam (lub funkcjonalnie równoważny, w przypadku wyników nienumerycznych, takich jak NaN) jakby doublezamiast tego zastosowano odpowiednią operację matematyczną .

Możesz wybrać, którą częścią całkowitą chcesz manipulować, być może nawet używając różnych spośród różnych operatorów. (Możesz także usunąć „niepodpisany” z dowolnego pola w unii, chociaż nie jestem pewien, czy chcesz to zrobić.)

Twój wynik to suma długości kodu w znakach dla każdego z czterech operatorów. Najniższy wynik wygrywa.

Dla tych z nas znają specyfikacji IEEE 754, tutaj jest artykuł o nim na Wikipedii.


Edycje:

03-06 08:47 Dodano konstruktory do struktury intfloat. Możesz używać ich do testowania, zamiast ręcznego ustawiania podwójnego / itp.

Joe Z.
źródło
1
Yikes! Powiedz mi, że masz rozwiązanie.
dmckee --- były moderator kociak
4
Hmmm ... może byłoby lepiej zdefiniować intstructw kategoriach uint8_8, uint16_ti tak dalej jako absolutnych rozmiarów short, inta więc nie są określone przez normę (każdy typ ma wielkość minimalną i istnieje ścisła kolejność pod względem wielkości, ale Otóż ​​to).
dmckee --- były moderator kociak
1
Sądzę, że jest to świetna (i trudna) praktyka, nawet jeśli nie jest golfistą
John Dvorak
3
W tym pytaniu można wykorzystać dokumentację dotyczącą obsługi zaokrąglania i dobry zestaw testów.
Peter Taylor
4
Jestem pewien, że jest w specyfikacji, ale rzeczywista specyfikacja kosztuje kilkaset USD. Prawdopodobnie istnieją opisy, które są dostępne za darmo, ale na IMO ciężar powinien spoczywać na pytającym, aby podać tego rodzaju szczegóły (lub przynajmniej link do strony, która prawdopodobnie będzie za kilka lat) w ciągu pytanie, a nie na respondentów, którzy szukają niezbędnych materiałów, aby wiedzieć, czego tak naprawdę chce pytanie.
Peter Taylor

Odpowiedzi:

11

C ++, ~ 1500 znaków

Rozwija liczby zmiennoprzecinkowe do reprezentacji stałoprzecinkowej o 8 000 cyfrach binarnych, wykonuje na tym operacje, a następnie dokonuje konwersji.

// 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))));}

Jestem zbyt leniwy, aby usunąć wszystkie spacje i znaki nowej linii, aby uzyskać dokładną liczbę w golfa, ale jest to około 1500 znaków.

Keith Randall
źródło