프로젝트 오일러 문제를 Rust로 풀다가 불현듯 Rust로 분수 타입을 구현해 놓으면 좋겠다는 생각이 들었다. Clojure에서는 정수끼리 나누기를 하면 분수(clojure.lang.Ratio)가 나오기 때문에 문제 풀이에 유용하게 사용할 수 있었다. Rust 표준 라이브러리에는 분수 타입이 포함되어 있지 않지만, 만들기 어려울 것 같지도 않았다.
Ratio 구조체 정의
먼저 구조체를 만들어야 한다. 이름은 Ratio로 하려 한다. 여러 정수 타입에 대해 동작하게 하려면 제너릭을 써야 한다. count_digits 함수 구현에서 했던 것과 마찬가지로 Int 트레잇이 필요하다.
pub trait Int {
fn zero() -> Self;
fn one() -> Self;
}
macro_rules! impl_int_for {
( $( $t:ty )* ) => {
$( impl Int for $t {
fn zero() -> Self { 0 }
fn one() -> Self { 1 }
} )*
};
}
impl_int_for!(u8 u16 u32 u64 u128 i8 i16 i32 i64 i128);
이제 다음과 같이 Ratio를 정의한다.
pub struct Ratio<T: Int> {
pub nu: T, // numerator
pub de: T, // denominator
}
그리고 다음과 같이 Ratio에 다음과 같이 연관 함수와 메서드를 구현한다.
impl<T: Int> Ratio<T> {
pub fn new(nu: T, de: T) -> Self {
// ...
}
fn gcd(mut m: T, mut n: T) -> T {
// ...
}
fn reduce(&mut self) -> Self {
// ...
}
}
new()는 다음과 같이 간단히 정의할 수 있다.
pub fn new(nu: T, de: T) -> Self {
Self {
nu,
de,
}
.reduce()
}
reduce() 메서드는 아직 정의하지 않았지만, 분수를 저장한 때 항상 약분한 형태로 저장하기 위해 구조체를 생성한 후 바로 호출하도록 했다.
약분을 구현하려면 최대공약수를 알아야 한다. 따라서 다음과 같이 gcd() 함수를 정의한다.
fn gcd(mut m: T, mut n: T) -> T {
let zero = T::zero();
assert!(m != zero && n != zero);
while m != zero {
if m < n {
std::mem::swap(&mut m, &mut n);
}
m %= n;
}
n
}
m, n의 타입 T는 비교 연산(!=, < 등)이 필요하므로 PartialEq와 PartialOrd 트레잇을 추가해야 한다. 사실 T에 대해 더하기, 빼기, 곱하기, 나누기 등의 모든 연산이 필요하므로 다음과 같이 Int 트레잇을 수정한다.
use std::ops::{Add, Sub, Mul, Div, Rem, DivAssign, RemAssign};
pub trait Int:
Copy
+ Default
+ Add<Output = Self>
+ Sub<Output = Self>
+ Mul<Output = Self>
+ Div<Output = Self>
+ Rem<Output = Self>
+ DivAssign
+ RemAssign
+ Sized
+ PartialEq
+ PartialOrd {
fn zero() -> Self;
fn one() -> Self;
}
reduce() 메서드는 다음과 같이 정의할 수 있다. 분모가 0이면 panic이고, 분자가 0이면 분모를 1로 만들고 바로 리턴한다.
fn reduce(&mut self) -> Self {
if self.de == T::zero() {
panic!("denominator == 0");
}
if self.nu == T::zero() {
self.de = T::one();
return *self;
}
let gcd = Self::gcd(self.nu, self.de);
self.nu /= gcd;
self.de /= gcd;
*self
}
코드를 컴파일하면 다음과 같이 컴파일 에러가 발생하는 것을 볼 수 있다.
| 72 | *self | ^^^^^ move occurs because `*self` has type `ratio::Ratio`, | which does not implement the `Copy` trait
Ratio 필드 Int는 Copy 타입이므로 Ratio도 다음과 같이 Copy 타입으로 만들 수 있다. 수정하는 김에 Debug, PartialEq도 함께 추가한다.
#[derive(Debug, Copy, Clone, PartialEq)]
pub struct Ratio<T: Int> {
pub nu: T,
pub de: T,
}
다시 컴파일해보면 에러 없이 성공하는 것을 화인할 수 있다. 다음과 같이 간단한 테스트를 추가해 돌려보자.
#[test]
fn test_new() {
let r0 = Ratio::new(0, 10);
assert_eq!(r0.nu, 0);
assert_eq!(r0.de, 1);
let r1 = Ratio::new(2, 4);
assert_eq!(r1.nu, 1);
assert_eq!(r1.de, 2);
let r2 = Ratio::new(3, 12);
assert_eq!(r2.nu, 1);
assert_eq!(r2.de, 4);
}
약분도 문제 없이 잘 동작한다.
분모가 0인 경우는 정의되지 않으므로 다음과 같이 에러가 발생하는 것을 확인할 수 있다.
#[test]
#[should_panic]
fn test_zero_denominator() {
Ratio::new(10, 0);
}
사칙연산 지원
Ratio 구조체를 만들기는 했지만, 아직까지는 별로 유용해보이지 않는다. 다른 숫자 타입처럼 Ratio도 덧셈, 뺄셈, 곱셈, 나눗셈을 할 수 있다면 훨씬 유용할 것이다. 즉, Ratio에 Add, Sub, Mul, Div 트레잇을 구현해야 한다.
impl<T: Int> Add for Ratio<T> {
type Output = Self;
fn add(self, rhs: Self) -> Self::Output {
Self {
nu: self.nu * rhs.de + self.de * rhs.nu,
de: self.de * rhs.de,
}
.reduce()
}
}
impl<T: Int> Sub for Ratio<T> {
type Output = Self;
fn sub(self, rhs: Self) -> Self::Output {
Self {
nu: self.nu * rhs.de - self.de * rhs.nu,
de: self.de * rhs.de,
}
.reduce()
}
}
impl<T: Int> Mul for Ratio<T> {
type Output = Self;
fn mul(self, rhs: Self) -> Self::Output {
Self {
nu: self.nu * rhs.nu,
de: self.de * rhs.de,
}
.reduce()
}
}
impl<T: Int> Div for Ratio<T> {
type Output = Self;
fn div(self, rhs: Self) -> Self::Output {
Self {
nu: self.nu * rhs.de,
de: self.de * rhs.nu,
}
.reduce()
}
}
다음과 같이 테스트를 추가해 돌려보면 잘 돌아감을 확인할 수 있다.
#[test]
fn test_arithmetic() {
let one_half = Ratio::new(1, 2);
let one_third = Ratio::new(1, 3);
assert_eq!(one_half + one_third, Ratio::new(5, 6));
assert_eq!(one_half - one_third, Ratio::new(1, 6));
assert_eq!(one_half * one_third, Ratio::new(1, 6));
assert_eq!(one_half / one_third, Ratio::new(3, 2));
}
음수 처리
사칙연산 외에도 - 연산자를 통해 분수 전체를 음수로 만드는 것도 가능해야 한다. 좀더 생각해보니 Ratio에서 분모나 분자가 음수가 될 수 있다. 최대공약수를 구하는 gcd() 함수도 입력에 따라 음수 또는 양수가 될 수 있고, 경우에 따라 무한루프에 빠지기도 하는 문제가 있다. 조금 찾아보니 최대공약수를 구할 때는 인자를 모두 양수로 만들어 구해도 된다.
따라서 함수 앞 부분에서 루프를 돌리기 전에 m, n이 음수인지 확인하고 음수인 경수 양수로 바꿔주면 된다. 그런데 여기서 문제가 생긴다. 일단 m = -m과 같은 식으로 부호를 바꿀 수는 없다. 이렇게 하려면 T가 Neg 트레잇을 구현해야 하지만, 이렇게 하면 부호 없는 타입(u8, u16, u32 등)에 대해서는 동작하지 않는다.
대안으로 Abs 트레잇을 정의한 다음 abs() 메서드를 부호 있는 정수와 부호 없는 정수에 대해 다르게 구현할 수 있다. 즉 부호 있는 정수에서는 값이 0보다 작은 경우 -self를 리턴하도록 하고, 부호 없는 정수에 대해서는 0보다 작아질 수가 없으므로 항상 자기 자신을 그대로 리턴하게 하면 된다.
그러나 더 간단한 방법을 찾았다. 부호 있는 정수든 부호 없는 정수든 Sub 트레잇을 구현하고 있으므로 다음과 같이 0에서 해당 수를 빼주면 된다. 부호 없는 정수는 항상 0보다 크거나 같으므로 if 안의 코드가 실행될 일은 없다.
fn gcd(mut m: T, mut n: T) -> T {
let zero = T::zero();
assert!(m != zero && n != zero);
if m < zero {
m = zero - m;
}
if n < zero {
n = zero - n;
}
while m != zero {
// ...
}
Ratio가 음수가 된다는 것은 분모 또는 분자가 음수가 되는 경우다. 분모, 분자가 모두 음수인 경우 Ratio는 양수가 된다. 이렇게 분모, 분자가 각각 음수가 될 수 있게 하는 것 보다는, 분자만 음수가 될 수 있고 분모는 항상 양수가 되도록 하는 게 여러 모로 생각하기 편하다. 따라서 redoce() 메서드에서 분모가 음수인 경우 분자의 부호를 바꾸도록 수정한다.
fn reduce(&mut self) -> Self {
// ...
let zero: T = T::zero();
if self.de < zero {
self.nu = zero - self.nu;
self.de = zero - self.de;
}
*self
}
테스트에 다음을 추가해 돌려보자.
fn test_new() {
// ...
let r3 = Ratio::new(2, -4);
assert_eq!(r3.nu, -1);
assert_eq!(r3.de, 2);
let r4 = Ratio::new(-3, -12);
assert_eq!(r4.nu, 1);
assert_eq!(r4.de, 4);
}
그리고 분모 자체를 마이너스로 만드는 것도 지원해야 한다. 즉 Ratio 타입 r에 대해 -r도 가능하도록 해야 한다. 이렇게 하려면 Neg 트레잇을 구현해야 한다. 분모는 항상 양수로 하고 분자에 부호를 저장하기로 했으므로, neg() 메서드에서 분자의 부호를 반대로 바꿔주면 된다.
impl <T:Int> Neg for Ratio<T> {
type Output = Self;
fn neg(self) -> Self::Output {
Self {
nu: T::zero() - self.nu,
de: self.de,
}
}
}
다음과 같이 테스트를 추가해 생각한 대로 잘 동작하는지 확인한다.
#[test]
fn test_neg() {
assert_eq!(-Ratio::new(1, 2), Ratio::new(-1, 2));
assert_eq!(-Ratio::new(1, -2), Ratio::new(1, 2));
assert_eq!(-Ratio::new(-1, 2), Ratio::new(1, 2));
assert_eq!(-Ratio::new(-1, -2), Ratio::new(-1, 2));
}
비교 지원
두 분수를 비교하려면 PartialOrd 트레잇을 구현해야 한다. 분수의 크기를 비교하는 방법은 초등학교 때 배웠을 것이다. 분모가 같으면 분자를 비교하면 되고, 분모가 다르면 통분해 분모를 같게 만든 다음 분자를 비교하면 된다.
impl<T: Int> PartialOrd for Ratio<T> {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
if self.de == other.de {
self.nu.partial_cmp(&other.nu)
} else {
let self_nu = self.nu * other.de;
let other_nu = self.de * other.nu;
self_nu.partial_cmp(&other_nu)
}
}
}
다음과 같이 테스트해보면 크기를 잘 비교함을 확인할 수 있다.
#[test]
fn test_ord() {
assert!(Ratio::new(1, 2) > Ratio::new(1, 3));
assert!(Ratio::new(1, 3) < Ratio::new(1, 2));
assert!(Ratio::new(1, 2) > Ratio::new(1, -3));
assert!(Ratio::new(-1, 3) < Ratio::new(1, 2));
assert!(Ratio::new(1, 2) == Ratio::new(1, 2));
}
마무리
처음에는 간단할 줄 알았는데, 하다보니 끝이 없다. 복잡한 건 아니지만, AddAssign, SubAssign, MulAssign, DivAssign 트레잇도 구현해야 한다. 분수와 정수 사이의 변환도 구현해야 할 것 같다. floor, ceil, round 같은 메서드도 구현할 수 있다. 부동소수점 형으로 근사값을 구하는 메서드도 구현할 수 있다. 뭔가 제대로 하려면 아직 한참을 더 해야 할 것 같다.
그런데, num 크레잇에서 이미 Ratio를 구현해 놓았다는 사실을 알게 되었다. 소스코드를 살펴보니 더 많은 기능이 구현되어 있고, 최적화도 많이 된 듯 하다. 생각해보이, 이런 기본적인 데이터 구조는 이미 구현되어 있을 게 뻔했는데, 왜 찾아볼 생각을 하지 않았나 모르겠다. 그러나 간만에 재미있게 코딩했고, 특히 정수형을 제너릭으로 처리할 때 도움이 될 팁을 많이 배웠다는 것을 위안으로 삼아야 겠다.