7 #include "cl_float_io.h"
12 // Michael Stoll 10.2.1990 - 26.3.1990
13 // Bruno Haible 8.9.1990 - 10.9.1990
16 // Jede Real-Zahl /= 0 repräsentiert ein (offenes) Intervall. Es wird die-
17 // jenige Dezimalzahl mit möglichst wenig Stellen ausgegeben, die in diesem
19 // Um auch große Exponenten zu behandeln, werden Zweier- in Zehnerpotenzen
20 // erst einmal näherungsweise umgerechnet. Nötigenfalls wird die Rechen-
21 // genauigkeit erhöht. Hierbei wird von den Long-Floats beliebiger
22 // Genauigkeit Gebrauch gemacht.
25 // cl_ln2(digits) liefert ln(2) mit mindestens digits Mantissenbits.
26 // cl_ln10(digits) liefert ln(10) mit mindestens digits Mantissenbits.
27 // cl_decimal_string(integer) liefert zu einem Integer >0
28 // einen String mit seiner Dezimaldarstellung.
29 // (substring string start [end]) wie subseq, jedoch für Strings schneller.
31 CL_REQUIRE(cl_F_ln2_var)
32 CL_REQUIRE(cl_F_ln10_var)
34 #include "cl_output.h"
35 #include "cl_sstring.h"
39 #include "cl_F_tran.h"
40 #include "cl_rational.h"
41 #include "cl_integer.h"
42 #include "cl_integer_io.h"
45 // Hauptfunktion zur Umwandlung von Floats ins Dezimalsystem:
46 // Zu einem Float x werden ein String as und drei Integers k,e,s
47 // berechnet mit folgenden Eigenschaften:
49 // Falls x/=0, betrachte |x| statt x. Also oBdA x>0.
50 // Seien x1 und x2 die nächstkleinere bzw. die nächstgrößere Zahl zu x
51 // vom selben Floating-Point-Format. Die Zahl x repräsentiert somit das
52 // offene Intervall von (x+x1)/2 bis (x+x2)/2.
53 // a ist ein Integer >0, mit genau k Dezimalstellen (k>=1), und es gilt
54 // (x+x1)/2 < a*10^(-k+e) < (x+x2)/2 .
55 // Dabei ist k minimal, also a nicht durch 10 teilbar.
56 // Falls x=0: a=0, k=1, e=0.
57 // as ist die Ziffernfolge von a, der Länge k.
60 struct cl_decimal_decoded_float {
66 cl_decimal_decoded_float (char * ap, uintL kp, const cl_I& ep, const cl_I& sp) : a(ap), k(kp), e(ep), s(sp) {}
69 static const cl_decimal_decoded_float decode_float_decimal (const cl_F& x)
71 var cl_idecoded_float x_idecoded = integer_decode_float(x);
72 var cl_I& binmant = x_idecoded.mantissa;
73 var cl_I& binexpo = x_idecoded.exponent;
74 var cl_I& sign = x_idecoded.sign;
75 if (eq(binmant,0)) // x=0 ?
77 return cl_decimal_decoded_float(cl_sstring("0",1), 1, 0, 0);
78 // x/=0, also ist sign das Vorzeichen von x und
79 // |x| = 2^binexpo * float(binmant,x) . Ab jetzt oBdA x>0.
80 // Also x = 2^binexpo * float(binmant,x) .
81 var uintL l = integer_length(binmant); // Anzahl der Bits von binmant, >=3
82 var cl_I binmant2 = ash(binmant,1); // 2*binmant
83 var cl_I oben = plus1(binmant2); // obere Intervallgrenze ist
84 // (x+x2)/2 = 2^(binexpo-1) * oben
85 var cl_I unten = minus1(binmant2); // untere Intervallgrenze ist
86 var uintL untenshift = 0; // (x+x1)/2 = 2^(binexpo-1-untenshift) * unten
87 if (integer_length(unten) == l) {
88 // Normalerweise integerlength(unten) = 1+integerlength(binmant).
89 // Hier integerlength(unten) = l = integerlength(binmant),
90 // also war binmant eine Zweierpotenz. In diesem Fall ist die
91 // die Toleranz nach oben 1/2 Einheit, aber die Toleranz nach unten
92 // nur 1/4 Einheit: (x+x1)/2 = 2^(binexpo-2) * (4*binmant-1)
93 unten = minus1(ash(binmant2,1));
96 // Bestimme d (ganz) und a1,a2 (ganz, >0) so, daß
97 // die ganzen a mit (x+x1)/2 < 10^d * a < (x+x2)/2 genau
98 // die ganzen a mit a1 <= a <= a2 sind und 0 <= a2-a1 < 20 gilt.
99 // Wandle dazu 2^e := 2^(binexpo-1) ins Dezimalsystem um.
100 var cl_I e = binexpo - 1;
101 var bool e_gross = (abs(e) > ash(l,1)); // Ist |e| recht groß, >2*l ?
102 var uintL g; // Hilfsvariablen für den Fall, daß |e| groß ist
104 var cl_I zehn_d; // Hilfsvariable 10^|d| für den Fall, daß |e| klein ist
105 var cl_I d; // Ergebnisvariablen
108 if (e_gross) { // Ist |e| recht groß ?
109 // Da 2^e nur näherungsweise gehen kann, braucht man Schutzbits.
110 var uintL h = 16; // Anzahl der Schutzbits, muß >= 3 sein
112 // Ziel: 2^e ~= 10^d * f/2^g, wobei 1 <= f/2^g < 10.
113 g = l + h; // Anzahl der gültigen Bits von f
114 // Schätze d = floor(e*lg(2))
115 // mit Hilfe der Näherungsbrüche von lg(2):
116 // (0 1/3 3/10 28/93 59/196 146/485 643/2136 4004/13301
117 // 8651/28738 12655/42039 21306/70777 76573/254370 97879/325147
118 // 1838395/6107016 1936274/6432163 13456039/44699994
119 // 15392313/51132157 44240665/146964308 59632978/198096465
120 // 103873643/345060773 475127550/1578339557 579001193/1923400330
122 // e>=0 : wähle lg(2) < a/b < lg(2) + 1/e,
123 // dann ist d <= floor(e*a/b) <= d+1 .
124 // e<0 : wähle lg(2) - 1/abs(e) < a/b < lg(2),
125 // dann ist d <= floor(e*a/b) <= d+1 .
126 // Es ist bekannt, daß abs(e) <= 2^31 + 2^20 .
127 // Unser d sei := floor(e*a/b)-1. (d /= 0, da abs(e) >= 7.)
130 ? floor1(e*3,10) // Näherungsbruch 3/10
131 : floor1(e*21306,70777) // Näherungsbruch 21306/70777
134 ? floor1(e*28,93) // Näherungsbruch 28/93
135 : floor1(e*12655,42039) // Näherungsbruch 12655/42039
138 // Das wahre d wird durch diese Schätzung entweder getroffen
139 // oder um 1 unterschätzt.
140 // Anders ausgedrückt: 0 < e*log(2)-d*log(10) < 2*log(10).
141 // Nun f/2^g als exp(e*log(2)-d*log(10)) berechnen.
142 // Da f < 100*2^g < 2^(g+7), sind g+7 Bits relative Genauigkeit
143 // des Ergebnisses, also g+7 Bits absolute Genauigkeit von
144 // e*log(2)-d*log(10) nötig. Dazu mit l'=integerlength(e)
145 // für log(2): g+7+l' Bits abs. Gen., g+7+l' Bits rel. Gen.,
146 // für log(10): g+7+l' Bits abs. Gen., g+7+l'+2 Bist rel. Gen.
147 var cl_float_format_t gen = (cl_float_format_t)(g + integer_length(e) + 9); // Genauigkeit
148 var cl_F f2g = exp(The(cl_F)(e * cl_ln2(gen)) - The(cl_F)(d * cl_ln10(gen))); // f/2^g
149 // Das so berechnete f/2^g ist >1, <100.
150 // Mit 2^g multiplizieren und auf eine ganze Zahl runden:
151 f = round1(scale_float(f2g,g)); // liefert f
152 // Eventuell f und d korrigieren:
153 if (f >= ash(10,g)) // f >= 10*2^g ?
154 { f = floor1(f,10); d = d+1; }
155 // Nun ist 2^e ~= 10^d * f/2^g, wobei 1 <= f/2^g < 10 und
156 // f ein Integer ist, der um höchstens 1 vom wahren Wert abweicht:
157 // 10^d * (f-1)/2^g < 2^e < 10^d * (f+1)/2^g
158 // Wir verkleinern nun das offene Intervall
159 // von (x+x1)/2 = 2^(binexpo-1-untenshift) * unten
160 // bis (x+x2)/2 = 2^(binexpo-1) * oben
161 // zu einem abgeschlossenen Intervall
162 // von 10^d * (f+1)/2^(g+untenshift) * unten
163 // bis 10^d * (f-1)/2^g * oben
164 // und suchen darin Zahlen der Form 10^d * a mit ganzem a.
165 // Wegen oben - unten/2^untenshift >= 3/2
166 // und oben + unten/2^untenshift <= 4*binmant+1 < 2^(l+2) <= 2^(g-1)
167 // ist die Intervall-Länge
168 // = 10^d * ((f-1)*oben - (f+1)*unten/2^untenshift) / 2^g
169 // = 10^d * ( f * (oben - unten/2^untenshift)
170 // - (oben + unten/2^untenshift) ) / 2^g
171 // >= 10^d * (2^g * 3/2 - 2^(g-1)) / 2^g
172 // = 10^d * (3/2 - 2^(-1)) = 10^d
173 // und daher gibt es in dem Intervall mindestens eine Zahl
175 // Die Zahlen der Form 10^d * a in diesem Intervall sind die
176 // mit a1 <= a <= a2, wobei a2 = floor((f-1)*oben/2^g) und
177 // a1 = ceiling((f+1)*unten/2^(g+untenshift))
178 // = floor(((f+1)*unten-1)/2^(g+untenshift))+1 .
179 // Wir haben eben gesehen, daß a1 <= a2 sein muß.
180 a1 = plus1(ash(minus1((f+1)*unten),-(g+untenshift)));
181 a2 = ash((f-1)*oben,-g);
182 // Wir können auch das offene Intervall
183 // von (x+x1)/2 = 2^(binexpo-1-untenshift) * unten
184 // bis (x+x2)/2 = 2^(binexpo-1) * oben
185 // in das (abgeschlossene) Intervall
186 // von 10^d * (f-1)/2^(g+untenshift) * unten
187 // bis 10^d * (f+1)/2^g * oben
188 // einschachteln. Hierin sind die Zahlen der Form 10^d * a
189 // die mit a1' <= a <= a2', wobei a1' <= a1 <= a2 <= a2' ist
190 // und sich a1' und a2' analog zu a1 und a2 berechnen.
191 // Da (f-1)*oben/2^g und (f+1)*oben/2^g sich um 2*oben/2^g
192 // < 2^(l+2-g) < 1 unterscheiden, unterscheiden sich a2 und
193 // a2' um höchstens 1.
194 // Ebenso, wenn 'oben' durch 'unten/2^untenshift' ersetzt
195 // wird: a1' und a1 unterscheiden sich um höchstens 1.
196 // Ist nun a1' < a1 oder a2 < a2' , so ist die Zweierpotenz-
197 // Näherung 10^d * f/2^g für 2^e nicht genau genug gewesen,
198 // und man hat das Ganze mit erhöhtem h zu wiederholen.
199 // Ausnahme (da hilft auch keine höhere Genauigkeit):
200 // Wenn die obere oder untere Intervallgrenze (x+x2)/2 bzw.
201 // (x+x1)/2 selbst die Gestalt 10^d * a mit ganzem a hat.
202 // Dies testet man so:
203 // (x+x2)/2 = 2^e * oben == 10^d * a mit ganzem a, wenn
204 // - für e>=0, (dann 0 <= d <= e): 5^d | oben,
205 // - für e<0, (dann e <= d < 0): 2^(d-e) | oben, was
206 // nur für d-e=0 der Fall ist.
207 // (x+x1)/2 = 2^(e-untenshift) * unten == 10^d * a
208 // mit ganzem a, wenn
209 // - für e>0, (dann 0 <= d < e): 5^d | unten,
210 // - für e<=0, (dann e <= d <= 0): 2^(d-e+untenshift) | unten,
211 // was nur für d-e+untenshift=0 der Fall ist.
212 // Da wir es jedoch mit großem |e| zu tun haben, kann dieser
213 // Ausnahmefall hier gar nicht eintreten!
214 // Denn im Falle e>=0: Aus e>=2*l und l>=11 folgt
215 // e >= (l+2)*ln(10)/ln(5) + ln(10)/ln(2),
216 // d >= e*ln(2)/ln(10)-1 >= (l+2)*ln(2)/ln(5),
218 // und wegen 0 < unten < 2^(l+2) und 0 < oben < 2^(l+1)
219 // sind unten und oben nicht durch 5^d teilbar.
220 // Und im Falle e<=0: Aus -e>=2*l und l>=6 folgt
221 // -e >= (l+2)*ln(10)/ln(5),
222 // d-e >= e*ln(2)/ln(10)-1-e = (1-ln(2)/ln(10))*(-e)-1
223 // = (-e)*ln(5)/ln(10)-1 >= l+1,
224 // 2^(d-e) >= 2^(l+1),
225 // und wegen 0 < unten < 2^(l+1+untenshift) ist unten nicht
226 // durch 2^(d-e+untenshift) teilbar, und wegen
227 // 0 < oben < 2^(l+1) ist oben nicht durch 2^(d-e) teilbar.
229 var cl_I a1prime = plus1(ash(minus1((f-1)*unten),-(g+untenshift)));
231 { h = 2*h; goto neue_schutzbits; } // h verdoppeln und alles wiederholen
232 var cl_I a2prime = ash((f+1)*oben,-g);
234 { h = 2*h; goto neue_schutzbits; } // h verdoppeln und alles wiederholen
236 // Jetzt ist a1 der kleinste und a2 der größte Wert, der
237 // für a möglich ist.
238 // Wegen oben - unten/2^untenshift <= 2
239 // ist die obige Intervall-Länge
240 // = 10^d * ((f-1)*oben - (f+1)*unten/2^untenshift) / 2^g
241 // < 10^d * ((f-1)*oben - (f-1)*unten/2^untenshift) / 2^g
242 // = 10^d * (f-1)/2^g * (oben - unten/2^untenshift)
244 // also gibt es höchstens 20 mögliche Werte für a.
246 // |e| ist recht klein -> man kann 2^e und 10^d exakt ausrechnen
248 // e >= 0. Schätze d = floor(e*lg(2)) wie oben.
249 // Es ist e<=2*l<2^21.
251 ? floor1(e*28,93) // Näherungsbruch 28/93
252 : floor1(e*4004,13301) // Näherungsbruch 4004/13301
254 // Das wahre d wird durch diese Schätzung entweder getroffen
255 // oder um 1 überschätzt, aber das können wir leicht feststellen.
256 zehn_d = The(cl_I)(expt(10,d)); // zehn_d = 10^d
257 if (ash(1,e) < zehn_d) // falls 2^e < 10^d,
258 { d = d-1; zehn_d = exquo(zehn_d,10); } // Schätzung korrigieren
259 // Nun ist 10^d <= 2^e < 10^(d+1) und zehn_d = 10^d.
260 // a1 sei das kleinste ganze a > 2^(e-untenshift) * unten / 10^d,
261 // a2 sei das größte ganze a < 2^e * oben / 10^d.
262 // a1 = 1+floor(unten*2^e/(2^untenshift*10^d)),
263 // a2 = floor((oben*2^e-1)/10^d).
264 a1 = plus1(floor1(ash(unten,e),ash(zehn_d,untenshift)));
265 a2 = floor1(minus1(ash(oben,e)),zehn_d);
267 // e < 0. Schätze d = floor(e*lg(2)) wie oben.
268 // Es ist |e|<=2*l<2^21.
270 ? floor1(e*3,10) // Näherungsbruch 3/10
271 : floor1(e*643,2136) // Näherungsbruch 643/2136
273 // Das wahre d wird durch diese Schätzung entweder getroffen
274 // oder um 1 überschätzt, aber das können wir leicht feststellen.
275 zehn_d = The(cl_I)(expt(10,-d)); // zehn_d = 10^(-d)
276 if (integer_length(zehn_d) <= -e) // falls 2^e < 10^d,
277 { d = d-1; zehn_d = zehn_d*10; } // Schätzung korrigieren
278 // Nun ist 10^d <= 2^e < 10^(d+1) und zehn_d = 10^(-d).
279 // a1 sei das kleinste ganze a > 2^(e-untenshift) * unten / 10^d,
280 // a2 sei das größte ganze a < 2^e * oben / 10^d.
281 // a1 = 1+floor(unten*10^(-d)/2^(-e+untenshift)),
282 // a2 = floor((oben*10^(-d)-1)/2^(-e))
283 a1 = plus1(ash(unten*zehn_d,e-untenshift));
284 a2 = ash(minus1(oben*zehn_d),e);
287 // Nun sind die ganzen a mit (x+x1)/2 < 10^d * a < (x+x2)/2 genau
288 // die ganzen a mit a1 <= a <= a2. Deren gibt es höchstens 20.
289 // Diese werden in drei Schritten auf einen einzigen reduziert:
290 // 1. Enthält der Bereich eine durch 10 teilbare Zahl a ?
291 // ja -> setze a1:=ceiling(a1/10), a2:=floor(a2/10), d:=d+1.
292 // Danach enthält der Bereich a1 <= a <= a2 höchstens 10
293 // mögliche Werte für a.
294 // 2. Falls jetzt einer der möglichen Werte durch 10 teilbar ist
295 // (es kann nur noch einen solchen geben),
296 // wird er gewählt, die anderen vergessen.
297 // 3. Sonst wird unter allen noch möglichen Werten der zu x
298 // nächstgelegene gewählt.
299 var cl_boolean d_shift = cl_false; // Flag, ob im 1. Schritt d incrementiert wurde
300 var cl_I a; // das ausgewählte a
303 var cl_I b1 = ceiling1(a1,10);
304 var cl_I b2 = floor1(a2,10);
305 if (b1 <= b2) // noch eine durch 10 teilbare Zahl a ?
306 { a1 = b1; a2 = b2; d = d+1; d_shift = cl_true; }
313 // Noch eine durch 10 teilbare Zahl -> durch 10 teilen.
314 d = d+1; // noch d erhöhen, zehn-d wird nicht mehr gebraucht
315 // Nun a in einen Dezimalstring umwandeln
316 // und dann Nullen am Schluß streichen:
317 var char* as = cl_decimal_string(a); // Ziffernfolge zu a>0
318 var uintL las = strlen(as); // Länge der Ziffernfolge
319 var uintL k = las; // Länge ohne die gestrichenen Nullen am Schluß
320 var cl_I ee = k+d; // a * 10^d = a * 10^(-k+ee)
321 while (as[k-1] == '0') // eine 0 am Schluß?
322 { // ja -> a := a / 10 (wird aber nicht mehr gebraucht),
323 // d := d+1 (wird aber nicht mehr gebraucht),
324 k = k-1; as[k] = '\0';
326 return cl_decimal_decoded_float(as,k,ee,sign);
331 // a1=a2 -> keine Frage der Auswahl mehr:
334 // a1<a2 -> zu x nächstgelegenes 10^d * a wählen:
336 // a = round(f*2*binmant/2^g/(1oder10)) (beliebige Rundung)
337 // = ceiling(floor(f*2*binmant/(1oder10)/2^(g-1))/2) wählen:
338 var cl_I temp = f * binmant2;
339 if (d_shift) { temp = floor1(temp,10); }
340 a = ash(plus1(ash(temp,1-g)),-1);
342 // |e| klein -> analog wie oben a2 berechnet wurde
344 // e>=0: a = round(2^e*2*binmant/10^d)
345 if (d_shift) { zehn_d = 10*zehn_d; }
346 a = round1(ash(binmant2,e),zehn_d);
348 // e<0, also war d<0, jetzt (wegen Schritt 1) d<=0.
349 // a = round(2*binmant*10^(-d)/2^(-e))
350 if (d_shift) { zehn_d = floor1(zehn_d,10); }
351 a = ash(plus1(ash(binmant2*zehn_d,e+1)),-1);
355 var char* as = cl_decimal_string(a); // Ziffernfolge zu a>0
356 var uintL k = strlen(as);
357 ASSERT(as[k-1] != '0');
358 return cl_decimal_decoded_float(as,k,k+d,sign);
362 void print_float (cl_ostream stream, const cl_print_float_flags& flags, const cl_F& z)
364 var cl_decimal_decoded_float z_decoded = decode_float_decimal(z);
365 var char * & mantstring = z_decoded.a;
366 var uintL& mantlen = z_decoded.k;
367 var cl_I& expo = z_decoded.e;
368 var cl_I& sign = z_decoded.s;
369 // arg in Dezimaldarstellung: +/- 0.mant * 10^expo, wobei
370 // mant die Mantisse: als Simple-String mantstring mit Länge mantlen,
371 // expo der Dezimal-Exponent,
372 // sign das Vorzeichen (-1 oder 0 oder 1).
373 if (eq(sign,-1)) // z < 0 ?
374 fprintchar(stream,'-');
375 var bool flag = (expo >= -2) && (expo <= 7); // z=0 oder 10^-3 <= |z| < 10^7 ?
376 // Was ist auszugeben? Fallunterscheidung:
377 // flag gesetzt -> "fixed-point notation":
378 // expo <= 0 -> Null, Punkt, -expo Nullen, alle Ziffern
379 // 0 < expo < mantlen ->
380 // die ersten expo Ziffern, Punkt, die restlichen Ziffern
381 // expo >= mantlen -> alle Ziffern, expo-mantlen Nullen, Punkt, Null
382 // Nach Möglichkeit kein Exponent// wenn nötig, Exponent 0.
383 // flag gelöscht -> "scientific notation":
384 // erste Ziffer, Punkt, die restlichen Ziffern, bei mantlen=1 eine Null
386 if (flag && !plusp(expo)) {
387 // "fixed-point notation" mit expo <= 0
388 // erst Null und Punkt, dann -expo Nullen, dann alle Ziffern
389 fprintchar(stream,'0');
390 fprintchar(stream,'.');
391 for (uintL i = -FN_to_L(expo); i > 0; i--)
392 fprintchar(stream,'0');
393 fprint(stream,mantstring);
394 expo = 0; // auszugebender Exponent ist 0
396 // "fixed-point notation" mit expo > 0 oder "scientific notation"
397 var uintL scale = (flag ? FN_to_L(expo) : 1);
398 // Der Dezimalpunkt wird um scale Stellen nach rechts geschoben,
399 // d.h. es gibt scale Vorkommastellen. scale > 0.
400 if (scale < mantlen) {
401 // erst scale Ziffern, dann Punkt, dann restliche Ziffern:
402 { for (uintL i = 0; i < scale; i++)
403 fprintchar(stream,mantstring[i]);
405 fprintchar(stream,'.');
406 { for (uintL i = scale; i < mantlen; i++)
407 fprintchar(stream,mantstring[i]);
410 // scale>=mantlen -> es bleibt nichts für die Nachkommastellen.
411 // alle Ziffern, dann scale-mantlen Nullen, dann Punkt und Null
412 fprint(stream,mantstring);
413 for (uintL i = mantlen; i < scale; i++)
414 fprintchar(stream,'0');
415 fprintchar(stream,'.');
416 fprintchar(stream,'0');
418 expo = expo - scale; // der auszugebende Exponent ist um scale kleiner.
420 // Nun geht's zum Exponenten:
428 if (!flags.float_readably) {
429 floatformatcase(flags.default_float_format
430 , if (exp_marker=='s') { exp_marker = 'E'; }
431 , if (exp_marker=='f') { exp_marker = 'E'; }
432 , if (exp_marker=='d') { exp_marker = 'E'; }
433 , if ((exp_marker=='L') && (len == TheLfloat(z)->len)) { exp_marker = 'E'; }
436 if (!(flag && (exp_marker=='E'))) { // evtl. Exponent ganz weglassen
437 fprintchar(stream,exp_marker);
438 print_integer(stream,10,expo);
440 // Fertig. Aufräumen.
441 cl_free_hook(mantstring);