More Efficient Recursive Tetranacci function in F#

user_10327184 0
Viewed 313

I am trying to write a tetranacci function using F# as efficiently as possible the first solution I came up with was really inefficient. can you help me come up with a better one? How would i be able to implement this in linear time? 

let rec tetra n =
 match n with
 | 0 -> 0
 | 1 -> 1
 | 2 -> 1
 | 3 -> 2
 | _ -> tetra (n - 1) + tetra (n - 2) + tetra (n - 3) + tetra (n - 4)
f#-3.0 c#-to-f# fibonacci time-complexity f#
3 Answers

You could economise by devising a function that computes the state for the next iteration on a 4-tuple. Then the sequence generator function Seq.unfold can be used to build a sequence that contains the first element of each state quadruple, an operation that is 'lazy` -- the elements of the sequence are only computed on demand as they are consumed.

let tetranacci (a3, a2, a1, a0) = a2, a1, a0, a3 + a2 + a1 + a0
(0, 1, 1, 2) 
|> Seq.unfold (fun (a3, _, _, _ as a30) -> Some(a3, tetranacci a30))
|> Seq.take 10
|> Seq.toList
// val it : int list = [0; 1; 1; 2; 4; 8; 15; 29; 56; 108]

Note that the standard Tetranacci sequence (OEIS A000078) would usually be generated with the start state of (0, 0, 0, 1):

// val it : int list = [0; 0; 0; 1; 1; 2; 4; 8; 15; 29]
user_28071300

kaefer's answer is good, but why stop at linear time? It turns out that you can actually achieve logarithmic time instead, by noting that the recurrence can be expressed as a matrix multiplication:

[T_n+1]   [0; 1; 0; 0][T_n]
[T_n+2] = [0; 0; 1; 0][T_n+1]
[T_n+3]   [0; 0; 0; 1][T_n+2]
[T_n+4]   [1; 1; 1; 1][T_n+3]

But then T_n can be achieved by applying the recurrence n times, which we can see as the first entry of M^n*[T_0; T_1; T_2; T_3] (which is just the upper right entry of M^n), and we can perform the matrix multiplication in O(log n) time by repeated squaring:

type Mat =
| Mat of bigint[][]
    static member (*)(Mat arr1, Mat arr2) =
        Array.init arr1.Length (fun i -> Array.init arr2.[0].Length (fun j -> Array.sum [| for k in 0 .. arr2.Length - 1 -> arr1.[i].[k]*arr2.[k].[j] |]))
        |> Mat

    static member Pow(m, n) =
        match n with
        | 0 -> 
            let (Mat arr) = m
            Array.init arr.Length (fun i -> Array.init arr.Length (fun j -> if i = j then 1I else 0I))
            |> Mat
        | 1 -> m
        | _ ->
            let m2 = m ** (n/2)
            if n % 2 = 0 then m2 * m2
            else m2 * m2 * m

let tetr =
    let m = Mat [| [|0I; 1I; 0I; 0I|]
                   [|0I; 0I; 1I; 0I|]
                   [|0I; 0I; 0I; 1I|]
                   [|1I; 1I; 1I; 1I|]|]
    fun n -> 
        let (Mat m') = m ** n
        m'.[0].[3]

for i in 0 .. 50 do
    printfn "%A" (tetr i)
kvb_829590

Here is a tail recursive version, which compiles to mostly loops (and its complexity should be O(n)):

let tetr n =
  let rec t acc4 acc3 acc2 acc1 = function
    | n when n = 0 -> acc4
    | n when n = 1 -> acc3
    | n when n = 2 -> acc2
    | n when n = 3 -> acc1
    | n -> t acc3 acc2 acc1 (acc1 + acc2 + acc3 + acc4) (n - 1)
  t 0 1 1 2 n

acc1 corresponds to tetra (n - 1), acc2 corresponds to tetra (n - 2), acc3 corresponds to tetra (n - 3), acc4 corresponds to tetra (n - 4)

Based on the Fibonacci example

user_15021480
Related