fibonacci_like/lib.rs
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239
#![warn(missing_docs)]
#![cfg_attr(not(feature = "std"), no_std)]
#![doc = include_str!("../README.md")]
/// An error for when the given input could not be found in the sequence
#[derive(Debug)]
pub enum FindError {
/// The input was not found in the sequence
NotFound(Number),
}
impl core::fmt::Display for FindError {
fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
match self {
FindError::NotFound(number) => {
write!(f, "The number `{}` was not found in the sequence", number)
}
}
}
}
#[cfg(feature = "std")]
impl std::error::Error for FindError {}
type FindResult<T> = Result<T, FindError>;
/// The into_number trait
///
/// See [`Number`] for more information.
pub trait IntoNumber {
/// Converts the given value into a [`Number`] type
fn into_number(self) -> Number;
}
/// The number return type
///
/// Will be either [`num_bigint::BigInt`] or [`i128`] based on whether the `big-int` feature is enabled or not
#[cfg(feature = "big-int")]
pub type Number = num_bigint::BigInt;
/// The number return type
///
/// Will be either [`num_bigint::BigInt`] or [`i128`] based on whether the `big-int` feature is enabled or not
#[cfg(not(feature = "big-int"))]
pub type Number = i128;
impl IntoNumber for i128 {
fn into_number(self) -> Number {
cfg_if::cfg_if! {
if #[cfg(feature = "big-int")] {
use num_bigint::ToBigInt;
self.to_bigint().unwrap()
} else {
self
}
}
}
}
fn update_array(numbers: &mut [Number; 2]) {
let old_x = &numbers[0];
let old_y = &numbers[1];
let new_y = old_x + old_y;
// Removes the need to clone if we add 0
numbers[0] = old_y + 0;
numbers[1] = new_y;
}
/// A sequence, represented by the two starting values, which are later used to compute further values
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Sequence(pub Number, pub Number);
impl Sequence {
/// Creates a new sequence with the given starting values
///
/// # Examples
///
/// ```
/// # use fibonacci_like::Sequence;
/// Sequence::new([1,1]);
/// ```
pub fn new(sequence: impl Into<Self>) -> Self {
sequence.into()
}
/// Returns the fibonacci sequence, represented as a [`Sequence`] struct
///
/// # Examples
///
/// ```
/// # use fibonacci_like::Sequence;
/// let sequence = Sequence::new([1, 1]);
/// let fib_sequence = Sequence::fibonacci();
///
/// assert_eq!(sequence, fib_sequence);
/// ```
pub fn fibonacci() -> Self {
Self::new([1, 1])
}
/// Calculate the nth term of the sequence
///
/// # Examples
///
/// ```
/// # use fibonacci_like::{Sequence, IntoNumber};
/// let sequence = Sequence::fibonacci();
/// let nth_term = sequence.calculate(3);
///
/// assert_eq!(nth_term, 2_i128.into_number());
/// ```
pub fn calculate(self, n: usize) -> Number {
let mut numbers = [self.0, self.1];
for _ in 2..n {
update_array(&mut numbers);
}
cfg_if::cfg_if! {
if #[cfg(feature = "big-int")] {
use num_bigint::ToBigInt;
numbers[1].to_bigint().unwrap()
} else {
numbers[1]
}
}
}
/// Find the given number's position in the sequence
///
/// # Examples
///
/// ```
/// # use fibonacci_like::{Sequence, IntoNumber};
/// let fifteenth = 610.into_number();
///
/// let fib = Sequence::fibonacci();
///
/// assert_eq!(fib.find(fifteenth).unwrap(), 15);
/// ```
pub fn find(self, number: Number) -> FindResult<usize> {
let mut numbers = [self.0, self.1];
if number == numbers[0] {
return Ok(1);
} else if number == numbers[1] {
return Ok(2);
}
let mut n = 2;
loop {
update_array(&mut numbers);
n += 1;
if numbers[1] > number {
break Err(FindError::NotFound(number));
}
if numbers[1] == number {
break Ok(n);
}
}
}
}
impl From<[i128; 2]> for Sequence {
fn from(array: [i128; 2]) -> Sequence {
Sequence(array[0].into_number(), array[1].into_number())
}
}
#[cfg(test)]
mod tests {
cfg_if::cfg_if! {
if #[cfg(feature = "big-int")] {
use num_bigint::BigInt;
use std::str::FromStr;
}
}
use super::*;
// This test does not work without big-int as the literal is too large to fit in i128
#[cfg(feature = "big-int")]
#[test]
fn test_get_500th() {
let nth500 = BigInt::from_str("139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125").unwrap();
let fib = Sequence::fibonacci();
assert_eq!(fib.calculate(500), nth500);
}
#[test]
fn test_get_first() {
let first = 1.into_number();
let fib = Sequence::fibonacci();
assert_eq!(fib.calculate(1), first);
}
#[test]
fn test_get_third() {
let third = 2.into_number();
let fib = Sequence::fibonacci();
assert_eq!(fib.calculate(3), third);
}
#[test]
fn test_find_first() {
let first = 1.into_number();
let fib = Sequence::fibonacci();
assert_eq!(fib.find(first).unwrap(), 1);
}
#[test]
fn test_find_third() {
let third = 2.into_number();
let fib = Sequence::fibonacci();
assert_eq!(fib.find(third).unwrap(), 3);
}
#[test]
fn test_find_fifteenth() {
let fifteenth = 610.into_number();
let fib = Sequence::fibonacci();
assert_eq!(fib.find(fifteenth).unwrap(), 15);
}
}