What's in a Generic Number Type?
Pick a number, any typeof number

05 January 2017

Recently, I’ve been looking over an old signal processing textbook from university. It’s been a few of years, so I remember parts of it and don’t remember other parts at all. I decided, as a way to make it more interesting, I would code up a library in Rust to do the stuff I was reading over while I was reading it.

To make this library more flexible, I decided that the underlying number type should be generic. For example, a complex number would look something like this:

pub struct Complex<T> {
    pub real: T,
    pub imag: T
}

What is a Generic Type?

Maybe I should back up a bit, and start at the beginning, what is a generic type? The easiest way to explain this would probably be with an example. Say I were implementing a complex number data type, and I decided it would only need to hold integers. Here it is:

pub struct ComplexInt {
    pub real: i32,
    pub imag: i32
}

Add a hundred or so lines of implementation around conjugating, going to and from polar form, and arithmetic operations like adding and multiplication, and you have a useful type for complex integers.

And then you need one for working with floating point numbers…

So you do the whole thing over with floats.

pub struct ComplexFloat {
    pub real: f32,
    pub imag: f32
}

When you do the implementation, you’ll find that adding two ComplexInts together is very similar to adding two ComplexFloats together. Many programming languages, including Rust, use generic types to handle this problem. You define your data structure and its functionality once, in terms of a generic type T, and when you use it you specify what T needs to be.

pub struct Complex<T> {
    pub real: T,
    pub imag: T
}

let complex_int = Complex::<i32> {
    real: 1,
    imag: 2
};
let complex_float = Complex::<f32> {
    real: 1.5,
    imag: 2.7
};
//if you leave out the ::<f32>, Rust will infer the type from the values you use

However, if type T can be absolutely anything, we can’t write any useful complex number functionality. We need to put some constraints on T so that we can work with it.

What Limitations Do I Need?

The actual type of T will end up affecting two aspects of your complex number: what the actual data looks like as bytes laid out in memory, and what you can do with it.

Broadly speaking, it doesn’t really matter to your complex number functions how it looks in memory, as long as the compiler can tell how big T is at compile time so that it can allocate memory correctly. On the other hand, it does matter a whole lot what you can do with T. For example, if you want to add two complex numbers together, you need to be able to add two Ts together.

Rust lets you enforce this by specifying that T must implement certain Traits.

Traits

In Rust, a trait is a set of functions that are implemented for a data type. You can use traits sort of like you would use interfaces in other languages.

Some of the traits in the standard library are for overloading the arithmetic operators. For example, if I wanted to add two complex numbers together with a +, then I would implement the Add trait like so:

use std::ops::Add;

#[derive(Debug)]
pub struct Complex<T> {
    pub real: T,
    pub imag: T
}

impl<T> Add for Complex<T> where T: Add<Output=T> {
    type Output = Complex<T>;

    fn add(self, other: Complex<T>) -> Complex<T> {
        Complex {
            real: self.real + other.real,
            imag: self.imag + other.imag
        }
    }
}

let a = Complex { real: 1, imag: 5 };
let b = Complex { real: -3, imag: 2 };
println!("a + b = {:?}", a+b); // a + b = Complex { real: -2, imag: 7 }

To be able to do this, I needed to be able to add two numbers of type T together. I make sure I can do this with where T: Add<Output=T>, which means that T needs to implement the Add trait, and if I add a T to a T I get another T as the output. Since Add is part of the standard library, it is already implemented for all of the primitive integer and floating point types.

Something that I found really interesting is that the restriction on T is on the functionality of my complex type, and not on the data type itself. I could, for example, create a Complex with T as a string, but I wouldn’t be able to add two of them together.

Arithmetic Operations

I think it would be useful to be able to do other arithmetic operations on my complex numbers. The arithmetic operations, according to Wikipedia, are addition, subtraction, multiplication, and division.

In rust, that means implementing the traits called Add, Sub, Mul, and Div.

Multiplication is an interesting one, because it needs more than just multiplying two Ts together. You also need to be able to add and subtract! Mathematically, you can see why by multiplying it out by hand.

  (a + ib) * (c + id)
= (ac - bd) + i(bc + ad)

Or, to put it in Rust

use std::ops::{Add, Sub, Mul};

#[derive(Debug)]
pub struct Complex<T> {
    pub real: T,
    pub imag: T
}

impl<T> Mul for Complex<T> 
    where T: Add<Output=T> + Sub<Output=T> + Mul<Output=T> + Clone {
    type Output = Complex<T>;

    fn mul(self, other: Complex<T>) -> Complex<T> {
        //   (a + ib) * (c + id)
        // = (ac - bd) + i(bc + ad)
        let a = self.real;
        let b = self.imag;
        let c = other.real;
        let d = other.imag;

        Complex {
            real: (a.clone() * c.clone()) - (b.clone() * d.clone()),
            imag: (b * c) + (a * d)
        }
    }
}

let a = Complex { real: 2, imag: 1 };
let b = Complex { real: 3, imag: 2 };
println!("a * b = {:?}", a*b); // a * b = Complex { real: 4, imag: 7 }

You might also notice that I needed to copy the values with clone() the first time I used them. This is because I still need those values for the second part. If I didn’t make copies with clone(), it wouldn’t compile because I wouldn’t have ownership of the values after using them.

The Other Arithmetic Operation - Negation

What’s the difference between subtraction and negation?

One answer would be the number of numbers involved. Subtraction is a-b, whereas negation is just -b.

They are clearly related. You can write negation in terms of subtraction with a zero (-b = 0-b), and you can write subtraction in terms of negation and addition (a-b = a+(-b)). What is the core difference and why do we need both?

I’m sure there are many good answers for this, but the one I came up with while working on my complex numbers is how to handle unsigned numbers.

An unsigned number is a number that can only be positive. They are commonly used for values like the indexes in arrays, where negative numbers don’t make any sense. You can still do subtraction between unsigned numbers, as long as you are always subtracting a larger number from a smaller number. However, you cannot negate an unsigned number.

Rust provides the Neg trait for negation, and I’ve implemented it on my complex number type (where T: Neg<Output=T>). Something interesting about having the restrictions tied to the function, and not to the Complex struct itself, is what happens if I create a complex number where T is unsigned. I can still use all of my other complex functions. Just the negation is not implemented.

If you are using a generic type, and get a weird compile error saying that a function doesn’t exist when you can clearly see it does, maybe just check the restrictions the function puts on the generic type.

Bring Your Own Pi

As my journey into generic types and maths brought me to some trigonometry, I found that Pi started to crop up. Not only did I need a value for Pi, I needed that value to be of the generic type T.

Rust’s standard library provides values for Pi for all of it’s primitive floating point number types, I just needed a way to express generically in terms of T which one to use.

I solved this by adding my own trait, and implementing it for the standard library primitives. Anyone else that wants to use my types with their own number type as T would also need to implement the traits to provide the appropriate constants.

pub trait Pi {
    fn pi() -> Self;
}

impl Pi for f32 {
    fn pi() -> f32 {
        std::f32::consts::PI
    }
}

impl Pi for f64 {
    fn pi() -> f64 {
        std::f64::consts::PI
    }
}


fn print_pi<T>() where T: Pi + std::fmt::Display {
    println!("PI for type T is {}", T::pi());
}

print_pi::<f32>(); //PI for type T is 3.1415927
print_pi::<f64>(); //PI for type T is 3.141592653589793

Sometimes, you need to do this for less exotic constants as well, like zero and one.

That’s Not All

You can find these examples in a longer form, with much more context, in the code I’m working on in this repo on GitHub.

But if you want really good examples of making new and useful number types in Rust, done by the Rust team, then check out Num (also on GitHub). Num is the library I’m looking at for inspiration when I want to figure out how to do my own generic numbers better.