1 /* Rational - Rational number class with overflow detection
2 Copyright (C) 2005-2020 Antonio Diaz Diaz.
3
4 This library is free software. Redistribution and use in source and
5 binary forms, with or without modification, are permitted provided
6 that the following conditions are met:
7
8 1. Redistributions of source code must retain the above copyright
9 notice, this list of conditions, and the following disclaimer.
10
11 2. Redistributions in binary form must reproduce the above copyright
12 notice, this list of conditions, and the following disclaimer in the
13 documentation and/or other materials provided with the distribution.
14
15 This library is distributed in the hope that it will be useful,
16 but WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
18 */
19
20 #include <algorithm>
21 #include <cctype>
22 #include <climits>
23 #include <cstdlib>
24 #include <string>
25
26 #include "rational.h"
27
28 #ifndef LLONG_MAX
29 #define LLONG_MAX 0x7FFFFFFFFFFFFFFFLL
30 #endif
31 #ifndef LLONG_MIN
32 #define LLONG_MIN (-LLONG_MAX - 1LL)
33 #endif
34 #ifndef ULLONG_MAX
35 #define ULLONG_MAX 0xFFFFFFFFFFFFFFFFULL
36 #endif
37
38
39 namespace {
40
gcd(long long n,long long m)41 long long gcd( long long n, long long m ) // Greatest Common Divisor
42 {
43 if( n < 0 ) n = -n;
44 if( m < 0 ) m = -m;
45
46 while( true )
47 {
48 if( m ) n %= m; else return n;
49 if( n ) m %= n; else return m;
50 }
51 }
52
53
overflow_string(const int n)54 std::string overflow_string( const int n )
55 { if( n > 0 ) return "+INF"; if( n < 0 ) return "-INF"; return "NAN"; }
56
overflow_value(const long long n,const bool negate=false)57 int overflow_value( const long long n, const bool negate = false )
58 {
59 if( negate )
60 { if( n > 0 ) return -INT_MAX; if( n < 0 ) return INT_MAX; return 0; }
61 else
62 { if( n > 0 ) return INT_MAX; if( n < 0 ) return -INT_MAX; return 0; }
63 }
64
65 } // end namespace
66
67
normalize(long long n,long long d)68 void Rational::normalize( long long n, long long d )
69 {
70 if( d == 0 ) { num = overflow_value( n ); den = 0; return; } // set error
71 if( n == 0 ) { num = 0; den = 1; return; }
72 if( d != 1 )
73 {
74 const long long tmp = gcd( n, d );
75 n /= tmp; d /= tmp;
76 }
77
78 if( n <= INT_MAX && n >= -INT_MAX && d <= INT_MAX && d >= -INT_MAX )
79 { if( d >= 0 ) { num = n; den = d; } else { num = -n; den = -d; } }
80 else
81 { num = overflow_value( n, d < 0 ); den = 0; }
82 }
83
84
normalize()85 void Rational::normalize()
86 {
87 if( den == 0 ) { num = overflow_value( num ); return; }
88 if( num == 0 ) { den = 1; return; }
89 if( den != 1 )
90 {
91 const int tmp = gcd( num, den );
92 num /= tmp; den /= tmp;
93 }
94 if( num < -INT_MAX )
95 { num = overflow_value( den, true ); den = 0; return; }
96 if( den < 0 )
97 {
98 if( den < -INT_MAX )
99 { num = overflow_value( num, true ); den = 0; return; }
100 num = -num; den = -den;
101 }
102 }
103
104
inverse() const105 Rational Rational::inverse() const
106 {
107 if( den <= 0 ) return *this; // no op on error
108 Rational tmp;
109 if( num > 0 ) { tmp.num = den; tmp.den = num; }
110 else if( num < 0 ) { tmp.num = -den; tmp.den = -num; }
111 else { tmp.num = overflow_value( den ); tmp.den = 0; } // set error
112 return tmp;
113 }
114
115
operator +=(const Rational & r)116 Rational & Rational::operator+=( const Rational & r )
117 {
118 if( den <= 0 ) return *this; // no op on error
119 if( r.den <= 0 ) { num = r.num; den = 0; return *this; } // set error
120
121 long long new_den = den; new_den *= r.den;
122 long long new_num1 = num; new_num1 *= r.den;
123 long long new_num2 = r.num; new_num2 *= den;
124 normalize( new_num1 + new_num2, new_den );
125 return *this;
126 }
127
128
operator *=(const Rational & r)129 Rational & Rational::operator*=( const Rational & r )
130 {
131 if( den <= 0 ) return *this; // no op on error
132 if( r.den <= 0 ) { num = r.num; den = 0; return *this; } // set error
133
134 long long new_num = num; new_num *= r.num;
135 long long new_den = den; new_den *= r.den;
136 normalize( new_num, new_den );
137 return *this;
138 }
139
140
round() const141 int Rational::round() const
142 {
143 if( den <= 0 ) return num;
144 int result = num / den;
145 const int rest = std::abs( num ) % den;
146 if( rest > 0 && rest >= den - rest )
147 { if( num >= 0 ) ++result; else --result; }
148 return result;
149 }
150
151
152 // Recognized formats: 123 123/456 123.456 .123 12% 12/3% 12.3% .12%
153 // Values may be preceded by an optional '+' or '-' sign.
154 // Returns the number of chars read from 's', or 0 if input is invalid.
155 // In case of invalid input, the Rational is not changed.
156 //
parse(const char * const s)157 int Rational::parse( const char * const s )
158 {
159 if( !s || !s[0] ) return 0;
160 long long n = 0, d = 1; // restrain intermediate overflow
161 int c = 0;
162 bool minus = false;
163
164 while( std::isspace( s[c] ) ) ++c;
165 if( s[c] == '+' ) ++c;
166 else if( s[c] == '-' ) { ++c; minus = true; }
167 if( !std::isdigit( s[c] ) && s[c] != '.' ) return 0;
168
169 while( std::isdigit( s[c] ) )
170 {
171 if( ( LLONG_MAX - (s[c] - '0') ) / 10 < n ) return 0;
172 n = (n * 10) + (s[c] - '0'); ++c;
173 }
174
175 if( s[c] == '.' )
176 {
177 ++c; if( !std::isdigit( s[c] ) ) return 0;
178 while( std::isdigit( s[c] ) )
179 {
180 if( ( LLONG_MAX - (s[c] - '0') ) / 10 < n || LLONG_MAX / 10 < d )
181 return 0;
182 n = (n * 10) + (s[c] - '0'); d *= 10; ++c;
183 }
184 }
185 else if( s[c] == '/' )
186 {
187 ++c; d = 0;
188 while( std::isdigit( s[c] ) )
189 {
190 if( ( LLONG_MAX - (s[c] - '0') ) / 10 < d ) return 0;
191 d = (d * 10) + (s[c] - '0'); ++c;
192 }
193 if( d == 0 ) return 0;
194 }
195
196 if( s[c] == '%' )
197 {
198 ++c;
199 if( n % 100 == 0 ) n /= 100;
200 else if( n % 10 == 0 && LLONG_MAX / 10 >= d ) { n /= 10; d *= 10; }
201 else if( LLONG_MAX / 100 >= d ) d *= 100;
202 else return 0;
203 }
204
205 if( minus ) n = -n;
206 Rational tmp; tmp.normalize( n, d );
207 if( !tmp.error() ) { *this = tmp; return c; }
208 return 0;
209 }
210
211
212 // Returns a string representing the value 'num/den' in decimal point
213 // format with 'prec' decimals.
214 // 'iwidth' is the minimum width of the integer part, prefixed with
215 // spaces if needed.
216 // If 'prec' is negative, only the decimals needed are produced.
217 //
to_decimal(const unsigned iwidth,int prec) const218 std::string Rational::to_decimal( const unsigned iwidth, int prec ) const
219 {
220 if( den <= 0 ) return overflow_string( num );
221
222 std::string s;
223 int ipart = std::abs( num / den );
224 const bool truncate = ( prec < 0 );
225 if( prec < 0 ) prec = -prec;
226
227 do { s += '0' + ( ipart % 10 ); ipart /= 10; } while( ipart > 0 );
228 if( num < 0 ) s += '-';
229 if( iwidth > s.size() ) s.append( iwidth - s.size(), ' ' );
230 std::reverse( s.begin(), s.end() );
231 long long rest = std::abs( num ) % den;
232 if( prec > 0 && ( rest > 0 || !truncate ) )
233 {
234 s += '.';
235 while( prec > 0 && ( rest > 0 || !truncate ) )
236 { rest *= 10; s += '0' + ( rest / den ); rest %= den; --prec; }
237 }
238 return s;
239 }
240
241
242 // Returns a string representing the value 'num/den' in fractional form.
243 // 'width' is the minimum width to be produced, prefixed with spaces if
244 // needed.
245 //
to_fraction(const unsigned width) const246 std::string Rational::to_fraction( const unsigned width ) const
247 {
248 if( den <= 0 ) return overflow_string( num );
249
250 std::string s;
251 int n = std::abs( num ), d = den;
252
253 do { s += '0' + ( d % 10 ); d /= 10; } while( d > 0 );
254 s += '/';
255 do { s += '0' + ( n % 10 ); n /= 10; } while( n > 0 );
256 if( num < 0 ) s += '-';
257 if( width > s.size() ) s.append( width - s.size(), ' ' );
258 std::reverse( s.begin(), s.end() );
259 return s;
260 }
261