Generic numeric functions in safe, stable Rust with the num crate
Note: This post assumes some familiarity with Rust, in particular traits.
Introduction🔗
It is useful to be able to write code that is generic over multiple types, such as integer types.
The Rust standard library originally had the unstable (deprecated since release 1.11.0) traits Zero and One that could partially help, but these required the nightly compiler.
Since then, the num crate has moved out of the standard library.
In this post, I used stable Rust version 1.15.1. The code examples will probably work with earlier versions as well.
All example code is available on GitHub.
What do we need?🔗
In order to be able to write a generic function for various number types, we need a trait that guarantees several things, including:
- Addition
- Multiplication
- Equality testing
The num crate has the useful PrimInt trait which inherits various traits.
Factorial example🔗
The factorial function is defined to be the product of integers from 1 to n (inclusive).
The special case of 0! = 1.
For example, 4! = 4 * 3 * 2 * 1 = 24.
Factorial is defined only for non-negative integers.
Concrete function🔗
Let's start with an non-generic factorial function:
/// Find the factorial of n
fn factorial(n: u32) -> u32 {
(1..n + 1).product()
}
This function only supports the concrete u32 type.
Generic attempt 1🔗
We make the n parameter have the generic type T with the trait bound requiring the PrimInt trait and Unsigned trait:
extern crate num;
use num::{PrimInt, Unsigned};
/// Find the factorial of n
fn factorial<T>(n: T) -> T
where T: PrimInt + Unsigned
{
(1..n + 1).product()
}
We get the following error:
error[E0308]: mismatched types
--> src/main.rs:9:13
|
9 | (1..n + 1).product()
| ^ expected type parameter, found integral variable
|
= note: expected type `T`
= note: found type `{integer}`
error[E0308]: mismatched types
--> src/main.rs:9:9
|
9 | (1..n + 1).product()
| ^^^^^ expected integral variable, found type parameter
|
= note: expected type `{integer}`
= note: found type `T`
...
Generic attempt 2🔗
It seems like we cannot use the 1 literal.
Luckily, the PrimInt trait inherits from the One trait (through Num), which requires the one() method.
extern crate num;
use num::{PrimInt, Unsigned};
/// Find the factorial of n
fn factorial<T>(n: T) -> T
where T: PrimInt + Unsigned
{
(T::one()..n + T::one()).product()
}
However, we still get the error related to the required traits (like Step) being implemented.
We could state in a where clause that the Step trait is required, but as of writing, Step is not stable.
error: no method named `product` found for type `std::ops::Range<T>` in the current scope
--> src/main.rs:9:30
|
9 | (T::one()..n + T::one()).product()
| ^^^^^^^
|
= note: the method `product` exists but the following trait bounds were not satisfied: `T : std::iter::Step`, `&'a T : std::ops::Add`, `std::ops::Range<T> : std::iter::Iterator`
Generic attempt 3🔗
We can avoid the ".." range syntax by using and use num's range function.
extern crate num;
use std::iter::Product;
use num::{PrimInt, Unsigned};
/// Find the factorial of n
fn factorial<T>(n: T) -> T
where T: PrimInt + Unsigned
{
num::range(T::one(), n + T::one()).product()
}
The PrimInt trait still does not guarantee the existence of the Product trait.
error[E0277]: the trait bound `T: std::iter::Product` is not satisfied
--> src/main.rs:10:40
|
10 | num::range(T::one(), n + T::one()).product()
| ^^^^^^^ the trait `std::iter::Product` is not implemented for `T`
|
= help: consider adding a `where T: std::iter::Product` bound
Final result🔗
We can import Product add add it to the where clause.
Now we have a factorial function that works over arbitrary unsigned integer type!
extern crate num;
use std::iter::Product;
use num::{PrimInt, Unsigned};
/// Find the factorial of n
fn factorial<T>(n: T) -> T
where T: PrimInt + Unsigned + Product
{
num::range(T::one(), n + T::one()).product()
}
Using the generic function🔗
Now we can call our factorial function with different unsigned types.
fn main() {
println!("u8: 3! = {}", factorial(3_u8));
println!("u16: 3! = {}", factorial(3_u16));
println!("u32: 3! = {}", factorial(3_u32));
println!("u64: 3! = {}", factorial(3_u64));
}
Analyzing generated code🔗
Rust monomorphizes generic functions, which means a new function is created for each type.
This means rustc can optimize each instantiated function independently.
Below we can see the symbols for the four factorial functions (for each type) and the main function.
$ nm target/release/factorial-generic-analysis | grep factorial --color=always | sort
0000000000005e90 t _ZN26factorial_generic_analysis9factorial17h771813924a71f57dE
0000000000005ed0 t _ZN26factorial_generic_analysis9factorial17h9049e4d7daf7ac87E
0000000000005f80 t _ZN26factorial_generic_analysis9factorial17h92280da431f06ddaE
00000000000062b0 t _ZN26factorial_generic_analysis9factorial17had561ff9f2a266a5E
00000000000062f0 t _ZN26factorial_generic_analysis4main17h5d9c70811fce980bE
Below, we can see factorial::<u16>():
$ objdump -d target/release/factorial-generic-analysis
...
0000000000005e90 <_ZN26factorial_generic_analysis9factorial17h771813924a71f57dE>:
5e90: ff c7 inc %edi
5e92: 66 b8 01 00 mov $0x1,%ax
5e96: 0f b7 cf movzwl %di,%ecx
5e99: 83 f9 02 cmp $0x2,%ecx
5e9c: 72 28 jb 5ec6 <_ZN26factorial_generic_analysis9factorial17h771813924a71f57dE+0x36>
5e9e: 66 b9 02 00 mov $0x2,%cx
5ea2: 66 ba 01 00 mov $0x1,%dx
5ea6: 66 b8 01 00 mov $0x1,%ax
5eaa: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)
5eb0: 0f af c2 imul %edx,%eax
5eb3: 66 39 f9 cmp %di,%cx
5eb6: 89 ce mov %ecx,%esi
5eb8: 83 d6 00 adc $0x0,%esi
5ebb: 66 39 f9 cmp %di,%cx
5ebe: 66 89 ca mov %cx,%dx
5ec1: 66 89 f1 mov %si,%cx
5ec4: 72 ea jb 5eb0 <_ZN26factorial_generic_analysis9factorial17h771813924a71f57dE+0x20>
5ec6: c3 retq
5ec7: 66 0f 1f 84 00 00 00 nopw 0x0(%rax,%rax,1)
5ece: 00 00
...
Conclusion🔗
With the num crate, we can write stable, safe Rust code that is generic over various integer types.
Thanks to Gulshan Singh for reviewing this post.
Comments on Reddit