はじめに
一年ぶりにプログラミングを改めて勉強し始めました。
前まではCを使っていたのでC++の勉強を今しています。これはその過程で作った演算子のオーバーロードの演習(C++実践プログラミング18.6節の実習18-1)です。
実装
使い方の説明
コンストラクタを使って分数を入力します。
Fraction<int> a(9, 5); // 9/5で分数を定義
Fraction<int> b; // 0で分数を定義
int型との演算は明示的な型変換が必要です。
auto c = a + b;
auto d = c + Fraction<int>(2);
std::cout << を使って出力できるようにします(1/2 のようなフォーマット)
std::cout << a << std::endl;
- 分数に対して約分を行う関数
reduction() - 分数の逆数を返す関数
reciprocal() const - 分数が過去にオーバーフローを起こしたかを返す関数
get_status() const - 分数を要素(分子と分母)に分解して返す関数
get_fraction() const
があります。約分は分数同士の演算時に毎回呼び出されます。
a.reduction();
auto e = a.reciprocal();
auto s = a.stat();
float及びdouble型にキャストできます。
float f = (float)(a);
double g = (double)(a);
.hppファイル
テンプレートを使用しているのでヘッダーオンリーです。
template_checked.hpp
/includes/template_checked.hpp
#ifndef template_checked_hpp
#define template_checked_hpp
#include <iostream>
#include <limits>
#include <compare>
// Constatnt
namespace {
template <typename T> constexpr T min = std::numeric_limits<T>::min();
template <typename T> constexpr T max = std::numeric_limits<T>::max();
}
// Flagged definition
namespace checked {
enum class HadOverflowed : bool {
Yes = true, No = false
};
template <typename T> struct Flagged {
T value;
HadOverflowed status;
constexpr Flagged() noexcept : value(0), status(HadOverflowed::No) {}
constexpr Flagged(const T& v) noexcept : value(v), status(HadOverflowed::No) {}
constexpr Flagged(const T& v, const HadOverflowed& s) noexcept : value(v), status(s) {}
constexpr Flagged(const Flagged& f) noexcept : value(f.value), status(f.status) {}
constexpr Flagged operator=(const Flagged& f) noexcept { this->value = f.value, this->status = f.status; return (*this); }
};
}
namespace checked {
// Preparation for operators
constexpr HadOverflowed operator||(const HadOverflowed& lhs, const HadOverflowed& rhs) noexcept;
template <typename T> struct OperandData { T lhs; T rhs; HadOverflowed status; };
enum class Sign { SamePositive, SameNegative, Different };
template <typename T> constexpr Sign get_operand_sign(const T& lhs, const T& rhs) noexcept;
// Checked class
template <typename T> class Checked {
private:
Flagged<T> integer;
constexpr OperandData<T> get_operand_data(const Checked<T>& c) {
return { .lhs = this->integer.value, .rhs = c.get_value(), .status = (this->integer.status || c.get_status()) };
}
public:
constexpr Checked() noexcept : integer(0) {}
constexpr Checked(const T& v) noexcept : integer(v) {}
constexpr Checked(const T& v, const HadOverflowed& s) noexcept : integer(v, s) {}
constexpr Checked(const Checked& c) noexcept : integer(c.integer) {};
constexpr T get_value() const noexcept { return this->integer.value; }
constexpr HadOverflowed get_status() const noexcept { return this->integer.status; }
constexpr Flagged<T> get_flagged() const noexcept { return this->integer; }
constexpr Checked operator= (const Checked& c) noexcept { this->integer = c.integer; return (*this); }
constexpr Checked operator+=(const Checked& c) noexcept {
const auto [lhs, rhs, status] = get_operand_data(c);
switch (get_operand_sign(lhs, rhs)) {
case Sign::SamePositive:
if (max<T> - lhs >= rhs) { (*this) = Checked(lhs + rhs, status); return (*this); }
else { (*this) = Checked(max<T>, HadOverflowed::Yes); return (*this); }
case Sign::SameNegative:
if (min<T> - lhs <= rhs) { (*this) = Checked(lhs + rhs, status); return (*this); }
else { (*this) = Checked(min<T>, HadOverflowed::Yes); return (*this); }
case Sign::Different:
default:
(*this) = Checked(lhs + rhs, status); return (*this);
}
}
constexpr Checked operator-=(const Checked& c) noexcept {
const auto [lhs, rhs, status] = get_operand_data(c);
if (rhs == min<T> && lhs < 0) { (*this) = Checked(lhs - rhs, status); return (*this); }
else if (rhs == min<T> && lhs >= 0) { (*this) = Checked(max<T>, HadOverflowed::Yes); return (*this); }
else { (*this) += Checked(-rhs, status); return (*this); }
}
constexpr Checked operator*=(const Checked& c) noexcept {
const auto [lhs, rhs, status] = get_operand_data(c);
if (lhs == 0 || lhs == 1 || rhs == 0 || rhs == 1) { (*this) = Checked(lhs * rhs, status); return(*this); }
else if (lhs == min<T> || rhs == min<T>) {
(*this) = get_operand_sign(lhs, rhs) == Sign::Different ? Checked(max<T>, HadOverflowed::Yes) : Checked(min<T>, HadOverflowed::Yes);
return (*this);
}
switch (get_operand_sign(lhs, rhs)) {
case Sign::SamePositive:
case Sign::SameNegative:
if (std::abs(max<T> / lhs) >= std::abs(rhs)) { (*this) = Checked(lhs * rhs, status); return (*this); }
else { (*this) = Checked(max<T>, HadOverflowed::Yes); return (*this); }
case Sign::Different:
default:
if (lhs == -1) { (*this) = Checked(lhs * rhs, status); return (*this); }
else if (std::abs(min<T> / lhs) >= std::abs(rhs)) { (*this) = Checked(lhs * rhs, status); return (*this); }
else { (*this) = Checked(min<T>, HadOverflowed::Yes); return (*this); }
}
}
constexpr Checked operator/=(const Checked& c) noexcept {
const auto [lhs, rhs, status] = get_operand_data(c);
if (lhs == min<T> && rhs == -1) { (*this) = Checked(min<T>, HadOverflowed::Yes); return (*this); }
else if (rhs == 0) { (*this) = Checked(0, HadOverflowed::Yes); return (*this); }
else { (*this) = Checked(lhs / rhs, status); return (*this); }
}
constexpr Checked operator%=(const Checked& c) noexcept {
const auto [lhs, rhs, status] = get_operand_data(c);
if (rhs == 1 || rhs == -1) { (*this) = Checked(0, status); return (*this); }
else if (rhs == 0) { (*this) = Checked(0, HadOverflowed::Yes); return (*this); }
else { (*this) = Checked(lhs % rhs, status); return (*this); }
}
constexpr Checked operator++(int) noexcept { (*this) += 1; return (*this); }
constexpr Checked operator--(int) noexcept { (*this) -= 1; return (*this); }
constexpr Checked operator++() noexcept { (*this) += 1; return (*this); }
constexpr Checked operator--() noexcept { (*this) -= 1; return (*this); }
private:
friend std::istream& operator>><>(std::istream&, Checked<T>&) noexcept;
};
}
// Binary operators
namespace checked {
template <typename T> constexpr Checked<T> operator+(const Checked<T>& c) noexcept { return c; }
template <typename T> constexpr Checked<T> operator-(const Checked<T>& c) noexcept { return Checked(-c.get_value(), c.get_status()); }
template <typename T> constexpr Checked<T> operator+(const Checked<T>& lhs, const Checked<T>& rhs) noexcept { Checked tmp = lhs; return tmp += rhs; }
template <typename T> constexpr Checked<T> operator-(const Checked<T>& lhs, const Checked<T>& rhs) noexcept { Checked tmp = lhs; return tmp -= rhs; }
template <typename T> constexpr Checked<T> operator*(const Checked<T>& lhs, const Checked<T>& rhs) noexcept { Checked tmp = lhs; return tmp *= rhs; }
template <typename T> constexpr Checked<T> operator/(const Checked<T>& lhs, const Checked<T>& rhs) noexcept { Checked tmp = lhs; return tmp /= rhs; }
template <typename T> constexpr Checked<T> operator%(const Checked<T>& lhs, const Checked<T>& rhs) noexcept { Checked tmp = lhs; return tmp %= rhs; }
}
// Comparison operators
namespace checked {
template <typename T> constexpr bool operator==(const Checked<T>& lhs, const Checked<T>& rhs) noexcept { return (lhs.get_value() == rhs.get_value()); }
template <typename T> constexpr std::strong_ordering operator<=>(const Checked<T>& lhs, const Checked<T>& rhs) noexcept {
if (lhs == rhs) return std::strong_ordering::equal;
else return (lhs.get_value() <=> rhs.get_value());
}
}
// IO operators
namespace checked {
template <typename T> std::ostream& operator<<(std::ostream& out, const Checked<T>& c) noexcept { out << c.get_value(); return out; }
template <typename T> std::istream& operator>>(std::istream& cin, Checked<T>& c) noexcept { cin >> c.integer.value; return cin; }
}
// impl: Preparation for operators
namespace checked {
constexpr HadOverflowed operator||(const HadOverflowed& lhs, const HadOverflowed& rhs) noexcept {
return (static_cast<bool>(lhs) || static_cast<bool>(rhs)) ? HadOverflowed::Yes : HadOverflowed::No;
}
template <typename T> constexpr Sign get_operand_sign(const T& lhs, const T& rhs) noexcept {
if (lhs >= 0 && rhs >= 0) return Sign::SamePositive;
else if (lhs < 0 && rhs < 0) return Sign::SameNegative;
else return Sign::Different;
}
}
#endif // template_checked_hpp
template_fraction.hpp
/includes/template_fraction.hpp
#ifndef template_fraction_hpp
#define template_fraction_hpp
#include "template_checked.hpp"
#include <iostream>
#include <compare>
#include <numeric>
#include <iomanip>
namespace checked::fraction {
template <typename T> struct CheckedFraction {
Checked<T> nume;
Checked<T> deno;
constexpr CheckedFraction() noexcept : nume(0), deno(1){}
constexpr CheckedFraction(const Checked<T>& n) noexcept : nume(n), deno(1){}
constexpr CheckedFraction(const Checked<T>& n, const Checked<T>& d) noexcept : nume(n), deno(d){}
constexpr CheckedFraction(const CheckedFraction& cf) noexcept : nume(cf.nume), deno(cf.deno){}
constexpr CheckedFraction operator=(const CheckedFraction& cf) noexcept { this->nume = cf.nume; this->deno = cf.deno; return (*this); }
};
}
namespace checked::fraction {
constexpr std::streamsize fw = 20;
constexpr std::streamsize nw = fw * 2 + 1;
template <typename T> class Fraction {
private:
CheckedFraction<T> frac;
public:
constexpr Fraction() noexcept : frac(0){}
constexpr Fraction(const Checked<T>& n) noexcept : frac(n){}
constexpr Fraction(const Checked<T>& n, const Checked<T>& d) noexcept : frac(n, d){}
constexpr Fraction(const Fraction& f) noexcept : frac(f.frac){}
constexpr Fraction reduction() noexcept {
auto& nume = this->frac.nume;
auto& deno = this->frac.deno;
if(nume == Checked<T>(0)) { (*this) = Fraction(0); return (*this); }
const auto divisor = Checked<T>(std::gcd(nume.get_value(), deno.get_value()));
nume /= divisor;
deno /= divisor;
if(deno < Checked<T>(0)) {
nume *= Checked<T>(-1);
deno *= Checked<T>(-1);
}
return (*this);
}
constexpr Fraction reciprocal() const noexcept { return Fraction(this->frac.deno, this->frac.nume); }
constexpr CheckedFraction<T> get_fraction() const noexcept { return this->frac; }
constexpr HadOverflowed get_status() const noexcept {
if(static_cast<bool>(this->frac.nume.get_status()) || static_cast<bool>(this->frac.deno.get_status()))
return HadOverflowed::Yes;
else
return HadOverflowed::No;
}
constexpr Fraction operator= (const Fraction& f) noexcept { this->frac = f.frac; return (*this); }
constexpr Fraction operator+=(const Fraction& f) noexcept {
const auto [rnume, rdeno] = f.get_fraction();
this->frac.nume = (this->frac.nume * rdeno) + (rnume * this->frac.deno);
this->frac.deno *= rdeno;
return reduction();
}
constexpr Fraction operator-=(const Fraction& f) noexcept {
const auto [rnume, rdeno] = f.get_fraction();
this->frac.nume = (this->frac.nume * rdeno) - (rnume * this->frac.deno);
this->frac.deno *= rdeno;
return reduction();
}
constexpr Fraction operator*=(const Fraction& f) noexcept {
const auto [rnume, rdeno] = f.get_fraction();
this->frac.nume *= rnume;
this->frac.deno *= rdeno;
return reduction();
}
constexpr Fraction operator/=(const Fraction& f) noexcept {
return (*this) *= f.reciprocal();
}
constexpr Fraction operator++(int) noexcept { this->frac.nume += this->frac.deno; return (*this); }
constexpr Fraction operator--(int) noexcept { this->frac.nume -= this->frac.deno; return (*this); }
constexpr Fraction operator++() noexcept { this->frac.nume += this->frac.deno; return (*this); }
constexpr Fraction operator--() noexcept { this->frac.nume -= this->frac.deno; return (*this); }
constexpr explicit operator double() const noexcept {
return static_cast<double>(this->frac.nume.get_value()) / static_cast<double>(this->frac.deno.get_value());
}
constexpr explicit operator float() const noexcept {
return static_cast<float>(this->frac.nume.get_value()) / static_cast<float>(this->frac.deno.get_value());
}
};
}
namespace checked::fraction {
template <typename T> constexpr Fraction<T> operator+(const Fraction<T>& f) noexcept { return f; }
template <typename T> constexpr Fraction<T> operator-(const Fraction<T>& f) noexcept { const auto [nume, deno] = f.get_fraction(); return Fraction(-nume, deno); }
template <typename T> constexpr Fraction<T> operator+(const Fraction<T>& lhs, const Fraction<T>& rhs) noexcept { Fraction tmp = lhs; return tmp += rhs; }
template <typename T> constexpr Fraction<T> operator-(const Fraction<T>& lhs, const Fraction<T>& rhs) noexcept { Fraction tmp = lhs; return tmp -= rhs; }
template <typename T> constexpr Fraction<T> operator*(const Fraction<T>& lhs, const Fraction<T>& rhs) noexcept { Fraction tmp = lhs; return tmp *= rhs; }
template <typename T> constexpr Fraction<T> operator/(const Fraction<T>& lhs, const Fraction<T>& rhs) noexcept { Fraction tmp = lhs; return tmp /= rhs; }
}
namespace checked::fraction {
template <typename T> constexpr bool operator==(const Fraction<T>& lhs, const Fraction<T>& rhs) noexcept {
const auto [lnume, ldeno] = lhs.get_fraction();
const auto [rnume, rdeno] = rhs.get_fraction();
return ((lnume == rnume) && (ldeno == rdeno));
}
template <typename T> constexpr std::strong_ordering operator<=>(const Fraction<T>& lhs_, const Fraction<T>& rhs_) noexcept {
if(lhs_ == rhs_) return std::strong_ordering::equal;
auto lhs = lhs_, rhs = rhs_;
const auto num = [](const Fraction<T>& f) -> Checked<T> {
const auto [nume, deno] = f.get_fraction();
if(const auto n = nume / deno; n < Checked<T>(0)) return n - Checked<T>(1);
else return n;
};
for(int i = 0; ; ++i) {
if(const auto lnum = num(lhs), rnum = num(rhs); lnum == rnum) {
lhs = (lhs - Fraction<T>(lnum)).reciprocal();
rhs = (rhs - Fraction<T>(rnum)).reciprocal();
}
else if(i % 2 == 0) return (lnum <=> rnum);
else return (rnum <=> lnum);
}
}
template <typename T> constexpr std::ostream& operator<<(std::ostream& out, const Fraction<T>& f) noexcept {
const auto [nume, deno] = f.get_fraction();
if(deno == Checked<T>(1) || nume == Checked<T>(0)) out << std::setw(nw) << nume;
else out << std::setw(fw) << nume << "/" << std::setw(fw) << deno;
return out;
}
}
#endif // template_fraction_hpp
簡単な説明
-
Checkedは演算中にオーバーフローが発生したか否かの情報を整数型に加えたクラスです。 -
Flagged及びCheckedFractionは構造化束縛で要素を受け取るために定義されています。 -
HadOverflowedはbool型にキャストすることができます。 - 四則演算、代入演算、比較演算、インクリメントデクリメント、出力が定義されています。
Checkedはこれに加え、入力と剰余演算子が定義されています。 -
Fractionの比較には連分数展開を用いています。 -
std::gcdの結果はChecked型になるので0が返っても例外は発生しません。
動作テスト
動作テストは次の四つです。
- 簡単な四則演算、比較演算の正誤チェック(
simple) - 四則演算のチェック(
normal_calc) - 比較演算のチェック(
comparison) - 演算速度の比較(
speed)
simple
各演算を一度ずつ行い、その結果を出力します。手計算で結果が正しいかを判定するとても簡便なテストです。
normal_calc
被演算子と演算子を乱数によって生成し、double型とFraction型で演算後、その値をdoubleにキャストして比較します。浮動小数点型は精度が常に$100\%$というわけではないので、その相対誤差を取り、誤差の平均が$10^{-15.955}$より小さければOK、$10^{-15}$より小さければPosiibly OKであるとします。オーバーフローが発生している場合、何らかの原因で誤差がinfとなった場合は誤差は取らずにスキップします。
comparison
normal_calcと同様に乱数によって被演算子と演算子を生成し、double型とFraction型で比較後、その結果を照合します。結果が等しくない場合はそのケースを出力するので、手動でどちらが正しいかを判断します。結果が一致するケースがテストケースの数と等しい場合はOK、テストケースの$99.99\%$以上が等しい場合はPossibly OKとなります。
speed
同様に乱数によって被演算子と演算子を生成し、double、Fraction、IntFractionの三つの型の演算速度を比較します。各テストケースの初めにシード値を決め、それぞれ決められたシード値で乱数生成機を作り、演算を行います。従って、各テストケースで行われる演算は三つの型で完全に一致します。IntFractionとはFraction内のデータの型をCheckedからstd::int64_tへ変えたものです。
名前空間はinteger::fractionとしています。
int_fraction.hpp
/includes/int_fraction.hpp
#ifndef int_fraction_hpp
#define int_fraction_hpp
#include <iostream>
#include <compare>
#include <numeric>
#include <iomanip>
namespace integer::fraction {
template <typename T> struct IntFraction {
T nume;
T deno;
constexpr IntFraction() noexcept : nume(0), deno(1){}
constexpr IntFraction(const T& n) noexcept : nume(n), deno(1){}
constexpr IntFraction(const T& n, const T& d) noexcept : nume(n), deno(d){}
constexpr IntFraction(const IntFraction& cf) noexcept : nume(cf.nume), deno(cf.deno){}
constexpr IntFraction operator=(const IntFraction& cf) noexcept { this->nume = cf.nume; this->deno = cf.deno; return (*this); }
};
}
namespace integer::fraction {
constexpr std::streamsize fw = 20;
constexpr std::streamsize nw = fw * 2 + 1;
template <typename T> class Fraction {
private:
IntFraction<T> frac;
public:
constexpr Fraction() noexcept : frac(0){}
constexpr Fraction(const T& n) noexcept : frac(n){}
constexpr Fraction(const T& n, const T& d) noexcept : frac(n, d){}
constexpr Fraction(const Fraction& f) noexcept : frac(f.frac){}
constexpr Fraction reduction() noexcept {
auto& nume = this->frac.nume;
auto& deno = this->frac.deno;
if(nume == 0) { (*this) = Fraction(0); return (*this); }
const auto divisor = std::gcd(nume, deno);
nume /= divisor;
deno /= divisor;
if(deno < 0) {
nume *= -1;
deno *= -1;
}
return (*this);
}
constexpr Fraction reciprocal() const noexcept { return Fraction(this->frac.deno, this->frac.nume); }
constexpr IntFraction<T> get_fraction() const noexcept { return this->frac; }
constexpr Fraction operator= (const Fraction& f) noexcept { this->frac = f.frac; return (*this); }
constexpr Fraction operator+=(const Fraction& f) noexcept {
const auto [rnume, rdeno] = f.get_fraction();
this->frac.nume = (this->frac.nume * rdeno) + (rnume * this->frac.deno);
this->frac.deno *= rdeno;
return reduction();
}
constexpr Fraction operator-=(const Fraction& f) noexcept {
const auto [rnume, rdeno] = f.get_fraction();
this->frac.nume = (this->frac.nume * rdeno) - (rnume * this->frac.deno);
this->frac.deno *= rdeno;
return reduction();
}
constexpr Fraction operator*=(const Fraction& f) noexcept {
const auto [rnume, rdeno] = f.get_fraction();
this->frac.nume *= rnume;
this->frac.deno *= rdeno;
return reduction();
}
constexpr Fraction operator/=(const Fraction& f) noexcept {
return (*this) *= f.reciprocal();
}
constexpr Fraction operator++(int) noexcept { this->frac.nume += this->frac.deno; return (*this); }
constexpr Fraction operator--(int) noexcept { this->frac.nume -= this->frac.deno; return (*this); }
constexpr Fraction operator++() noexcept { this->frac.nume += this->frac.deno; return (*this); }
constexpr Fraction operator--() noexcept { this->frac.nume -= this->frac.deno; return (*this); }
constexpr explicit operator double() const noexcept {
return static_cast<double>(this->frac.nume) / static_cast<double>(this->frac.deno);
}
constexpr explicit operator float() const noexcept {
return static_cast<float>(this->frac.nume) / static_cast<float>(this->frac.deno);
}
};
}
namespace integer::fraction {
template <typename T> constexpr Fraction<T> operator+(const Fraction<T>& f) noexcept { return f; }
template <typename T> constexpr Fraction<T> operator-(const Fraction<T>& f) noexcept { const auto [nume, deno] = f.get_fraction(); return Fraction(-nume, deno); }
template <typename T> constexpr Fraction<T> operator+(const Fraction<T>& lhs, const Fraction<T>& rhs) noexcept { Fraction tmp = lhs; return tmp += rhs; }
template <typename T> constexpr Fraction<T> operator-(const Fraction<T>& lhs, const Fraction<T>& rhs) noexcept { Fraction tmp = lhs; return tmp -= rhs; }
template <typename T> constexpr Fraction<T> operator*(const Fraction<T>& lhs, const Fraction<T>& rhs) noexcept { Fraction tmp = lhs; return tmp *= rhs; }
template <typename T> constexpr Fraction<T> operator/(const Fraction<T>& lhs, const Fraction<T>& rhs) noexcept { Fraction tmp = lhs; return tmp /= rhs; }
}
namespace integer::fraction {
template <typename T> constexpr bool operator==(const Fraction<T>& lhs, const Fraction<T>& rhs) noexcept {
const auto [lnume, ldeno] = lhs.get_fraction();
const auto [rnume, rdeno] = rhs.get_fraction();
return ((lnume == rnume) && (ldeno == rdeno));
}
template <typename T> constexpr std::strong_ordering operator<=>(const Fraction<T>& lhs_, const Fraction<T>& rhs_) noexcept {
if(lhs_ == rhs_) return std::strong_ordering::equal;
auto lhs = lhs_, rhs = rhs_;
const auto num = [](const Fraction<T>& f) -> T {
const auto [nume, deno] = f.get_fraction();
if(const auto n = nume / deno; n < 0) return n - 1;
else return n;
};
for(int i = 0; ; ++i) {
if(const auto lnum = num(lhs), rnum = num(rhs); lnum == rnum) {
lhs = (lhs - Fraction<T>(lnum)).reciprocal();
rhs = (rhs - Fraction<T>(rnum)).reciprocal();
}
else if(i % 2 == 0) return (lnum <=> rnum);
else return (rnum <=> lnum);
}
}
template <typename T> constexpr std::ostream& operator<<(std::ostream& out, const Fraction<T>& f) noexcept {
const auto [nume, deno] = f.get_fraction();
if(deno == 1 || nume == 0) out << std::setw(nw) << nume;
else out << std::setw(fw) << nume << "/" << std::setw(fw) << deno;
return out;
}
}
#endif // int_fraction_hpp
実際のテスト
テストを行うためのファイルと実行結果の例です。結構ごちゃごちゃしているので結果だけ見てもらえれば十分なのですが、とりあえず載せておきます。
test_frac.hpp
/includes/test_frac.hpp
#ifndef frac_test_hpp
#define frac_test_hpp
namespace simple { void test(); }
namespace normal_calc { void test(); }
namespace comparison{ void test(); }
namespace speed{ void test(); }
#endif // frac_test_hpp
frac_test.cpp
/test/frac_test.cpp
#include "../includes/frac_test.hpp"
#include "../includes/template_fraction.hpp"
#include "../includes/int_fraction.hpp"
#include <vector>
#include <random>
#include <iomanip>
#include <math.h>
#include <chrono>
#include <limits>
using checked::fraction::Fraction;
using i64 = std::int64_t;
std::random_device rd;
std::mt19937 eng32(rd());
i64 get_random_32() { return (static_cast<i64>(eng32()) / std::pow(10, eng32() % 5)) + 1; }
enum class Op : std::size_t { add=0, sub=1, mul=2, div=3, equ=4 };
template <typename T> std::size_t to_size(const T& op) { return static_cast<std::size_t>(op); }
template <typename T> T op_divided(const Op& op, std::vector<T>&& list) {
switch(op) {
case Op::add: return list.at(to_size(Op::add));
case Op::sub: return list.at(to_size(Op::sub));
case Op::mul: return list.at(to_size(Op::mul));
case Op::div: return list.at(to_size(Op::div));
case Op::equ: return list.at(to_size(Op::equ));
}
std::exit(8);
}
std::ostream& operator<<(std::ostream& out, const Op& op) {
out << op_divided(op, std::vector{"+", "-", "*", "/", "="});
return out;
}
template <typename T> T calc_result(const T& lhs, const T& rhs, const Op& op) {
return op_divided(op, std::vector<T>{ lhs + rhs, lhs - rhs, lhs * rhs, lhs / rhs });
}
template <typename T> void output(const T& lhs, const T& rhs, const Op& op) {
std::cout << lhs << op << rhs << Op::equ << calc_result(lhs, rhs, op) << std::endl;
return;
}
namespace simple {
void test() {
Fraction<i64> a(1, 5), b(2, 7), c(1, 5);
output(a, b, Op::add);
output(a, b, Op::sub);
++a, ++b, c++;
output(a, b, Op::mul);
output(a, b, Op::div);
--a, --b, c--;
std::cout << a << " == " << b << " => " << std::boolalpha << (a == b) << std::endl;
std::cout << a << " != " << b << " => " << std::boolalpha << (a != b) << std::endl;
std::cout << a << " == " << c << " => " << std::boolalpha << (a == c) << std::endl;
std::cout << a << " < " << b << " => " << std::boolalpha << (a < b) << std::endl;
std::cout << a << " > " << b << " => " << std::boolalpha << (a > b) << std::endl;
return;
}
}
Op get_random_op() {
return op_divided(static_cast<Op>(eng32() % 4), std::vector<Op>{ Op::add, Op::sub, Op::mul, Op::div });
}
namespace normal_calc {
constexpr int cases = 100000000;
constexpr std::streamsize w = 15;
constexpr bool large_test = false;
void test() {
std::cout << "Normal calc test ( Cases: " << cases << " ) => ";
double total_error = 0.0;
int overflowed = 0;
int infinity = 0;
auto start = std::chrono::system_clock::now();
for(int i = 0; i < cases; ++i) {
i64 ln(get_random_32()), ld(get_random_32()), rn(get_random_32()), rd(get_random_32());
Fraction<i64> lhs_f(ln, ld), rhs_f(rn, rd);
double lhs_d(static_cast<double>(ln) / static_cast<double>(ld)), rhs_d(static_cast<double>(rn) / static_cast<double>(rd));
Op op = get_random_op();
Fraction<i64> result_f = calc_result(lhs_f, rhs_f, op);
double result_d = calc_result(lhs_d, rhs_d, op);
double error = std::abs((static_cast<double>(result_f) - result_d) / static_cast<double>(result_f));
if(result_f.get_status() == checked::HadOverflowed::Yes) ++overflowed;
else if(error == std::numeric_limits<double>::infinity()) ++infinity;
else total_error += error;
}
auto end = std::chrono::system_clock::now();
double average_error = total_error / static_cast<double>(cases - overflowed - infinity);
double overflow_ratio = (static_cast<double>(overflowed) / static_cast<double>(cases)) * 100.0;
double infinity_ratio = (static_cast<double>(infinity) / static_cast<double>(cases)) * 100.0;
std::cout << "average error: [ " << average_error << " < " << "10e-15.955" << " ] ? ( Overflowed: " << overflow_ratio << " %";
std::cout << ", Infinity: " << infinity_ratio << " % ) => ";
if(average_error < std::pow(10, -15.955)) std::cout << "OK";
else if(average_error < std::pow(10, -15)) std::cout << "Possibly OK ( average_error < 10e-15 )";
else std::cout << "NG";
std::cout << " => Time: " << std::chrono::duration_cast<std::chrono::seconds>(end-start).count() << " (s)" << std::endl;
return;
}
}
namespace comparison {
constexpr int cases = 100000000;
enum class Comp : std::size_t { equ, neq, gtr, lss, geq, leq };
template <typename T> T comparison_divided(const Comp& c, std::vector<T>&& list) {
switch(c) {
case Comp::equ: return list.at(to_size(Comp::equ));
case Comp::neq: return list.at(to_size(Comp::neq));
case Comp::gtr: return list.at(to_size(Comp::gtr));
case Comp::lss: return list.at(to_size(Comp::lss));
case Comp::geq: return list.at(to_size(Comp::geq));
case Comp::leq: return list.at(to_size(Comp::leq));
}
std::exit(8);
}
Comp get_random_logical() {
return comparison_divided(static_cast<Comp>(eng32() % 6), std::vector{ Comp::equ, Comp::neq, Comp::gtr, Comp::lss, Comp::geq, Comp::leq });
}
std::ostream& operator<<(std::ostream& out, const Comp& c) {
out << comparison_divided(c, std::vector{ " == ", " != ", " < ", " > ", " <= ", " >= " });
return out;
}
void test() {
int correct = 0;
std::cout << "Comparison operation test ( Cases: " << cases << " ) => ";
auto start = std::chrono::system_clock::now();
bool first(true);
for(int i = 0; i < cases; ++i) {
i64 ln(get_random_32()), ld(get_random_32()), rn(get_random_32()), rd(get_random_32());
Fraction<i64> lhs_f(ln, ld), rhs_f(rn, rd);
double lhs_d(static_cast<double>(ln) / static_cast<double>(ld)), rhs_d(static_cast<double>(rn) / static_cast<double>(rd));
Comp c = get_random_logical();
bool result_f = comparison_divided(c, std::vector<bool>{ (lhs_f == rhs_f), (lhs_f != rhs_f), (lhs_f > rhs_f), (lhs_f < rhs_f), (lhs_f >= rhs_f), (lhs_f <= rhs_f) });
bool result_d = comparison_divided(c, std::vector<bool>{ (lhs_d == rhs_d), (lhs_d != rhs_d), (lhs_d > rhs_d), (lhs_d < rhs_d), (lhs_d >= rhs_d), (lhs_d <= rhs_d) });
if(result_f == result_d) ++correct;
else {
if(first) { first = false; std::cout << std::endl; }
std::cout << "\t- Error case:";
std::cout << lhs_f << c << rhs_f << " => Fraction result: " << std::setw(5) << std::boolalpha << result_f << ", double result: " << std::setw(5) << result_d << std::endl;
}
}
auto end = std::chrono::system_clock::now();
std::cout << "Correct cases: ";
if(correct == cases) std::cout << "[ " << correct << " == " << cases << " ] => " << "OK";
else if(static_cast<double>(cases) * 0.9999 < correct) std::cout << "[ " << correct << " > " << static_cast<int>(static_cast<double>(cases) * 0.9999) << " ( > 99.99 % ) ] => " << "Possibly OK";
else std::cout << correct << " => " << "NG";
std::cout << " => Time: " << std::chrono::duration_cast<std::chrono::seconds>(end-start).count() << " (s)" << std::endl;
return;
}
}
namespace speed {
constexpr int cases = 10;
constexpr int ratio_cases = 10;
constexpr int operation = 1000000;
template <typename T> std::vector<T> query(std::mt19937_64& eng) {
std::vector<T> all;
for(int i = 0; i < operation; ++i) {
i64 ln(static_cast<i64>(eng())), ld(static_cast<i64>(eng())), rn(static_cast<i64>(eng())), rd(static_cast<i64>(eng()));
T lhs(ln, ld), rhs(rn, rd), res;
Op op = op_divided(static_cast<Op>(eng() % 4), std::vector<Op>{ Op::add, Op::sub, Op::mul, Op::div });
res = op_divided(op, std::vector{ lhs + rhs, lhs - rhs, lhs * rhs, lhs / rhs });
all.push_back(res);
}
return all;
}
template <> std::vector<double> query<double>(std::mt19937_64& eng) {
std::vector<double> all;
for(int i = 0; i < operation; ++i) {
i64 ln(static_cast<i64>(eng())), ld(static_cast<i64>(eng())), rn(static_cast<i64>(eng())), rd(static_cast<i64>(eng()));
double lhs(static_cast<double>(ln) / static_cast<double>(ld)), rhs(static_cast<double>(rn) / static_cast<double>(rd)), res;
Op op = op_divided(static_cast<Op>(eng() % 4), std::vector<Op>{ Op::add, Op::sub, Op::mul, Op::div });
res = op_divided(op, std::vector<double>{ lhs + rhs, lhs - rhs, lhs * rhs, lhs / rhs });
all.push_back(res);
}
return all;
}
void test() {
std::cout << "Speed test ( Ratio cases: " << ratio_cases << ", Cases: " << cases << ", Operations: " << operation << " )" << std::endl;
double total_d(0.0), total_f(0.0), total_if(0.0), total_ratio_df(0.0), total_ratio_dif(0.0), total_ratio_fif(0.0);
auto start = std::chrono::system_clock::now();
for(int i = 0; i < ratio_cases; ++i) {
double total_d_r = 0.0, total_f_r = 0.0, total_if_r = 0.0;
std::vector<double> all_d;
std::vector<Fraction<i64>> all_f;
std::vector<integer::fraction::Fraction<i64>> all_if;
std::uint32_t seed = eng32();
for(int j = 0; j < cases; ++j) {
std::mt19937_64 eng_d(seed);
auto start_d = std::chrono::system_clock::now();
all_d = query<double>(eng_d);
auto end_d = std::chrono::system_clock::now();
std::mt19937_64 eng_f(seed);
auto start_f = std::chrono::system_clock::now();
all_f = query<checked::fraction::Fraction<i64>>(eng_f);
auto end_f = std::chrono::system_clock::now();
std::mt19937_64 eng_if(seed);
auto start_if = std::chrono::system_clock::now();
all_if = query<integer::fraction::Fraction<i64>>(eng_if);
auto end_if = std::chrono::system_clock::now();
total_d_r += std::chrono::duration_cast<std::chrono::milliseconds>(end_d - start_d).count();
total_f_r += std::chrono::duration_cast<std::chrono::milliseconds>(end_f - start_f).count();
total_if_r+= std::chrono::duration_cast<std::chrono::milliseconds>(end_if - start_if).count();
}
total_d += total_d_r;
total_f += total_f_r;
total_if+= total_if_r;
if(i == ratio_cases - 1) {
std::cout << "Result: Average Calculation Time" << std::endl;
std::cout << "\t- Average calculation time (double) : " << total_d / static_cast<double>(ratio_cases * cases) << " (ms)" << std::endl;
std::cout << "\t- Average calculation time (IntFraction) : " << total_if / static_cast<double>(ratio_cases * cases) << " (ms)" << std::endl;
std::cout << "\t- Average calculation time (CheckedFraction): " << total_f / static_cast<double>(ratio_cases * cases) << " (ms)" << std::endl;
}
total_ratio_df += (total_f_r / static_cast<double>(cases)) / (total_d_r / static_cast<double>(cases));
total_ratio_dif+= (total_if_r/ static_cast<double>(cases)) / (total_d_r / static_cast<double>(cases));
total_ratio_fif+= (total_f_r / static_cast<double>(cases)) / (total_if_r/ static_cast<double>(cases));
}
auto end = std::chrono::system_clock::now();
std::cout << "Result: Average Ratio" << std::endl;
std::cout << "\t- Average Intraction / double ratio: " << total_ratio_dif/ static_cast<double>(ratio_cases) << std::endl;
std::cout << "\t- Average CheckedFraction / double ratio: " << total_ratio_df / static_cast<double>(ratio_cases) << std::endl;
std::cout << "\t- Average CheckedFraction / IntFraction ratio: " << total_ratio_fif/ static_cast<double>(ratio_cases) << std::endl;
std::cout << "=> Time: " << std::chrono::duration_cast<std::chrono::seconds>(end - start).count() << std::endl;
return;
}
}
main.cpp
/test/main.cpp
#include <iostream>
#include "../includes/frac_test.hpp"
int main() {
simple::test();
normal_calc::test();
comparison::test();
speed::test();
return 0;
}
Result.txt
Result.txt
1/ 5+ 2/ 7= 17/ 35
1/ 5- 2/ 7= -3/ 35
6/ 5* 9/ 7= 54/ 35
6/ 5/ 9/ 7= 14/ 15
1/ 5 == 2/ 7 => false
1/ 5 != 2/ 7 => true
1/ 5 == 1/ 5 => true
1/ 5 < 2/ 7 => true
1/ 5 > 2/ 7 => false
Normal calc test ( Cases: 100000000 ) => average error: [ 7.49344e-17 < 10e-15.955 ] ? ( Overflowed: 1.49578 %, Infinity: 0.000887 % ) => OK => Time: 117 (s)
Comparison operation test ( Cases: 100000000 ) =>
- Error case: 229736239/ 290120859 >= 121812/ 162416 => Fraction result: true, double result: false
Correct cases: [ 99999999 > 99990000 ( > 99.99 % ) ] => Possibly OK => Time: 69 (s)
Speed test ( Ratio cases: 10, Cases: 10, Operations: 1000000 )
Result: Average Calculation Time
- Average calculation time (double) : 155.92 (ms)
- Average calculation time (IntFraction) : 930.56 (ms)
- Average calculation time (CheckedFraction): 540.46 (ms)
Result: Average Ratio
- Average Intraction / double ratio: 5.97362
- Average CheckedFraction / double ratio: 3.46895
- Average CheckedFraction / IntFraction ratio: 0.580739
=> Time: 162
結果としては
- 通常の演算における誤差が$10^{-17}$程なので、正しく演算できていると考えられます。
- 比較演算についても
Error CaseをWolframAlphaで見てみるとFractionの方が正しい結果になっていると分かります。 - 演算速度は
double型と比べて3.5倍程度の遅延があります。
となります。template_fractionをコピペして作ったint_fractionはなぜかは知りませんがCheckedを使用したものより遅くなってます。なんだこれ...
CMake
CMakeLists.txt
cmake_minimum_required(VERSION 3.16)
set(CMAKE_CXX_STANDARD 20)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_FLAGS "-Wall -Wextra -std=c++20")
set(CMAKE_CXX_FLAGS_RELEASE "-Ofast -flto -mtune=native -march=native")
project(fraction)
add_subdirectory(src)
add_subdirectory(test)
/test/CMakeLists.txt
add_executable(
main
main.cpp
template_frac_test.cpp
)
あとがき
元々はFlagged.hpp、Checked.hpp、Checked.cpp、CheckedFraction.hpp、Fraction.hpp、Fraction.cppに分かれていたためフォルダが分割されています。
最近編集履歴を確認できることを知りました。わざわざ線で消すみたいなことしなくても良かったです。