File indexing completed on 2024-05-12 05:55:18
0001 // This file is part of the SpeedCrunch project 0002 // Copyright (C) 2015 Pol Welter <polwelter@gmail.com> 0003 // 0004 // This program is free software; you can redistribute it and/or 0005 // modify it under the terms of the GNU General Public License 0006 // as published by the Free Software Foundation; either version 2 0007 // of the License, or (at your option) any later version. 0008 // 0009 // This program is distributed in the hope that it will be useful, 0010 // but WITHOUT ANY WARRANTY; without even the implied warranty of 0011 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 0012 // GNU General Public License for more details. 0013 // 0014 // You should have received a copy of the GNU General Public License 0015 // along with this program; see the file COPYING. If not, write to 0016 // the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 0017 // Boston, MA 02110-1301, USA. 0018 0019 #include "rational.h" 0020 #include "hmath.h" 0021 #include "numberformatter.h" 0022 0023 #include <cmath> 0024 #include <QString> 0025 #include <QStringList> 0026 #include <limits.h> 0027 0028 0029 void Rational::normalize() 0030 { 0031 if(m_denom==0) { 0032 m_valid = false; 0033 return; 0034 } 0035 if(m_num==0) { 0036 m_denom=1; 0037 return; 0038 } 0039 int g = gcd(abs(m_num), abs(m_denom)); 0040 m_num /= g; 0041 m_denom /= g; 0042 if(m_denom<0) { 0043 m_num = -m_num; 0044 m_denom = -m_denom; 0045 } 0046 } 0047 0048 int Rational::compare(const Rational &other) const 0049 { 0050 return m_num*other.m_denom - m_denom*other.m_num; 0051 } 0052 0053 0054 /* 0055 * Find a rational approximation to num using a continued fraction scheme. 0056 * Code adapted from the 'Fraction' module for the PYTHON programming language, 0057 * authored by Sjoerd Mullender and Jeffrey Yasskin. 0058 */ 0059 Rational::Rational(const HNumber &num) : 0060 m_num(1), m_denom(1), m_valid(1) 0061 { 0062 if(num.isZero()) { 0063 m_num = 0; 0064 return; 0065 } 0066 if(HMath::abs(num)>HNumber(INT_MAX) || HMath::abs(num)<HNumber(1)/HNumber(INT_MAX)) { 0067 m_valid = false; 0068 return; 0069 } 0070 if(num.isInteger()) { 0071 m_num = num.toInt(); 0072 return; 0073 } 0074 const unsigned long long MAXD = INT_MAX/2; // maximal denominator 0075 unsigned long long p0=0, q0=1, p1=1, q1=0; 0076 HNumber val(HMath::abs(num)); 0077 while(true) { 0078 long a = HMath::floor(val).toInt(); 0079 unsigned long long q2 = q0 + a*q1; 0080 if(q2>MAXD) 0081 break; 0082 unsigned long long temp1=p0, temp2=p1, temp3=q1; 0083 p0 = temp2; 0084 q0 = temp3; 0085 p1 = temp1 + a*temp2; 0086 q1 = q2; 0087 if(HMath::frac(val).isZero()) break; 0088 val = HNumber(1)/HMath::frac(val); 0089 if(val>HNumber(MAXD)) break; 0090 } 0091 0092 Rational bound(p1, q1); 0093 if(num<0) { 0094 bound.m_num *= -1; 0095 } 0096 *this = bound; 0097 0098 } 0099 0100 Rational::Rational(const double &num): 0101 m_num(1), m_denom(1), m_valid(1) 0102 { 0103 if (num==0) { 0104 m_num = 0; 0105 return; 0106 } 0107 if (std::abs(num)>INT_MAX || std::abs(1./num)>INT_MAX) { 0108 m_valid = false; 0109 return; 0110 } 0111 const long long MAXD = INT_MAX/2; // maximal denominator 0112 long long p0=0, q0=1, p1=1, q1=0; 0113 0114 double val = fabs(num); 0115 while(true) { 0116 unsigned long long a = static_cast<unsigned long long>(floor(val)); 0117 unsigned long long q2 = q0 + a*q1; 0118 if(q2>MAXD) 0119 break; 0120 unsigned long long temp1=p0, temp2=p1, temp3=q1; 0121 p0 = temp2; 0122 q0 = temp3; 0123 p1 = temp1 + a*temp2; 0124 q1 = q2; 0125 if(val==a) break; 0126 val = 1/(val-a); 0127 } 0128 0129 Rational bound(p1, q1); 0130 if(num<0) 0131 bound.m_num *= -1; 0132 0133 *this = bound; 0134 } 0135 0136 Rational::Rational(const QString &str) : m_num(0), m_denom(1), m_valid(true) 0137 { 0138 if(str=="") { 0139 m_valid=false; 0140 return; 0141 } 0142 QStringList l = str.split("/"); 0143 if(l.size()==1) { 0144 bool ok; 0145 m_num = l.at(0).toInt(&ok); 0146 if(!ok) { 0147 m_valid=false; 0148 return; 0149 } 0150 } else if(l.size()==2) { 0151 bool ok; 0152 m_num = l.at(0).toInt(&ok); 0153 if(!ok) { 0154 m_valid=false; 0155 return; 0156 } 0157 m_denom = l.at(1).toInt(&ok); 0158 if(!ok) { 0159 m_valid=false; 0160 return; 0161 } 0162 } 0163 } 0164 0165 Rational Rational::operator*(const Rational &other) const 0166 { 0167 return Rational(this->m_num * other.m_num, this->m_denom * other.m_denom); 0168 } 0169 0170 Rational Rational::operator/(const Rational &other) const 0171 { 0172 if(other.isZero()) return Rational(1,0); // Rational(1,0) will set m_valid=false 0173 return Rational(this->m_num / other.m_num, this->m_denom / other.m_denom); 0174 } 0175 0176 Rational Rational::operator+(const Rational &other) const 0177 { 0178 return Rational(this->m_num*other.m_denom + this->m_denom*other.m_num, this->m_denom*other.m_denom); 0179 } 0180 0181 Rational Rational::operator-(const Rational &other) const 0182 { 0183 return Rational(this->m_num*other.m_denom - this->m_denom*other.m_num, this->m_denom*other.m_denom); 0184 } 0185 0186 Rational &Rational::operator=(const Rational &other) 0187 { 0188 m_num = other.m_num; 0189 m_denom = other.m_denom; 0190 m_valid = other.m_valid; 0191 return *this; 0192 } 0193 0194 Rational &Rational::operator+=(const Rational &other) 0195 { 0196 return operator=(*this + other); 0197 } 0198 0199 Rational &Rational::operator-=(const Rational &other) 0200 { 0201 return operator=(*this - other); 0202 } 0203 0204 Rational &Rational::operator*=(const Rational &other) 0205 { 0206 return operator=(*this * other); 0207 } 0208 0209 Rational &Rational::operator/=(const Rational &other) 0210 { 0211 return operator=(*this / other); 0212 } 0213 0214 bool Rational::operator<(const Rational &other) const 0215 { 0216 return compare(other)<0; 0217 } 0218 0219 bool Rational::operator==(const Rational &other) const 0220 { 0221 return compare(other) == 0; 0222 } 0223 0224 bool Rational::operator>(const Rational &other) const 0225 { 0226 return compare(other)>0; 0227 } 0228 0229 bool Rational::isZero() const 0230 { 0231 return m_num==0; 0232 } 0233 0234 bool Rational::isValid() const 0235 { 0236 return m_valid; 0237 } 0238 0239 QString Rational::toString() const 0240 { 0241 if(m_denom==1) 0242 return QString::fromLatin1("%1").arg(m_num); 0243 return QString::fromLatin1("%1/%2").arg(m_num).arg(m_denom); 0244 } 0245 0246 HNumber Rational::toHNumber() const 0247 { 0248 HNumber num(m_num); 0249 HNumber denom(m_denom); 0250 return num/denom; 0251 0252 } 0253 0254 double Rational::toDouble() const 0255 { 0256 return double(m_num)/m_denom; 0257 }