Tech Interview II

To get the feel for what we are working with let’s look at the first few powers of the update matrix:

$$\begin{align} & \begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} & \begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} & \begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} & \begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} & \cdots{} \\ \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix} & \begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix} & \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ \end{bmatrix} & \begin{bmatrix} 1 & 2 \\ 2 & 3 \\ \end{bmatrix} & \begin{bmatrix} 2 & 3 \\ 3 & 5 \\ \end{bmatrix} & \cdots{} \\ \end{align}$$

This seems to suggest that each element of the sequence is of form

$$\begin{bmatrix} a & b \\ b & a+b \\ \end{bmatrix}$$

For things to work we need e and f such that

$$\begin{bmatrix} a & b \\ b & a+b \\ \end{bmatrix} \begin{bmatrix} c & d \\ d & c+d \\ \end{bmatrix} = \begin{bmatrix} e & f \\ f & e+f \\ \end{bmatrix}$$

Which is indeed the case for

$$\begin{align} e & = ac + bd \\ f & = ad + bc + bd \\ \end{align}$$

This not only shows that we can reduce the original matrices to just tuples, but it also tells us how to combine them! And based on the way we constructed the operation it is trivially associative too. Giving us a semigroup. And while the identity matrix has a corresponding representation in our new structure making it a monoid, we don’t need it now. Cherry on top? Haskell’s Semigroup class has method stimes that does what we need, and the default implementation does it the way that we want!

data Fib a = F !a !a deriving Show

un (F x _) = x

instance Num a => Semigroup (Fib a) where
    F a b <> F c d = F (a*c + bd) (a*d+b*c+bd)
      where bd = b*d

fib = un . flip stimes (F 0 1) . succ

(Except for strictness, but if you’d want me to add that I’d just end up copy-pasting that code and sprinkling in some exclamation marks.)

I know what you want to say 🤔. This way we do 4 multiplications and 3 additions, but we know that multiplications are more expensive. Can we do any better? I think we can:

$$\begin{align} e & = ac + bd \\ f & = (a+b)(c+d) - ac \\ \end{align}$$

This way we do 3 multiplications and 4 “additive” operations, except now we need minus on the underlying numeric types.

Well, we just need a remainder after division by 100. And because mod is a homomorphism, we can carry out the whole calculation (`mod` 100).

Then that would be (`mod` 16^3).

Depends. Please don’t make me do that without a computer and documentation 🥺.

Pretty sweet. Now we can do fib 10000 :: Mod Int 100 and get something like 75 (mod 100). And it seems like the compiler might be able to be smart enough to calculate modulus only once 🤔. I quite like it, but it is usable only if we know modulus at compile time or for playing on the command line. Also your implementation of negate and minus are problematic 👀. For example running signum (negate 0) :: Mod Int 3 and 3 - 5 :: Mod Natural 10 will both break things. Would you like me to fix those?

One of them is (more) finite. But that means, that the step endomorphism \(a,b) -> (b,a+b) will start looping at some point! So if we knew where the loop starts and how big it is, we could calculate the n-th Fibonacci number in time completely independent of the n itself! But cycle detection could eat a lot of memory and testing against all the elements we visited can also add up quickly…

Well that would make it an isomorphism (automorphism?), which means there are no “tails” and it generates a cycle, so we know we would get back to the starting point of (0,1)! So no need to remember all the visited elements!

But is it? Let’s try (c,d) -> (d-c,c). For (e,f) after applying the step we get (f,e+f), and applying the proposed inverse step we get (e+f-f,f) = (e,f). So it is invertible!

No.

How can we make it work with the logarithmic version? Does it even make sense (we are already log, sooo log would need to be bigger than length of loop… still pretty cool…)