DEV Community: Benjamin Lehmann

Binet's Formula for Fibonacci Numbers and Where it Comes From

Benjamin Lehmann — Tue, 09 Jan 2024 05:30:02 +0000

This article was originally published here

Prologue

If you’re like me, you may be a little jaded towards the Golden Ratio and the Fibonacci numbers. If you aren’t already, I invite you to search YouTube for videos related to either topic — I had a look and I was suggested a video entitled “The Golden Ratio - Transmuted Pain to Power in Infinite Divine Proportion”. Suffice it to say, there’s a lot of garbage out there.

The Golden Ratio was familiar to the Greeks, and much of its allure comes from Greek philosopher’s obsession with the number. An allure that is evermore powerful today, as all three Abrahamic religions were greatly influenced by Greek philosophy, especially by the Neoplatonists. Unfortunately, while I’m sure it is possible to have an enlightening discussion about the role of the Golden Ratio in Greek philosophy and religion, much of the content concerning Phi makes a mockery of both philosophy and theology. To say nothing of mathematics.

That means that this article is not for you if you’re here because you expected me to tell you how to cure cancer by using 1.618 cups of flour instead of 1.5. Instead, I’d like to take a poke at why the Golden Ratio and the Fibonacci Numbers are related in the first place, while also making a short review piece for those studying linear algebra.

The Math

You may be familiar with the Binet formula for the Fibonacci numbers:

If not, you should watch this video, it's really quite a nice exploration of the formula.

But where does this formula come from? Well, it comes from observing that we can recontextualize the familiar Fibonacci series in matrix form:

This version is quite simple, but it's also quite uninteresting. However, if one adds another row to our matrix we will have a square matrix A, which unlocks a great many tools of linear algebra. Our second row will simply compute the previous Fibonacci number:

This is nice and all, but we want a more efficient way to compute this, not just a more mathy way. Fortunately, we can have both; we'll start by finding the eigenvalues of this matrix, which are the roots of the characteristic polynomial:

This has roots of 1 ± √5, which we typically write as φ and -(φ)^-1. The corresponding eigenvectors are non-zero solutions to (A− λI)x = 0 for an eigenvalue λ.

We find the eigenvector associated with λ = φ by row-reduction on the following matrix:

Which is row-equivalent to:

This matrix encodes a system with the following solution set:

Therefore an eigenvector associated with λ = φ is ⟨φ,1⟩. Similarly, an eigenvector associated with the other eigenvalue is ⟨−φ^−1,1⟩.
These choices are not unique, we could've chosen any of the infinite parallel vectors (except for the zero vector).

As we have two eigenvectors from different eigenspaces (i.e. are associated with different eigenvalues) we know they are linearly independent, and thus form a basis of ℝ^2. The vector ⟨1,0⟩ is thus necessarily a linear combination of this eigenbasis:

Therefore, if we multiply by A we only need to multiply each coefficient by the respective eigenvalue:

And if we multiply by A^n:

This lets us create a closed-form expression by solving for F_n which if you recall is the second element in our vector:

And so there we have it, we've derived Binet's formula.

SkiaSharp: Unmasking with SKColorFilter

Benjamin Lehmann — Mon, 07 Nov 2022 00:52:31 +0000

This article was originally published here

In my last post, we created a shader that tiled a bitmap across the filled area. In this post, we're going to change that bitmap to be a black-and-white mask, and use a color filter to change the color on the fly.

Our CreateBitmap method doesn't change much, we simply hardcode the colours to black and white:

private static SKBitmap CreateBitmap()
{
  var bitmap = new SKBitmap(20, 50);

  using var paint = new SKPaint() { Color = SKColors.White };
  using var path = new SKPath();
  using var canvas = new SKCanvas(bitmap);

  canvas.Clear(SKColors.Black);
  canvas.DrawRect(new SKRect(0, 0, 20, 20), paint);

  return bitmap;
}

public readonly static SKBitmap Bitmap = CreateBitmap();

Since this function will always return the same thing, we cache the result, which, rather predictably, looks the same but with the colours swapped:

Now, how do we map white to our hatch colour, and black to our background colour? The key is SKShader.WithColorFilter, which will allow us to remap black and white to blue and red.

There are two main ways to create such an SKColorFilter. There's a function SKColorFilter.CreateTable that takes four byte[256] arrays, which are interpreted as lookup tables for the A, R, G, and B channels respectively. For each colour c in the image, it applies this function:

c.A = alphaLookup[c.A]
c.R = redLookup[c.R]
c.G = greenLookup[c.G]
c.B = blueLookup[c.B]

Since our image only has two colours (black and white), you only need to set index 0 and index 255. For our purposes, this is a little wasteful, as it means allocating a kilobyte for what is a relatively simple filter. Unfortunately, be it out of concern for performance, or out of heretofore unknown masochism, I did not go with this option, I hope this was a good enough head start if you're interested.

The second way is to create a 4x5 matrix that all colours in our image will be multiplied by. I used to be a math minor, so I got a little overenthusiastic here. If you want to skip all the math you can jump to the bottom to see the code.

The Math (copy-pastable code below)

From this article in the Xamarmin docs, the matrix looks like this:

The formulas for each channel are as follows:

This matrix can encode an arbitrary affine transformation (i.e. any linear transformation, with the addition of translation). That's why we have a five-dimensional colour, and it's why the matrix has five columns, so we can encode translations as well.

However, we only care what this matrix does to two colours, black and white, which we'll denote the vectors $[0, 0, 0, 0, 1]$ and $[1, 1, 1, 1, 1]$ respectively. So we're going to create a matrix that maps these vectors to our hatchColor and backgroundColor, which has the geometric interpretation of placing every shade of gray onto a line between hatchColor and backgroundColor. Please note that black is actually the vector $[0, 0, 0, 1, 1]$ , and we'll correct our result at the end to account for the alpha channel.

We can start by translating all colours by the background colour $bg\textbf{bg}$ . This maps black to $bg\textbf{bg}$ , regardless of what the rest of the matrix looks like, as multiplying by the vector $[0, 0, 0, 0, 1]$ simply extracts the last column:

Now, we're going to define a vector $diff=hatch−bg\textbf{diff} = \textbf{hatch}- \textbf{bg}$ . This vector will form the main diagonal of our matrix, the rest of which will be zero:

You may notice that, save for the last column, this is a diagonal matrix (aka a scaling matrix). Multiplying by a diagonal matrix is equivalent to multiplying the first component of the vector by the first element of the matrix's diagonal, the second component by second element of the diagonal, and so on. That is to say:

We can write this pairwise multiplication more concisely as $c′=c⊙diff\textbf{c}' = \textbf{c} ⊙ \textbf{diff}$

Crucially, since the colour white is represented by the vector $[1, 1, 1, 1, 1]$ , white maps to $diff+bg\textbf{diff} + \textbf{bg}$ . Since $diff=hatch−bg\textbf{diff} = \textbf{hatch} - \textbf{bg}$ , white maps to $hatch\textbf{hatch}$ .

Now we have a matrix that maps black to the background colour and white to the hatch colour, but our alpha channel is incorrect. We pretended that black was $[0, 0, 0, 0, 1]$ , but it's actually $[0, 0, 0, 1, 1]$ . This means that the alpha of the background colour will be the same as the alpha channel of the hatch colour. We can fix this by placing the coefficient for the alpha channel in a different column (for example red) of the matrix:

Which changes the alpha channel so that:

We could've placed it in the blue or green channels as well, the only important part is it must be a channel that is 0 in the colour black, but 1 in the colour white. I also made another simplifying assumption, namely that colour channels are on the interval $[0, 1]$ rather than $[0, 255]$ . This is not true, so we also have to divide our matrix by 255 when we write our code.

SKColorFilter implementation

The code looks like this, note that I used foreground in place of hatchColor

public static SKColorFilter GetMaskColorFilter(SKColor foreground, SKColor background)
{
  float redDifference = foreground.Red - background.Red;
  float greenDifference = foreground.Green - background.Green;
  float blueDifference = foreground.Blue - background.Blue;
  float alphaDifference = foreground.Alpha - background.Alpha;

  var mat = new float[] {
    redDifference / 255, 0, 0, 0, background.Red / 255.0f,
    0, greenDifference / 255, 0, 0, background.Green / 255.0f,
    0, 0, blueDifference / 255, 0, background.Blue / 255.0f,
    0, 0, 0, alphaDifference / 255, background.Alpha / 255.0f,
  };

  return SKColorFilter.CreateColorMatrix(mat);
}

Now, to actually use this colour filter, GetShader becomes the following:

public static SKShader GetShader(SKColor hatchColor, SKColor backgroundColor, StripeDirection stripeDirection = StripeDirection.Horizontal)
{
  var rotationMatrix = stripeDirection switch
  {
    StripeDirection.DiagonalUp => SKMatrix.CreateRotationDegrees(-45),
    StripeDirection.DiagonalDown => SKMatrix.CreateRotationDegrees(45),
    StripeDirection.Horizontal => SKMatrix.Identity,
    StripeDirection.Vertical => SKMatrix.CreateRotationDegrees(90),
    _ => throw new NotImplementedException(nameof(StripeDirection))
  };

  var shader = SKShader.CreateBitmap(
    Bitmap,
    SKShaderTileMode.Repeat,
    SKShaderTileMode.Repeat,
    SKMatrix.CreateScale(0.25f, 0.25f)
      .PostConcat(rotationMatrix));

  return shader.WithColorFilter(ColorFilterHelpers.GetMaskColorFilter(hatchColor, backgroundColor));
}

And this code gives the correct result for a hatch colour of red, and a background colour of blue:

SkiaSharp: Hatched fills with SKShader

Benjamin Lehmann — Mon, 07 Nov 2022 00:29:11 +0000

This article was originally published here

Coming from System.Drawing.Common, one of the things I missed most about SkiaSharp was the lack of support for hatched fills out of the box. If you're unfamiliar, hatching allows you to paint with a pattern applied (source: ScottPlot 4.1 docs).

In SkiaSharp, you have two options:

If you want very simple results, SKPathEffect may be appropriate, but I would not recommend it for interactive or real-time rendering. SKShader isn't much harder to implement, and SKPathEffect has significantly poorer performance, especially if the hatched area takes up large portions of the screen. The same zoom level could yield ~10 FPS with SKPathEffect, and ~300 FPS with shaders.

Additionally, SKPathEffect has some further drawbacks. If you draw a circle with SKPathEffect, the effect will bleed over significantly. And SKPathEffect will not tile up to the edges of the circle, yielding poor-looking results. These can be countered by clipping and shrinking the tiling unit respectively, but for my purposes it wasn't worth it. Especially as reducing the size of each tile further exacerbates the performance problems. The rest of this post will be completely focused on SKShader.

SKShader

So, you've decided to use SKShader? Despite the name, it's really not too hard to use, you don't have to (and to my knowledge, cannot) write shaders from scratch in SkiaSharp. Instead, we're going to create a small bitmap, and use SKShader.CreateBitmap to create a shader that tiles it across the fill.

For a striped hatch, the code to create the bitmap looks like this:

public static SKBitmap CreateBitmap(SKColor hatchColor, SKColor backgroundColor)
{
  var bitmap = new SKBitmap(20, 50);

  using var paint = new SKPaint() { Color = hatchColor };
  using var path = new SKPath();
  using var canvas = new SKCanvas(bitmap);

  canvas.Clear(backgroundColor);
  canvas.DrawRect(new SKRect(0, 0, 20, 20), paint);

  return bitmap;
}

And the bitmap itself is simply CreateBitmap(SKColors.Red, SKColors.Blue):

Doesn't look like much, does it? In any case, it's enough to create a striped pattern. Now we have to create a shader:

public static SKShader GetShader(SKColor hatchColor, SKColor backgroundColor)
{
  return SKShader.CreateBitmap(
    CreateBitmap(hatchColor, backgroundColor),
    SKShaderTileMode.Repeat,
    SKShaderTileMode.Repeat,
    SKMatrix.CreateScale(0.25f, 0.25f));
}

Now, if we use this shader to paint a square:

var shader = GetShader(SKColors.Red, SKColors.Blue);
using var bmp = new SKBitmap(128, 128);
using var canvas = new SKCanvas(bmp);
using var paint = new SKPaint()
{
  Shader = shader
};

canvas.DrawRect(new(0, 0, 128, 128), paint);
WriteBitmapToFile(bmp, "hatch.png"); // This function is included in the github link at the bottom

Note that the 2nd and 3rd parameters set the tiling mode for the x and y directions respectively. In our case, we want it to repeat, but if you want it to mirror or clamp in one direction you can. Clamping in this context means displaying the image once and stretching the last pixel to the edge of the fill area.

The last parameter is for applying a transformation to the shader. For now, we just want to rescale it, but next we'll use it for rotations.

Rotating the shader

Now, what if you want vertical or diagonal stripes? You could rotate the bitmap, but it's simpler to rotate the shader. That way, you can reuse the same bitmap for different rotations.

Since the last parameter to SKShader.CreateBitmap was a transformation matrix, we can simply multiply by our desired rotation matrix to get what we want:

public static SKShader GetShader(SKColor hatchColor, SKColor backgroundColor, StripeDirection stripeDirection = StripeDirection.Horizontal)
{
  var rotationMatrix = stripeDirection switch
  {
    StripeDirection.DiagonalUp => SKMatrix.CreateRotationDegrees(-45),
    StripeDirection.DiagonalDown => SKMatrix.CreateRotationDegrees(45),
    StripeDirection.Horizontal => SKMatrix.Identity,
    StripeDirection.Vertical => SKMatrix.CreateRotationDegrees(90),
    _ => throw new NotImplementedException(nameof(StripeDirection))
  };

  return SKShader.CreateBitmap(
    CreateBitmap(hatchColor, backgroundColor),
    SKShaderTileMode.Repeat,
    SKShaderTileMode.Repeat,
    SKMatrix.CreateScale(0.25f, 0.25f)
      .PostConcat(rotationMatrix));
}

Now, if we call GetShader with StripeDirection.DiagonalUp, we get this result instead:

A quick note on the transformation matrix, when you call A.PostConcat(B) it represents this matrix multiplication A * B. These matrices represent a linear transformation, but matrix multiplication is not commutative, so the order matters. Unintuitively, the multiplication A * B corresponds to B(A(x)), not A(B(x)).

So while our code might look like it scales the shader followed by a rotation, it actually rotates and then scales. In this case, it doesn't make a difference, but it's worth noting in case you get up to anything more complicated.

Using a mask and colour filter

For most people's purposes, this is as far as they need to go. But if you're astute, you may have noticed that we baked the colours (in our case red and blue) into the bitmap. What if we need to be able to provide the same pattern with multiple colour palettes, do we have to regenerate the bitmap each time? Or do we have to write extra code to invalidate the bitmap should the colours change?

Instead, we can store the bitmaps as black and white, and then add the colour later. Then we can cache these bitmaps without ever needing to invalidate them. Seeing as they're so small, you could even bundle them with your distribution, should you be so inclined.

This is covered in this post.

DEV Community: Benjamin Lehmann

Binet's Formula for Fibonacci Numbers and Where it Comes From

Prologue

The Math

SkiaSharp: Unmasking with SKColorFilter

The Math (copy-pastable code below)

SKColorFilter implementation

Links

SkiaSharp: Hatched fills with SKShader

SKShader

Rotating the shader

Using a mask and colour filter

Links