1*89b56da7SAndrew Rist /**************************************************************
2*89b56da7SAndrew Rist *
3*89b56da7SAndrew Rist * Licensed to the Apache Software Foundation (ASF) under one
4*89b56da7SAndrew Rist * or more contributor license agreements. See the NOTICE file
5*89b56da7SAndrew Rist * distributed with this work for additional information
6*89b56da7SAndrew Rist * regarding copyright ownership. The ASF licenses this file
7*89b56da7SAndrew Rist * to you under the Apache License, Version 2.0 (the
8*89b56da7SAndrew Rist * "License"); you may not use this file except in compliance
9*89b56da7SAndrew Rist * with the License. You may obtain a copy of the License at
10*89b56da7SAndrew Rist *
11*89b56da7SAndrew Rist * http://www.apache.org/licenses/LICENSE-2.0
12cdf0e10cSrcweir *
13*89b56da7SAndrew Rist * Unless required by applicable law or agreed to in writing,
14*89b56da7SAndrew Rist * software distributed under the License is distributed on an
15*89b56da7SAndrew Rist * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16*89b56da7SAndrew Rist * KIND, either express or implied. See the License for the
17*89b56da7SAndrew Rist * specific language governing permissions and limitations
18*89b56da7SAndrew Rist * under the License.
19*89b56da7SAndrew Rist *
20*89b56da7SAndrew Rist *************************************************************/
21*89b56da7SAndrew Rist
22*89b56da7SAndrew Rist
23cdf0e10cSrcweir
24cdf0e10cSrcweir // MARKER(update_precomp.py): autogen include statement, do not remove
25cdf0e10cSrcweir #include "precompiled_tools.hxx"
26cdf0e10cSrcweir
27cdf0e10cSrcweir #ifndef _LIMITS_H
28cdf0e10cSrcweir #include <limits.h>
29cdf0e10cSrcweir #endif
30cdf0e10cSrcweir #include <tools/debug.hxx>
31cdf0e10cSrcweir #include <tools/fract.hxx>
32cdf0e10cSrcweir #include <tools/stream.hxx>
33cdf0e10cSrcweir
34cdf0e10cSrcweir #include <tools/bigint.hxx>
35cdf0e10cSrcweir
36cdf0e10cSrcweir /*************************************************************************
37cdf0e10cSrcweir |*
38cdf0e10cSrcweir |* GetGGT()
39cdf0e10cSrcweir |*
40cdf0e10cSrcweir |* Beschreibung Berechnet den groessten gemeinsamen Teiler von
41cdf0e10cSrcweir |* nVal1 und nVal2
42cdf0e10cSrcweir |* Parameter long nVal1, long nVal2
43cdf0e10cSrcweir |* Ersterstellung DV 20.09.90
44cdf0e10cSrcweir |* Letzte Aenderung DV 21.12.92
45cdf0e10cSrcweir |*
46cdf0e10cSrcweir *************************************************************************/
47cdf0e10cSrcweir
48cdf0e10cSrcweir // Die Funktion GetGGT berechnet den groessten gemeinsamen Teiler der
49cdf0e10cSrcweir // beiden als Parameter uebergebenen Werte nVal1 und nVal2 nach dem
50cdf0e10cSrcweir // Algorithmus von Euklid. Hat einer der beiden Parameter den Wert 0 oder
51cdf0e10cSrcweir // 1, so wird als Ergebnis der Wert 1 zur�ckgegeben. Da der Algorithmus
52cdf0e10cSrcweir // nur mit positiven Zahlen arbeitet, werden die beiden Parameter
53cdf0e10cSrcweir // entsprechend umgewandelt.
54cdf0e10cSrcweir // Zum Algorithmus: die beiden Parameter werden solange ducheinander
55cdf0e10cSrcweir // geteilt, bis sie beide gleich sind oder bis bei der Division
56cdf0e10cSrcweir // kein Rest bleibt. Der kleinere der beiden Werte ist dann der
57cdf0e10cSrcweir // GGT.
58cdf0e10cSrcweir
GetGGT(long nVal1,long nVal2)59cdf0e10cSrcweir static long GetGGT( long nVal1, long nVal2 )
60cdf0e10cSrcweir {
61cdf0e10cSrcweir nVal1 = Abs( nVal1 );
62cdf0e10cSrcweir nVal2 = Abs( nVal2 );
63cdf0e10cSrcweir
64cdf0e10cSrcweir if ( nVal1 <= 1 || nVal2 <= 1 )
65cdf0e10cSrcweir return 1;
66cdf0e10cSrcweir
67cdf0e10cSrcweir while ( nVal1 != nVal2 )
68cdf0e10cSrcweir {
69cdf0e10cSrcweir if ( nVal1 > nVal2 )
70cdf0e10cSrcweir {
71cdf0e10cSrcweir nVal1 %= nVal2;
72cdf0e10cSrcweir if ( nVal1 == 0 )
73cdf0e10cSrcweir return nVal2;
74cdf0e10cSrcweir }
75cdf0e10cSrcweir else
76cdf0e10cSrcweir {
77cdf0e10cSrcweir nVal2 %= nVal1;
78cdf0e10cSrcweir if ( nVal2 == 0 )
79cdf0e10cSrcweir return nVal1;
80cdf0e10cSrcweir }
81cdf0e10cSrcweir }
82cdf0e10cSrcweir
83cdf0e10cSrcweir return nVal1;
84cdf0e10cSrcweir }
85cdf0e10cSrcweir
Reduce(BigInt & rVal1,BigInt & rVal2)86cdf0e10cSrcweir static void Reduce( BigInt &rVal1, BigInt &rVal2 )
87cdf0e10cSrcweir {
88cdf0e10cSrcweir BigInt nA( rVal1 );
89cdf0e10cSrcweir BigInt nB( rVal2 );
90cdf0e10cSrcweir nA.Abs();
91cdf0e10cSrcweir nB.Abs();
92cdf0e10cSrcweir
93cdf0e10cSrcweir if ( nA.IsOne() || nB.IsOne() || nA.IsZero() || nB.IsZero() )
94cdf0e10cSrcweir return;
95cdf0e10cSrcweir
96cdf0e10cSrcweir while ( nA != nB )
97cdf0e10cSrcweir {
98cdf0e10cSrcweir if ( nA > nB )
99cdf0e10cSrcweir {
100cdf0e10cSrcweir nA %= nB;
101cdf0e10cSrcweir if ( nA.IsZero() )
102cdf0e10cSrcweir {
103cdf0e10cSrcweir rVal1 /= nB;
104cdf0e10cSrcweir rVal2 /= nB;
105cdf0e10cSrcweir return;
106cdf0e10cSrcweir }
107cdf0e10cSrcweir }
108cdf0e10cSrcweir else
109cdf0e10cSrcweir {
110cdf0e10cSrcweir nB %= nA;
111cdf0e10cSrcweir if ( nB.IsZero() )
112cdf0e10cSrcweir {
113cdf0e10cSrcweir rVal1 /= nA;
114cdf0e10cSrcweir rVal2 /= nA;
115cdf0e10cSrcweir return;
116cdf0e10cSrcweir }
117cdf0e10cSrcweir }
118cdf0e10cSrcweir }
119cdf0e10cSrcweir
120cdf0e10cSrcweir rVal1 /= nA;
121cdf0e10cSrcweir rVal2 /= nB;
122cdf0e10cSrcweir }
123cdf0e10cSrcweir
124cdf0e10cSrcweir /*************************************************************************
125cdf0e10cSrcweir |*
126cdf0e10cSrcweir |* Fraction::Fraction()
127cdf0e10cSrcweir |*
128cdf0e10cSrcweir |* Beschreibung FRACT.SDW
129cdf0e10cSrcweir |* Ersterstellung WP 07.03.97
130cdf0e10cSrcweir |* Letzte Aenderung
131cdf0e10cSrcweir |*
132cdf0e10cSrcweir *************************************************************************/
133cdf0e10cSrcweir
Fraction(long nN1,long nN2,long nD1,long nD2)134cdf0e10cSrcweir Fraction::Fraction( long nN1, long nN2, long nD1, long nD2 )
135cdf0e10cSrcweir {
136cdf0e10cSrcweir long n;
137cdf0e10cSrcweir int i = 1;
138cdf0e10cSrcweir
139cdf0e10cSrcweir if( nN1 < 0 ) { i = -i; nN1 = -nN1; }
140cdf0e10cSrcweir if( nN2 < 0 ) { i = -i; nN2 = -nN2; }
141cdf0e10cSrcweir if( nD1 < 0 ) { i = -i; nD1 = -nD1; }
142cdf0e10cSrcweir if( nD2 < 0 ) { i = -i; nD2 = -nD2; }
143cdf0e10cSrcweir
144cdf0e10cSrcweir n = GetGGT( nN1, nD1 ); if( n > 1 ) { nN1 /= n; nD1 /= n; }
145cdf0e10cSrcweir n = GetGGT( nN1, nD2 ); if( n > 1 ) { nN1 /= n; nD2 /= n; }
146cdf0e10cSrcweir n = GetGGT( nN2, nD1 ); if( n > 1 ) { nN2 /= n; nD1 /= n; }
147cdf0e10cSrcweir n = GetGGT( nN2, nD2 ); if( n > 1 ) { nN2 /= n; nD2 /= n; }
148cdf0e10cSrcweir
149cdf0e10cSrcweir BigInt nN( nN1 );
150cdf0e10cSrcweir nN *= BigInt( nN2 );
151cdf0e10cSrcweir
152cdf0e10cSrcweir BigInt nD( nD1 );
153cdf0e10cSrcweir nD *= BigInt( nD2 );
154cdf0e10cSrcweir
155cdf0e10cSrcweir while ( nN.bIsBig || nD.bIsBig )
156cdf0e10cSrcweir {
157cdf0e10cSrcweir BigInt n1 = 1;
158cdf0e10cSrcweir BigInt n2 = 2;
159cdf0e10cSrcweir
160cdf0e10cSrcweir nN += n1;
161cdf0e10cSrcweir nN /= n2;
162cdf0e10cSrcweir nD += n1;
163cdf0e10cSrcweir nD /= n2;
164cdf0e10cSrcweir
165cdf0e10cSrcweir // Kuerzen ueber Groesste Gemeinsame Teiler
166cdf0e10cSrcweir Reduce( nN, nD );
167cdf0e10cSrcweir }
168cdf0e10cSrcweir
169cdf0e10cSrcweir nNumerator = i * (long)nN;
170cdf0e10cSrcweir nDenominator = (long)nD;
171cdf0e10cSrcweir }
172cdf0e10cSrcweir
173cdf0e10cSrcweir /*************************************************************************
174cdf0e10cSrcweir |*
175cdf0e10cSrcweir |* Fraction::Fraction()
176cdf0e10cSrcweir |*
177cdf0e10cSrcweir |* Beschreibung FRACT.SDW
178cdf0e10cSrcweir |* Ersterstellung DV 20.09.90
179cdf0e10cSrcweir |* Letzte Aenderung DV 21.12.92
180cdf0e10cSrcweir |*
181cdf0e10cSrcweir *************************************************************************/
182cdf0e10cSrcweir
183cdf0e10cSrcweir // Zur Initialisierung eines Bruches wird nNum dem Zaehler und nDen dem
184cdf0e10cSrcweir // Nenner zugewiesen. Da negative Werte des Nenners einen Bruch als
185cdf0e10cSrcweir // ungueltig kennzeichnen, wird bei der Eingabe eines negativen Nenners
186cdf0e10cSrcweir // sowohl das Vorzeichen des Nenners und des Zaehlers invertiert um wieder
187cdf0e10cSrcweir // einen gueltigen Wert fuer den Bruch zu erhalten.
188cdf0e10cSrcweir
Fraction(long nNum,long nDen)189cdf0e10cSrcweir Fraction::Fraction( long nNum, long nDen )
190cdf0e10cSrcweir {
191cdf0e10cSrcweir nNumerator = nNum;
192cdf0e10cSrcweir nDenominator = nDen;
193cdf0e10cSrcweir if ( nDenominator < 0 )
194cdf0e10cSrcweir {
195cdf0e10cSrcweir nDenominator = -nDenominator;
196cdf0e10cSrcweir nNumerator = -nNumerator;
197cdf0e10cSrcweir }
198cdf0e10cSrcweir
199cdf0e10cSrcweir // Kuerzen ueber Groesste Gemeinsame Teiler
200cdf0e10cSrcweir long n = GetGGT( nNumerator, nDenominator );
201cdf0e10cSrcweir nNumerator /= n;
202cdf0e10cSrcweir nDenominator /= n;
203cdf0e10cSrcweir }
204cdf0e10cSrcweir
205cdf0e10cSrcweir /*************************************************************************
206cdf0e10cSrcweir |*
207cdf0e10cSrcweir |* Fraction::Fraction()
208cdf0e10cSrcweir |*
209cdf0e10cSrcweir |* Beschreibung FRACT.SDW
210cdf0e10cSrcweir |* Ersterstellung DV 20.09.90
211cdf0e10cSrcweir |* Letzte Aenderung DV 21.12.92
212cdf0e10cSrcweir |*
213cdf0e10cSrcweir *************************************************************************/
214cdf0e10cSrcweir
215cdf0e10cSrcweir // Wenn der Wert von dVal groesser ist als LONG_MAX, dann wird der Bruch
216cdf0e10cSrcweir // auf den Wert ungueltig gesetzt, ansonsten werden dVal und der Nenner
217cdf0e10cSrcweir // solange mit 10 multipliziert, bis entweder der Zaehler oder der Nenner
218cdf0e10cSrcweir // groesser als LONG_MAX / 10 ist. Zum Schluss wird der so entstandene Bruch
219cdf0e10cSrcweir // gekuerzt.
220cdf0e10cSrcweir
Fraction(double dVal)221cdf0e10cSrcweir Fraction::Fraction( double dVal )
222cdf0e10cSrcweir {
223cdf0e10cSrcweir long nDen = 1;
224cdf0e10cSrcweir long nMAX = LONG_MAX / 10;
225cdf0e10cSrcweir
226cdf0e10cSrcweir if ( dVal > LONG_MAX || dVal < LONG_MIN )
227cdf0e10cSrcweir {
228cdf0e10cSrcweir nNumerator = 0;
229cdf0e10cSrcweir nDenominator = -1;
230cdf0e10cSrcweir return;
231cdf0e10cSrcweir }
232cdf0e10cSrcweir
233cdf0e10cSrcweir while ( Abs( (long)dVal ) < nMAX && nDen < nMAX )
234cdf0e10cSrcweir {
235cdf0e10cSrcweir dVal *= 10;
236cdf0e10cSrcweir nDen *= 10;
237cdf0e10cSrcweir }
238cdf0e10cSrcweir nNumerator = (long)dVal;
239cdf0e10cSrcweir nDenominator = nDen;
240cdf0e10cSrcweir
241cdf0e10cSrcweir // Kuerzen ueber Groesste Gemeinsame Teiler
242cdf0e10cSrcweir long n = GetGGT( nNumerator, nDenominator );
243cdf0e10cSrcweir nNumerator /= n;
244cdf0e10cSrcweir nDenominator /= n;
245cdf0e10cSrcweir }
246cdf0e10cSrcweir
247cdf0e10cSrcweir /*************************************************************************
248cdf0e10cSrcweir |*
249cdf0e10cSrcweir |* Fraction::operator double()
250cdf0e10cSrcweir |*
251cdf0e10cSrcweir |* Beschreibung FRACT.SDW
252cdf0e10cSrcweir |* Ersterstellung DV 20.09.90
253cdf0e10cSrcweir |* Letzte Aenderung DV 14.05.91
254cdf0e10cSrcweir |*
255cdf0e10cSrcweir *************************************************************************/
256cdf0e10cSrcweir
257cdf0e10cSrcweir Fraction::operator double() const
258cdf0e10cSrcweir {
259cdf0e10cSrcweir if ( nDenominator > 0 )
260cdf0e10cSrcweir return (double)nNumerator / (double)nDenominator;
261cdf0e10cSrcweir else
262cdf0e10cSrcweir return (double)0;
263cdf0e10cSrcweir }
264cdf0e10cSrcweir
265cdf0e10cSrcweir /*************************************************************************
266cdf0e10cSrcweir |*
267cdf0e10cSrcweir |* Fraction::operator+=()
268cdf0e10cSrcweir |*
269cdf0e10cSrcweir |* Beschreibung FRACT.SDW
270cdf0e10cSrcweir |* Ersterstellung DV 20.09.90
271cdf0e10cSrcweir |* Letzte Aenderung DV 21.12.92
272cdf0e10cSrcweir |*
273cdf0e10cSrcweir *************************************************************************/
274cdf0e10cSrcweir
275cdf0e10cSrcweir // Zunaechst werden die beiden Parameter auf ihre Gueltigkeit ueberprueft.
276cdf0e10cSrcweir // Ist einer der Parameter ungueltig, dann ist auch des Ergebnis
277cdf0e10cSrcweir // ungueltig. Zur Addition werden die beiden Brueche erst durch
278cdf0e10cSrcweir // Erweiterung mit den Nenner des jeweils anderen Bruches auf einen
279cdf0e10cSrcweir // gemeinsamen Nenner gebracht. Anschliessend werden die beiden Zaehler
280cdf0e10cSrcweir // addiert und das Ergebnis gekuerzt (durch Division von Zaehler und
281cdf0e10cSrcweir // Nenner mit nGGT). Innerhalb der Funktion wird mit dem Datentyp SLong
282cdf0e10cSrcweir // gerechnet, um einen Moeglichen Ueberlauf erkennen zu koennen. Bei
283cdf0e10cSrcweir // einem Ueberlauf wird das Ergebnis auf den Wert ungueltig gesetzt.
284cdf0e10cSrcweir
operator +=(const Fraction & rVal)285cdf0e10cSrcweir Fraction& Fraction::operator += ( const Fraction& rVal )
286cdf0e10cSrcweir {
287cdf0e10cSrcweir if ( !rVal.IsValid() )
288cdf0e10cSrcweir {
289cdf0e10cSrcweir nNumerator = 0;
290cdf0e10cSrcweir nDenominator = -1;
291cdf0e10cSrcweir }
292cdf0e10cSrcweir if ( !IsValid() )
293cdf0e10cSrcweir return *this;
294cdf0e10cSrcweir
295cdf0e10cSrcweir // (a/b) + (c/d) = ( (a*d) + (c*b) ) / (b*d)
296cdf0e10cSrcweir BigInt nN( nNumerator );
297cdf0e10cSrcweir nN *= BigInt( rVal.nDenominator );
298cdf0e10cSrcweir BigInt nW1Temp( nDenominator );
299cdf0e10cSrcweir nW1Temp *= BigInt( rVal.nNumerator );
300cdf0e10cSrcweir nN += nW1Temp;
301cdf0e10cSrcweir
302cdf0e10cSrcweir BigInt nD( nDenominator );
303cdf0e10cSrcweir nD *= BigInt( rVal.nDenominator );
304cdf0e10cSrcweir
305cdf0e10cSrcweir Reduce( nN, nD );
306cdf0e10cSrcweir
307cdf0e10cSrcweir if ( nN.bIsBig || nD.bIsBig )
308cdf0e10cSrcweir {
309cdf0e10cSrcweir nNumerator = 0;
310cdf0e10cSrcweir nDenominator = -1;
311cdf0e10cSrcweir }
312cdf0e10cSrcweir else
313cdf0e10cSrcweir {
314cdf0e10cSrcweir nNumerator = (long)nN,
315cdf0e10cSrcweir nDenominator = (long)nD;
316cdf0e10cSrcweir }
317cdf0e10cSrcweir
318cdf0e10cSrcweir return *this;
319cdf0e10cSrcweir }
320cdf0e10cSrcweir
321cdf0e10cSrcweir /*************************************************************************
322cdf0e10cSrcweir |*
323cdf0e10cSrcweir |* Fraction::operator-=()
324cdf0e10cSrcweir |*
325cdf0e10cSrcweir |* Beschreibung FRACT.SDW
326cdf0e10cSrcweir |* Ersterstellung DV 20.09.90
327cdf0e10cSrcweir |* Letzte Aenderung DV 21.12.92
328cdf0e10cSrcweir |*
329cdf0e10cSrcweir *************************************************************************/
330cdf0e10cSrcweir
331cdf0e10cSrcweir // Zunaechst werden die beiden Parameter auf ihre Gueltigkeit ueberprueft.
332cdf0e10cSrcweir // Ist einer der Parameter ungueltig, dann ist auch des Ergebnis
333cdf0e10cSrcweir // ungueltig. Zur Subtraktion werden die beiden Brueche erst durch
334cdf0e10cSrcweir // Erweiterung mit den Nenner des jeweils anderen Bruches auf einen
335cdf0e10cSrcweir // gemeinsamen Nenner gebracht. Anschliessend werden die beiden Zaehler
336cdf0e10cSrcweir // subtrahiert und das Ergebnis gekuerzt (durch Division von Zaehler und
337cdf0e10cSrcweir // Nenner mit nGGT). Innerhalb der Funktion wird mit dem Datentyp BigInt
338cdf0e10cSrcweir // gerechnet, um einen Moeglichen Ueberlauf erkennen zu koennen. Bei
339cdf0e10cSrcweir // einem Ueberlauf wird das Ergebnis auf den Wert ungueltig gesetzt.
340cdf0e10cSrcweir
operator -=(const Fraction & rVal)341cdf0e10cSrcweir Fraction& Fraction::operator -= ( const Fraction& rVal )
342cdf0e10cSrcweir {
343cdf0e10cSrcweir if ( !rVal.IsValid() )
344cdf0e10cSrcweir {
345cdf0e10cSrcweir nNumerator = 0;
346cdf0e10cSrcweir nDenominator = -1;
347cdf0e10cSrcweir }
348cdf0e10cSrcweir if ( !IsValid() )
349cdf0e10cSrcweir return *this;
350cdf0e10cSrcweir
351cdf0e10cSrcweir // (a/b) - (c/d) = ( (a*d) - (c*b) ) / (b*d)
352cdf0e10cSrcweir BigInt nN( nNumerator );
353cdf0e10cSrcweir nN *= BigInt( rVal.nDenominator );
354cdf0e10cSrcweir BigInt nW1Temp( nDenominator );
355cdf0e10cSrcweir nW1Temp *= BigInt( rVal.nNumerator );
356cdf0e10cSrcweir nN -= nW1Temp;
357cdf0e10cSrcweir
358cdf0e10cSrcweir BigInt nD( nDenominator );
359cdf0e10cSrcweir nD *= BigInt( rVal.nDenominator );
360cdf0e10cSrcweir
361cdf0e10cSrcweir Reduce( nN, nD );
362cdf0e10cSrcweir
363cdf0e10cSrcweir if ( nN.bIsBig || nD.bIsBig )
364cdf0e10cSrcweir {
365cdf0e10cSrcweir nNumerator = 0;
366cdf0e10cSrcweir nDenominator = -1;
367cdf0e10cSrcweir }
368cdf0e10cSrcweir else
369cdf0e10cSrcweir {
370cdf0e10cSrcweir nNumerator = (long)nN,
371cdf0e10cSrcweir nDenominator = (long)nD;
372cdf0e10cSrcweir }
373cdf0e10cSrcweir
374cdf0e10cSrcweir return *this;
375cdf0e10cSrcweir }
376cdf0e10cSrcweir
377cdf0e10cSrcweir /*************************************************************************
378cdf0e10cSrcweir |*
379cdf0e10cSrcweir |* Fraction::operator*=()
380cdf0e10cSrcweir |*
381cdf0e10cSrcweir |* Beschreibung FRACT.SDW
382cdf0e10cSrcweir |* Ersterstellung DV 20.09.90
383cdf0e10cSrcweir |* Letzte Aenderung TH 19.08.92
384cdf0e10cSrcweir |*
385cdf0e10cSrcweir *************************************************************************/
386cdf0e10cSrcweir
387cdf0e10cSrcweir // Zunaechst werden die beiden Parameter auf ihre Gueltigkeit ueberprueft.
388cdf0e10cSrcweir // Ist einer der Parameter ungueltig, dann ist auch des Ergebnis
389cdf0e10cSrcweir // ungueltig. Zur Multiplikation werden jeweils die beiden Zaehler und
390cdf0e10cSrcweir // Nenner miteinander multipliziert. Um Ueberlaufe zu vermeiden, werden
391cdf0e10cSrcweir // vorher jeweils der GGT zwischen dem Zaehler des einen und dem Nenner
392cdf0e10cSrcweir // des anderen Bruches bestimmt und bei der Multiplikation Zaehler und
393cdf0e10cSrcweir // Nenner durch die entsprechenden Werte geteilt.
394cdf0e10cSrcweir // Innerhalb der Funktion wird mit dem Datentyp BigInt gerechnet, um
395cdf0e10cSrcweir // einen Moeglichen Ueberlauf erkennen zu koennen. Bei einem Ueberlauf
396cdf0e10cSrcweir // wird das Ergebnis auf den Wert ungueltig gesetzt.
397cdf0e10cSrcweir
operator *=(const Fraction & rVal)398cdf0e10cSrcweir Fraction& Fraction::operator *= ( const Fraction& rVal )
399cdf0e10cSrcweir {
400cdf0e10cSrcweir if ( !rVal.IsValid() )
401cdf0e10cSrcweir {
402cdf0e10cSrcweir nNumerator = 0;
403cdf0e10cSrcweir nDenominator = -1;
404cdf0e10cSrcweir }
405cdf0e10cSrcweir if ( !IsValid() )
406cdf0e10cSrcweir return *this;
407cdf0e10cSrcweir
408cdf0e10cSrcweir long nGGT1 = GetGGT( nNumerator, rVal.nDenominator );
409cdf0e10cSrcweir long nGGT2 = GetGGT( rVal.nNumerator, nDenominator );
410cdf0e10cSrcweir BigInt nN( nNumerator / nGGT1 );
411cdf0e10cSrcweir nN *= BigInt( rVal.nNumerator / nGGT2 );
412cdf0e10cSrcweir BigInt nD( nDenominator / nGGT2 );
413cdf0e10cSrcweir nD *= BigInt( rVal.nDenominator / nGGT1 );
414cdf0e10cSrcweir
415cdf0e10cSrcweir if ( nN.bIsBig || nD.bIsBig )
416cdf0e10cSrcweir {
417cdf0e10cSrcweir nNumerator = 0;
418cdf0e10cSrcweir nDenominator = -1;
419cdf0e10cSrcweir }
420cdf0e10cSrcweir else
421cdf0e10cSrcweir {
422cdf0e10cSrcweir nNumerator = (long)nN,
423cdf0e10cSrcweir nDenominator = (long)nD;
424cdf0e10cSrcweir }
425cdf0e10cSrcweir
426cdf0e10cSrcweir return *this;
427cdf0e10cSrcweir }
428cdf0e10cSrcweir
429cdf0e10cSrcweir /*************************************************************************
430cdf0e10cSrcweir |*
431cdf0e10cSrcweir |* Fraction::operator/=()
432cdf0e10cSrcweir |*
433cdf0e10cSrcweir |* Beschreibung FRACT.SDW
434cdf0e10cSrcweir |* Ersterstellung DV 20.09.90
435cdf0e10cSrcweir |* Letzte Aenderung DV 21.12.92
436cdf0e10cSrcweir |*
437cdf0e10cSrcweir *************************************************************************/
438cdf0e10cSrcweir
439cdf0e10cSrcweir // Zunaechst werden die beiden Parameter auf ihre Gueltigkeit ueberprueft.
440cdf0e10cSrcweir // Ist einer der Parameter ungueltig, dann ist auch des Ergebnis
441cdf0e10cSrcweir // ungueltig.
442cdf0e10cSrcweir // Um den Bruch a durch b zu teilen, wird a mit dem Kehrwert von b
443cdf0e10cSrcweir // multipliziert. Analog zu Multiplikation wird jezt jeweils der Zaehler
444cdf0e10cSrcweir // des einen Bruches mit dem Nenner des anderen multipliziert.
445cdf0e10cSrcweir // Um Ueberlaufe zu vermeiden, werden vorher jeweils der GGT zwischen den
446cdf0e10cSrcweir // beiden Zaehlern und den beiden Nennern bestimmt und bei der
447cdf0e10cSrcweir // Multiplikation Zaehler und Nenner durch die entsprechenden Werte
448cdf0e10cSrcweir // geteilt.
449cdf0e10cSrcweir // Innerhalb der Funktion wird mit dem Datentyp BigInt gerechnet, um
450cdf0e10cSrcweir // einen Moeglichen Ueberlauf erkennen zu koennen. Bei einem Ueberlauf
451cdf0e10cSrcweir // wird das Ergebnis auf den Wert ungueltig gesetzt.
452cdf0e10cSrcweir
operator /=(const Fraction & rVal)453cdf0e10cSrcweir Fraction& Fraction::operator /= ( const Fraction& rVal )
454cdf0e10cSrcweir {
455cdf0e10cSrcweir if ( !rVal.IsValid() )
456cdf0e10cSrcweir {
457cdf0e10cSrcweir nNumerator = 0;
458cdf0e10cSrcweir nDenominator = -1;
459cdf0e10cSrcweir }
460cdf0e10cSrcweir if ( !IsValid() )
461cdf0e10cSrcweir return *this;
462cdf0e10cSrcweir
463cdf0e10cSrcweir long nGGT1 = GetGGT( nNumerator, rVal.nNumerator );
464cdf0e10cSrcweir long nGGT2 = GetGGT( rVal.nDenominator, nDenominator );
465cdf0e10cSrcweir BigInt nN( nNumerator / nGGT1 );
466cdf0e10cSrcweir nN *= BigInt( rVal.nDenominator / nGGT2 );
467cdf0e10cSrcweir BigInt nD( nDenominator / nGGT2 );
468cdf0e10cSrcweir nD *= BigInt( rVal.nNumerator / nGGT1 );
469cdf0e10cSrcweir
470cdf0e10cSrcweir if ( nN.bIsBig || nD.bIsBig )
471cdf0e10cSrcweir {
472cdf0e10cSrcweir nNumerator = 0;
473cdf0e10cSrcweir nDenominator = -1;
474cdf0e10cSrcweir }
475cdf0e10cSrcweir else
476cdf0e10cSrcweir {
477cdf0e10cSrcweir nNumerator = (long)nN,
478cdf0e10cSrcweir nDenominator = (long)nD;
479cdf0e10cSrcweir if ( nDenominator < 0 )
480cdf0e10cSrcweir {
481cdf0e10cSrcweir nDenominator = -nDenominator;
482cdf0e10cSrcweir nNumerator = -nNumerator;
483cdf0e10cSrcweir }
484cdf0e10cSrcweir }
485cdf0e10cSrcweir
486cdf0e10cSrcweir return *this;
487cdf0e10cSrcweir }
488cdf0e10cSrcweir
489cdf0e10cSrcweir /*************************************************************************
490cdf0e10cSrcweir |*
491cdf0e10cSrcweir |* Fraction::ReduceInaccurate()
492cdf0e10cSrcweir |*
493cdf0e10cSrcweir |* Beschreibung FRACT.SDW
494cdf0e10cSrcweir |* Ersterstellung JOE 17.09.95
495cdf0e10cSrcweir |* Letzte Aenderung kendy 2007-06-13
496cdf0e10cSrcweir |*
497cdf0e10cSrcweir *************************************************************************/
498cdf0e10cSrcweir
499cdf0e10cSrcweir
500cdf0e10cSrcweir // Similar to clz_table that can be googled
501cdf0e10cSrcweir const char nbits_table[32] =
502cdf0e10cSrcweir {
503cdf0e10cSrcweir 32, 1, 23, 2, 29, 24, 14, 3,
504cdf0e10cSrcweir 30, 27, 25, 18, 20, 15, 10, 4,
505cdf0e10cSrcweir 31, 22, 28, 13, 26, 17, 19, 9,
506cdf0e10cSrcweir 21, 12, 16, 8, 11, 7, 6, 5
507cdf0e10cSrcweir };
508cdf0e10cSrcweir
impl_NumberOfBits(unsigned long nNum)509cdf0e10cSrcweir static int impl_NumberOfBits( unsigned long nNum )
510cdf0e10cSrcweir {
511cdf0e10cSrcweir // http://en.wikipedia.org/wiki/De_Bruijn_sequence
512cdf0e10cSrcweir //
513cdf0e10cSrcweir // background paper: Using de Bruijn Sequences to Index a 1 in a
514cdf0e10cSrcweir // Computer Word (1998) Charles E. Leiserson,
515cdf0e10cSrcweir // Harald Prokop, Keith H. Randall
516cdf0e10cSrcweir // (e.g. http://citeseer.ist.psu.edu/leiserson98using.html)
517cdf0e10cSrcweir const sal_uInt32 nDeBruijn = 0x7DCD629;
518cdf0e10cSrcweir
519cdf0e10cSrcweir if ( nNum == 0 )
520cdf0e10cSrcweir return 0;
521cdf0e10cSrcweir
522cdf0e10cSrcweir // Get it to form like 0000001111111111b
523cdf0e10cSrcweir nNum |= ( nNum >> 1 );
524cdf0e10cSrcweir nNum |= ( nNum >> 2 );
525cdf0e10cSrcweir nNum |= ( nNum >> 4 );
526cdf0e10cSrcweir nNum |= ( nNum >> 8 );
527cdf0e10cSrcweir nNum |= ( nNum >> 16 );
528cdf0e10cSrcweir
529cdf0e10cSrcweir sal_uInt32 nNumber;
530cdf0e10cSrcweir int nBonus = 0;
531cdf0e10cSrcweir
532cdf0e10cSrcweir #if SAL_TYPES_SIZEOFLONG == 4
533cdf0e10cSrcweir nNumber = nNum;
534cdf0e10cSrcweir #elif SAL_TYPES_SIZEOFLONG == 8
535cdf0e10cSrcweir nNum |= ( nNum >> 32 );
536cdf0e10cSrcweir
537cdf0e10cSrcweir if ( nNum & 0x80000000 )
538cdf0e10cSrcweir {
539cdf0e10cSrcweir nNumber = sal_uInt32( nNum >> 32 );
540cdf0e10cSrcweir nBonus = 32;
541cdf0e10cSrcweir
542cdf0e10cSrcweir if ( nNumber == 0 )
543cdf0e10cSrcweir return 32;
544cdf0e10cSrcweir }
545cdf0e10cSrcweir else
546cdf0e10cSrcweir nNumber = sal_uInt32( nNum & 0xFFFFFFFF );
547cdf0e10cSrcweir #else
548cdf0e10cSrcweir #error "Unknown size of long!"
549cdf0e10cSrcweir #endif
550cdf0e10cSrcweir
551cdf0e10cSrcweir // De facto shift left of nDeBruijn using multiplication (nNumber
552cdf0e10cSrcweir // is all ones from topmost bit, thus nDeBruijn + (nDeBruijn *
553cdf0e10cSrcweir // nNumber) => nDeBruijn * (nNumber+1) clears all those bits to
554cdf0e10cSrcweir // zero, sets the next bit to one, and thus effectively shift-left
555cdf0e10cSrcweir // nDeBruijn by lg2(nNumber+1). This generates a distinct 5bit
556cdf0e10cSrcweir // sequence in the msb for each distinct position of the last
557cdf0e10cSrcweir // leading 0 bit - that's the property of a de Bruijn number.
558cdf0e10cSrcweir nNumber = nDeBruijn + ( nDeBruijn * nNumber );
559cdf0e10cSrcweir
560cdf0e10cSrcweir // 5-bit window indexes the result
561cdf0e10cSrcweir return ( nbits_table[nNumber >> 27] ) + nBonus;
562cdf0e10cSrcweir }
563cdf0e10cSrcweir
564cdf0e10cSrcweir /** Inaccurate cancellation for a fraction.
565cdf0e10cSrcweir
566cdf0e10cSrcweir Clip both nominator and denominator to said number of bits. If
567cdf0e10cSrcweir either of those already have equal or less number of bits used,
568cdf0e10cSrcweir this method does nothing.
569cdf0e10cSrcweir
570cdf0e10cSrcweir @param nSignificantBits denotes, how many significant binary
571cdf0e10cSrcweir digits to maintain, in both nominator and denominator.
572cdf0e10cSrcweir
573cdf0e10cSrcweir @example ReduceInaccurate(8) has an error <1% [1/2^(8-1)] - the
574cdf0e10cSrcweir largest error occurs with the following pair of values:
575cdf0e10cSrcweir
576cdf0e10cSrcweir binary 1000000011111111111111111111111b/1000000000000000000000000000000b
577cdf0e10cSrcweir = 1082130431/1073741824
578cdf0e10cSrcweir = approx. 1.007812499
579cdf0e10cSrcweir
580cdf0e10cSrcweir A ReduceInaccurate(8) yields 1/1.
581cdf0e10cSrcweir */
ReduceInaccurate(unsigned nSignificantBits)582cdf0e10cSrcweir void Fraction::ReduceInaccurate( unsigned nSignificantBits )
583cdf0e10cSrcweir {
584cdf0e10cSrcweir if ( !nNumerator || !nDenominator )
585cdf0e10cSrcweir return;
586cdf0e10cSrcweir
587cdf0e10cSrcweir // Count with unsigned longs only
588cdf0e10cSrcweir const bool bNeg = ( nNumerator < 0 );
589cdf0e10cSrcweir unsigned long nMul = (unsigned long)( bNeg? -nNumerator: nNumerator );
590cdf0e10cSrcweir unsigned long nDiv = (unsigned long)( nDenominator );
591cdf0e10cSrcweir
592cdf0e10cSrcweir DBG_ASSERT(nSignificantBits<65, "More than 64 bit of significance is overkill!");
593cdf0e10cSrcweir
594cdf0e10cSrcweir // How much bits can we lose?
595cdf0e10cSrcweir const int nMulBitsToLose = Max( ( impl_NumberOfBits( nMul ) - int( nSignificantBits ) ), 0 );
596cdf0e10cSrcweir const int nDivBitsToLose = Max( ( impl_NumberOfBits( nDiv ) - int( nSignificantBits ) ), 0 );
597cdf0e10cSrcweir
598cdf0e10cSrcweir const int nToLose = Min( nMulBitsToLose, nDivBitsToLose );
599cdf0e10cSrcweir
600cdf0e10cSrcweir // Remove the bits
601cdf0e10cSrcweir nMul >>= nToLose;
602cdf0e10cSrcweir nDiv >>= nToLose;
603cdf0e10cSrcweir
604cdf0e10cSrcweir if ( !nMul || !nDiv )
605cdf0e10cSrcweir {
606cdf0e10cSrcweir // Return without reduction
607cdf0e10cSrcweir DBG_ERROR( "Oops, we reduced too much..." );
608cdf0e10cSrcweir return;
609cdf0e10cSrcweir }
610cdf0e10cSrcweir
611cdf0e10cSrcweir // Reduce
612cdf0e10cSrcweir long n1 = GetGGT( nMul, nDiv );
613cdf0e10cSrcweir if ( n1 != 1 )
614cdf0e10cSrcweir {
615cdf0e10cSrcweir nMul /= n1;
616cdf0e10cSrcweir nDiv /= n1;
617cdf0e10cSrcweir }
618cdf0e10cSrcweir
619cdf0e10cSrcweir nNumerator = bNeg? -long( nMul ): long( nMul );
620cdf0e10cSrcweir nDenominator = nDiv;
621cdf0e10cSrcweir }
622cdf0e10cSrcweir
623cdf0e10cSrcweir /*************************************************************************
624cdf0e10cSrcweir |*
625cdf0e10cSrcweir |* Fraction::operator ==()
626cdf0e10cSrcweir |*
627cdf0e10cSrcweir |* Beschreibung FRACT.SDW
628cdf0e10cSrcweir |* Ersterstellung DV 20.09.90
629cdf0e10cSrcweir |* Letzte Aenderung TH 19.08.92
630cdf0e10cSrcweir |*
631cdf0e10cSrcweir *************************************************************************/
632cdf0e10cSrcweir
operator ==(const Fraction & rVal1,const Fraction & rVal2)633cdf0e10cSrcweir sal_Bool operator == ( const Fraction& rVal1, const Fraction& rVal2 )
634cdf0e10cSrcweir {
635cdf0e10cSrcweir if ( !rVal1.IsValid() || !rVal2.IsValid() )
636cdf0e10cSrcweir return sal_False;
637cdf0e10cSrcweir
638cdf0e10cSrcweir return rVal1.nNumerator == rVal2.nNumerator
639cdf0e10cSrcweir && rVal1.nDenominator == rVal2.nDenominator;
640cdf0e10cSrcweir }
641cdf0e10cSrcweir
642cdf0e10cSrcweir /*************************************************************************
643cdf0e10cSrcweir |*
644cdf0e10cSrcweir |* Fraction::operator <()
645cdf0e10cSrcweir |*
646cdf0e10cSrcweir |* Beschreibung FRACT.SDW
647cdf0e10cSrcweir |* Ersterstellung DV 20.09.90
648cdf0e10cSrcweir |* Letzte Aenderung DV 21.12.92
649cdf0e10cSrcweir |*
650cdf0e10cSrcweir *************************************************************************/
651cdf0e10cSrcweir
652cdf0e10cSrcweir // Beide Operanden werden zunaechst auf ihre Gueltigkeit ueberprueft und
653cdf0e10cSrcweir // anschliessend zur Sicherheit noch einmal gekuerzt. Um die Brueche
654cdf0e10cSrcweir // (a/b) und (c/d) zu vergleichen, werden sie zunaechst auf einen
655cdf0e10cSrcweir // gemeinsamen Nenner gebracht (b*d), um dann die beiden Zaehler (a*d)
656cdf0e10cSrcweir // und (c*b) zu vergleichen. Das Ergebnis dieses Vergleichs wird
657cdf0e10cSrcweir // zurueckgegeben.
658cdf0e10cSrcweir
operator <(const Fraction & rVal1,const Fraction & rVal2)659cdf0e10cSrcweir sal_Bool operator < ( const Fraction& rVal1, const Fraction& rVal2 )
660cdf0e10cSrcweir {
661cdf0e10cSrcweir if ( !rVal1.IsValid() || !rVal2.IsValid() )
662cdf0e10cSrcweir return sal_False;
663cdf0e10cSrcweir
664cdf0e10cSrcweir BigInt nN( rVal1.nNumerator );
665cdf0e10cSrcweir nN *= BigInt( rVal2.nDenominator );
666cdf0e10cSrcweir BigInt nD( rVal1.nDenominator );
667cdf0e10cSrcweir nD *= BigInt( rVal2.nNumerator );
668cdf0e10cSrcweir
669cdf0e10cSrcweir return nN < nD;
670cdf0e10cSrcweir }
671cdf0e10cSrcweir
672cdf0e10cSrcweir /*************************************************************************
673cdf0e10cSrcweir |*
674cdf0e10cSrcweir |* Fraction::operator >()
675cdf0e10cSrcweir |*
676cdf0e10cSrcweir |* Beschreibung FRACT.SDW
677cdf0e10cSrcweir |* Ersterstellung DV 20.09.90
678cdf0e10cSrcweir |* Letzte Aenderung TH 19.08.92
679cdf0e10cSrcweir |*
680cdf0e10cSrcweir *************************************************************************/
681cdf0e10cSrcweir
682cdf0e10cSrcweir // Beide Operanden werden zunaechst auf ihre Gueltigkeit ueberprueft und
683cdf0e10cSrcweir // anschliessend zur Sicherheit noch einmal gekuerzt. Um die Brueche
684cdf0e10cSrcweir // (a/b) und (c/d) zu vergleichen, werden sie zunaechst auf einen
685cdf0e10cSrcweir // gemeinsamen Nenner gebracht (b*d), um dann die beiden Zaehler (a*d)
686cdf0e10cSrcweir // und (c*b) zu vergleichen. Das Ergebnis dieses Vergleichs wird
687cdf0e10cSrcweir // zurueckgegeben.
688cdf0e10cSrcweir
operator >(const Fraction & rVal1,const Fraction & rVal2)689cdf0e10cSrcweir sal_Bool operator > ( const Fraction& rVal1, const Fraction& rVal2 )
690cdf0e10cSrcweir {
691cdf0e10cSrcweir if ( !rVal1.IsValid() || !rVal2.IsValid() )
692cdf0e10cSrcweir return sal_False;
693cdf0e10cSrcweir
694cdf0e10cSrcweir BigInt nN( rVal1.nNumerator );
695cdf0e10cSrcweir nN *= BigInt( rVal2.nDenominator );
696cdf0e10cSrcweir BigInt nD( rVal1.nDenominator);
697cdf0e10cSrcweir nD *= BigInt( rVal2.nNumerator );
698cdf0e10cSrcweir
699cdf0e10cSrcweir return nN > nD;
700cdf0e10cSrcweir }
701cdf0e10cSrcweir
702cdf0e10cSrcweir /*************************************************************************
703cdf0e10cSrcweir |*
704cdf0e10cSrcweir |* SvStream& operator>>( SvStream& rIStream, Fraction& rFract )
705cdf0e10cSrcweir |*
706cdf0e10cSrcweir |* Beschreibung FRACT.SDW
707cdf0e10cSrcweir |* Ersterstellung MM 08.01.96
708cdf0e10cSrcweir |* Letzte Aenderung MM 08.01.96
709cdf0e10cSrcweir |*
710cdf0e10cSrcweir *************************************************************************/
operator >>(SvStream & rIStream,Fraction & rFract)711cdf0e10cSrcweir SvStream& operator >> ( SvStream& rIStream, Fraction& rFract )
712cdf0e10cSrcweir {
713cdf0e10cSrcweir rIStream >> rFract.nNumerator;
714cdf0e10cSrcweir rIStream >> rFract.nDenominator;
715cdf0e10cSrcweir return rIStream;
716cdf0e10cSrcweir }
717cdf0e10cSrcweir
718cdf0e10cSrcweir /*************************************************************************
719cdf0e10cSrcweir |*
720cdf0e10cSrcweir |* SvStream& operator<<( SvStream& rIStream, Fraction& rFract )
721cdf0e10cSrcweir |*
722cdf0e10cSrcweir |* Beschreibung FRACT.SDW
723cdf0e10cSrcweir |* Ersterstellung MM 08.01.96
724cdf0e10cSrcweir |* Letzte Aenderung MM 08.01.96
725cdf0e10cSrcweir |*
726cdf0e10cSrcweir *************************************************************************/
operator <<(SvStream & rOStream,const Fraction & rFract)727cdf0e10cSrcweir SvStream& operator << ( SvStream& rOStream, const Fraction& rFract )
728cdf0e10cSrcweir {
729cdf0e10cSrcweir rOStream << rFract.nNumerator;
730cdf0e10cSrcweir rOStream << rFract.nDenominator;
731cdf0e10cSrcweir return rOStream;
732cdf0e10cSrcweir }
733