Fibonacci sequences of higher order : The Nibonacci Sequence

-
So today I was messing around with optimising the calculation of Fibonacci sequences. Everyone has written code like this
Quickly we run into performance issues because many of the calculations are redundant, and these redundant repeated duplicate calculations result in massive function stacks. So the obvious solution here is to cache the intermediate results. We can do something like this

I wanted to create a Fibonacci sequence of order N  (Or Nibonacci sequence) using these same principles. First we need a cache that will store the N previous Nibonacci numbers. I designed this data structure, and I think it fits the bill:

Glorious right? This is essentially a circular buffer, and it will work as expected in the previous example when substituted appropriately. We could have used a std::vector, but we would then have to defer the generation of our cache to runtime and, more importantly, we would be storing unnecessary results (our memory requirements would increase with the size of the Nibonacci number, instead of the order N). Now let us consider using this to find the Tribonacci numbers:

We can wrap the latest_cache data structure inside a class and obtain something like
We can use it as follows to get Fibonacci, Tribonacci and Decibonacci sequences

Just a quickie today :)
Yours sincerely, Joey Tribonacci

Comments

Post a Comment

Popular posts from this blog

Using the AVX instruction set to boost performance

-
Image
The AVX instruction set uses CPU registers to perform SIMD (Single Instruction Multiple Data) operations, which can be used to significantly speed up mathematical operations. I recently decided to create a digital filter in C++, and starting with the basics I came across a Finite Impulse Response (FIR) filter. Mathematically a FIR filter outputs a weighted sum of the most recent input values of the signal. The mathematics of a FIR filter are outlined  here . In practice, we typically work on sections of a signal. This is quite simply because we can not hold the entire signal in RAM. Consider the following signal which has been split into three chunks each of size 6,                                                        $$ [012123][123332][123342] $$ and the following filter $b = [1,2]$. In the routines discussed in this blog the a...
Read more

The magic behind deep learning : Obtaining gradients using reverse Automatic Differentiation.

-
Image
Every now and again a wave of rage washes over me when I hear someone (be it a news outlet, etc) refer to deep learning, and the like, as magic. Although, I must admit that I was a bit vague on how you can generate an error function given a network of nodes then minimise it without using numerical differentiation or providing the actual derivative (Although there are (totally) derivative-free minimisation methods such as Simplex etc.). The process of writing software for generating this error function (and a neural network) is not of my concern here, although it might be in a future blog post. What is of my concern is obtaining the gradient of this error function. Automatic Differentiation  First, lets discuss the process of obtaining the derivative of a expression that we already have the computation graph for . You will see that obtaining the computation graph is half the battle and many of the resources on the internet explaining Automatic Differentiation (AD) tend to brus...
Read more

Information Entropy

-
In the field of Information Theory, we can define the information conveyed $I(E)$ by the occurrence of an event $E$ as $$I(E) = \log \frac{1}{p(E)},$$ where $p(E)$ is the probability of the event $E$. Note that if the event is unlikely then the information gained is large. Suppose that we have an information source $X$, which can be thought of as a discrete random variable. $X$ can take on many "states" $\{x_i\}$. We can define the entropy of the system as $$H(X) = \sum_i^n  p(x_i)I(x_i),$$ where $n$ is the number of states that $X$ can take. An example of $X$ is an alphabet. A qualitative description of the entropy of an information source is a measure of its unpredictability. We can see this by observing the following: If the probabilities of the states of the source are uniform the entropy is maximised. That is, when we have no prior information about the likelihood of each state we expect the entropy of the information source to be large. We can prove this f...
Read more