How can I implement this Fibonacci algorithm using a generic integer type?-CodePudding

I have the following code which, when given a number n, calculates the nth Fibonacci number.

pub fn fibonacci(n: i64) -> i64 {
   fib_iter(1, 0, 0, 1, n)
}


fn fib_iter(a: i64, b: i64, p: i64, q: i64, count: i64) -> i64 {
   if count == 0 {
      return b;
   }

   if is_even(count) {
      return fib_iter(a, b, p*p   q*q, 2*p*q   q*q, count / 2);
   }

   fib_iter(b*q   a*q   a*p, b*p   a*q, p, q, count - 1)
}

The problem is it only works for i64 while I would like it to be generic, so it works for any integral type.

I tried using the Integer trait from the num crate to make it generic:

pub fn fibonacci<T: Integer>(n: T) -> T {
   fib_iter(1, 0, 0, 1, n)
}

fn fib_iter<T: Integer>(a: T, b: T, p: T, q: T, count: T) -> T {
   if count.is_zero() {
      return b;
   }

   if count.is_even() {
      return fib_iter(a, b, p*p   q*q, 2*p*q   q*q, count / 2);
   }

   fib_iter(b*q   a*q   a*p, b*p   a*q, p, q, count - 1)
}

But it doesn't like the use of any integer literals, for example:


66 |       return fib_iter(a, b, p*p   q*q, 2*p*q   q*q, count / 2);
   |                                         ^ no implementation for `{integer} * T`

...


69 |    fib_iter(b*q   a*q   a*p, b*p   a*q, p, q, count - 1)
   |                                                       ^ expected type parameter `T`, found integer

I also tried doing something like the following:

let two: T = 2;

But same problem. And same if I try using traits Mul, Div, Add, Sub etc.

CodePudding user response：

Here is a way to use num_traits to implement this:


use num_traits::identities::{One, Zero};
use std::cmp::PartialEq;
use std::fmt::{Debug, Display};
use std::ops::Add;
use std::ops::BitAnd;
use std::ops::Mul;
use std::ops::Shl;
use std::ops::Shr;
use std::ops::Sub;

pub fn fibonacci<T>(n: T) -> T
where
    T: Add
          Mul
          Sub
          One
          Zero
          Shl
          Shr
          Copy
          Shl<Output = T>
          Shr<Output = T>
          PartialEq
          BitAnd
          Sub<Output = T>
          Debug
          Display,
    <T as Shl>::Output: Add<T>,
    <T as BitAnd>::Output: PartialEq<T>,
{
    fib_iter(T::one(), T::zero(), T::zero(), T::one(), n)
}

fn fib_iter<T>(a: T, b: T, p: T, q: T, count: T) -> T
where
    T: Add
          Mul
          One
          Sub
          Zero
          Shl
          Shr
          Copy
          Shl<Output = T>
          Shr<Output = T>
          PartialEq
          BitAnd
          Sub<Output = T>
          Debug
          Display,
    <T as Shl>::Output: Add<T>,
    <T as BitAnd>::Output: PartialEq<T>,
{
    if count == T::zero() {
         return b;
    }


    // If even
    if count & T::one() == T::zero() {
        let p2 = p * p;
        let q2 = q * q;
        let pq_x2 = (p * q) << T::one();
        return fib_iter(a, b, p2   q2, pq_x2   q2, count >> T::one());
    }

    let ap = a*p;
    let aq = a*q;
    let bp = b*p;
    let bq = b*q;

    fib_iter(bq   aq   ap, bp   aq, p, q, count - T::one())
}

fn main() {
    eprintln!("{}", fibonacci(100 as u128));
}

Rust Playground

GIST

CodePudding user response：

You can use T::one() and T::zero() to get 1 and 0. Other numbers can either be worked around (e.g. 2*x → x x) or obtained from 1 (e.g. 2 is T::one() T::one()). You will also need to add a T: Copy bound if you want to be able to reuse the same number more than once:

use num::Integer;

pub fn fibonacci<T: Integer   Copy>(n: T) -> T {
   fib_iter(T::one(), T::zero(), T::zero(), T::one(), n)
}

fn fib_iter<T: Integer   Copy>(a: T, b: T, p: T, q: T, count: T) -> T {
   if count.is_zero() {
      return b;
   }

   if count.is_even() {
      return fib_iter(a, b, p*p   q*q, p*q   p*q   q*q, count / (T::one()   T::one()));
   }

   fib_iter(b*q   a*q   a*p, b*p   a*q, p, q, count - T::one())
}

Playground