EBCDIC, thou art evil.

November 18, 2020 Mainframe , , ,

Here’s a bit of innocuous code. It was being compiled with gcc -fexec-charset=1047, so all the characters and strings were being treated as EBCDIC. For example ‘0’ = ‘\xF0’.

    if (c >= '0' && c <= '9')                                                                                                         
         c -= '0';                                                                                                                    
    else if (c >= 'A' && c <= 'Z')                                                                                                    
         c -= 'A' - 10;                                                                                                               
    else if (c >= 'a' && c <= 'z')                                                                                                    
         c -= 'a' - 10;                                                                                                               
    else                                                                                                                              
         break;

Specifying the charset is not enough to port this code to the mainframe.  The problem is that EDCDIC is completely braindead, and DOESN’T PUT THE FRIGGEN LETTERS TOGETHER!

The letters are clustered in groups:

  • a-i
  • j-r
  • s-z
  • A-I
  • J-R
  • S-Z

with whole piles of crap between each range of characters, so comparisons like c >= ‘A’ && c <= ‘Z’ are useless, as are constructions like (c-‘A’-10) since c in J-R or S-Z will break that.

Now I have a big hunt and destroy task ahead of me.  I can fix this code, but where else are problems like this lurking!

Guessing the nth Fibonacci number formula

November 17, 2020 math and physics play , , , ,

[If mathjax doesn’t display properly for you, click here for a PDF of this post]

My last two posts:

  1. The nth term of a Fibonacci series.
  2. More on that cool Fibonacci formula.

were both about a cool formula for the n-th term of the Fibonacci series.  Looks like I’m not done playing with this beastie.  A recap:

Definition 1.1: Fibonacci series.

With \( F_0 = 0 \), and \( F_1 = 1 \), the nth term \( F_n \) in the Fibonacci series is the sum of the previous two terms
\begin{equation*}
F_n = F_{n-2} + F_{n-1}.
\end{equation*}

Theorem 1.1: Nth term of the Fibonacci series.

\begin{equation*}
F_n = \frac{ \lr{ 1 + \sqrt{5} }^n – \lr{ 1 – \sqrt{5} }^n }{ 2^n \sqrt{5} }.
\end{equation*}

 

The guess.

We can rearrange the formula for the nth Fibonacci number as a difference equation
\begin{equation}\label{eqn:fibonacci:260}
F_n – F_{n-1} = F_{n-2}.
\end{equation}
This is a second order difference equation, so my naive expectation is that there are two particular solutions involved. We know the answer, so it’s not too hard to guess that the particular form of the solution has the following form
\begin{equation}\label{eqn:fibonacci:280}
F_n = \alpha a^n + \beta b^n.
\end{equation}
Given this guess, can we take some of the magic out of the formula, by just solving for \( \alpha, \beta, a, b \)? Let’s try that
\begin{equation}\label{eqn:fibonacci:300}
F_0 = \alpha + \beta = 0,
\end{equation}
\begin{equation}\label{eqn:fibonacci:320}
\begin{aligned}
F_1 &= \alpha a + \beta b \\
&= \alpha \lr{ a – b } \\
&= 1,
\end{aligned}
\end{equation}
and
\begin{equation}\label{eqn:fibonacci:340}
\begin{aligned}
F_n
&= F_{n-1} + F_{n-2} \\
&=
\alpha \lr{ a^{n-1} + a^{n-2} }
-\alpha \lr{ b^{n-1} + b^{n-2} } \\
&=
\alpha a^{n-2} \lr{ 1 + a }
-\alpha b^{n-2} \lr{ 1 + b },
\end{aligned}
\end{equation}
so
\begin{equation}\label{eqn:fibonacci:360}
\begin{aligned}
a^2 &= a + 1 \\
b^2 &= b + 1.
\end{aligned}
\end{equation}
If we complete the square we find
\begin{equation}\label{eqn:fibonacci:380}
\lr{ a – \inv{2} }^2 = 1 + \inv{4} = \frac{5}{4},
\end{equation}
or
\begin{equation}\label{eqn:fibonacci:400}
a, b = \inv{2} \pm \frac{\sqrt{5}}{2}.
\end{equation}
Out pop the golden ratio and it’s complement. Clearly we need to pick alternate roots for \( a \) and \( b \) or else we’d have zero for every value of \( n > 0 \). Suppose we pick the positive root for \( a \), then to find the scaling constant \( \alpha \), we just compute
\begin{equation}\label{eqn:fibonacci:420}
\begin{aligned}
1
&=
\alpha \lr{ \frac{ 1 + \sqrt{5}}{2} – \frac{ 1 – \sqrt{5} }{2} } \\
&= \alpha \sqrt{5},
\end{aligned}
\end{equation}
so our system \ref{eqn:fibonacci:280} has the solution:
\begin{equation}\label{eqn:fibonacci:520}
\begin{aligned}
a &= \frac{1 + \sqrt{5}}{2} \\
b &= \frac{1 – \sqrt{5}}{2} \\
\alpha &= \inv{\sqrt{5}} \\
\beta &= -\inv{\sqrt{5}}.
\end{aligned}
\end{equation}

We now see a path that will systematically lead us from the Fibonacci difference equation to the final result, and have only to fill in a few missing steps to understand how this could be discovered from scratch.

Motivating the root-fives.

I showed this to Sofia, and she came up with a neat very direct way to motivate the \( \sqrt{5} \). It follows naturally (again knowing the answer), by assuming the Fibonacci formula has the following form:
\begin{equation}\label{eqn:fibonacci:440}
F_n = \inv{x} \lr{
\lr{ \frac{1 + x}{2}}^n
–
\lr{ \frac{1 – x}{2}}^n
}.
\end{equation}
We have only to plug in \( n = 3 \) to find
\begin{equation}\label{eqn:fibonacci:460}
\begin{aligned}
2 x
&= \inv{4} \lr{ 1 + 3 x + 3 x^2 + x^3 – \lr{ 1 – 3 x + 3 x^2 – x^3 } } \\
&= \inv{2} \lr{ 3 x + x^3 },
\end{aligned}
\end{equation}
or
\begin{equation}\label{eqn:fibonacci:480}
8 = 3 + x^2,
\end{equation}
so
\begin{equation}\label{eqn:fibonacci:500}
x = \pm \sqrt{5}.
\end{equation}
Again the \( \sqrt{5} \)’s pop out naturally, taking away some of the mystery of the cool formula.

More on that cool Fibonacci formula

November 15, 2020 math and physics play

[If mathjax doesn’t display properly for you, click here for a PDF of this post]

In my previous post, I explored the following cool formula for the nth term of the Fibonacci series. In this post, I’ll show why there are no square root fives after evaluation. A recap:

Definition 1.1: Fibonacci series.

With \( F_0 = 0 \), and \( F_1 = 1 \), the nth term \( F_n \) in the Fibonacci series is the sum of the previous two terms
\begin{equation*}
F_n = F_{n-2} + F_{n-1}.
\end{equation*}

Theorem 1.1: Nth term of the Fibonacci series.

\begin{equation*}
F_n = \frac{ \lr{ 1 + \sqrt{5} }^n – \lr{ 1 – \sqrt{5} }^n }{ 2^n \sqrt{5} }.
\end{equation*}

How the square root fives cancel out.

One of the interesting things in this Fibonacci formula, is the \( \sqrt{5} \)’s that are all over the place, while the formula represents only integer values. Expanding the formula in binomial series shows us exactly why those terms all vanish. Consider the first few values of \( n \) explicitly.
\begin{equation}\label{eqn:fibonacci:160}
\begin{aligned}
F_1
&= \frac{ 1 + \sqrt{5} – \lr{ 1 – \sqrt{5} } }{ 2^1 \sqrt{5} } \\
&= \frac{ 2 \sqrt{5} }{ 2^1 \sqrt{5} } \\
&= 1,
\end{aligned}
\end{equation}
\begin{equation}\label{eqn:fibonacci:180}
\begin{aligned}
F_2
&= \frac{ 1 + 2 \sqrt{5} + 5 – \lr{ 1 – 2 \sqrt{5} + 5 } }{ 2^2 \sqrt{5} } \\
&= \frac{ 4 \sqrt{5} }{ 2^2 \sqrt{5} } \\
&= 1,
\end{aligned}
\end{equation}
\begin{equation}\label{eqn:fibonacci:200}
\begin{aligned}
F_3
&= \frac{ 1 + 3 \sqrt{5} + 3 (5) + \sqrt{5} 5 – \lr{ 1 – 3 \sqrt{5} + 3(5) – \sqrt{5} 5 } }{ 2^3 \sqrt{5} } \\
&= \frac{ 2 \lr{ 3 \sqrt{5} + \sqrt{5} 5 } }{ 2^3 \sqrt{5} } \\
&= \frac{ 3 + 5 }{ 2^2 } \\
&= 2.
\end{aligned}
\end{equation}
In the general case, we have
\begin{equation}\label{eqn:fibonacci:220}
\begin{aligned}
2^n \sqrt{5} F_n
&=
\sum_{k = 0}^n
\binom{n}{k}
{\sqrt{5}}^k
–
\sum_{k = 0}^n \binom{n}{k} (-\sqrt{5})^k \\
&=
2 \sum_{1 \le k \le n, \mbox{$k$ is odd}} \binom{n}{k} (\sqrt{5})^k \\
&=
2 \sqrt{5} \sum_{m = 0}^{\lfloor (n-1)/2 \rfloor} \binom{n}{2 m + 1} 5^m,
\end{aligned}
\end{equation}

so (for any \( n > 0 \)),
\begin{equation}\label{eqn:fibonacci:240}
F_n =
\inv{2^{n-1}} \sum_{m = 0}^{\lfloor (n-1)/2 \rfloor } \binom{n}{2 m + 1} 5^m.
\end{equation}
Since only the odd powers of \( \sqrt{5} \) in the binomial expansions survive, the root in the basement is obliterated every time, leaving only integers upstairs, and a power of two factor downstairs. It is still somewhat remarkable seeming that there is always a perfect cancellation of all the factors of two in the basement.

The nth term of a Fibonacci series.

November 13, 2020 math and physics play , , , ,

[If mathjax doesn’t display properly for you, click here for a PDF of this post.]

I’ve just started reading [1], but already got distracted from the plot by a fun math fact. Namely, a cute formula for the nth term of a Fibonacci series. Recall

Definition 1.1: Fibonacci series.

With \( F_0 = 0 \), and \( F_1 = 1 \), the nth term \( F_n \) in the Fibonacci series is the sum of the previous two terms
\begin{equation*}
F_n = F_{n-2} + F_{n-1}.
\end{equation*}

We can quickly find that the series has values \( 0, 1, 1, 2, 3, 5, 8, 13, \cdots \). What’s really cool, is that there’s a closed form expression for the nth term in the series that doesn’t require calculation of all the previous terms.

Theorem 1.1: Nth term of the Fibonacci series.

\begin{equation*}
F_n = \frac{ \lr{ 1 + \sqrt{5} }^n – \lr{ 1 – \sqrt{5} }^n }{ 2^n \sqrt{5} }.
\end{equation*}

This is a rather miraculous and interesting looking equation. Other than the \(\sqrt{5}\) scale factor, this is exactly the difference of the nth powers of the golden ratio \( \phi = (1+\sqrt{5})/2 \), and \( 1 – \phi = (1-\sqrt{5})/2 \). That is:
\begin{equation}\label{eqn:fibonacci:60}
F_n = \frac{\phi^n – (1 -\phi)^n}{\sqrt{5}}.
\end{equation}

How on Earth would somebody figure this out? According to Tattersal [2], this relationship was discovered by Kepler.

Understanding this from the ground up looks like it’s a pretty deep rabbit hole to dive into. Let’s save that game for another day, but try the more pedestrian task of proving that this formula works.

Start proof:

\begin{equation}\label{eqn:fibonacci:80}
\begin{aligned}
\sqrt{5} F_n
&=
\sqrt{5} \lr{ F_{n-2} + F_{n-1} } \\
&=
\phi^{n-2} – \lr{ 1 – \phi}^{n-2}
+ \phi^{n-1} – \lr{ 1 – \phi}^{n-1} \\
&=
\phi^{n-2} \lr{ 1 + \phi }
-\lr{1 – \phi}^{n-2} \lr{ 1 + 1 – \phi } \\
&=
\phi^{n-2}
\frac{ 3 + \sqrt{5} }{2}
-\lr{1 – \phi}^{n-2}
\frac{ 3 – \sqrt{5} }{2}.
\end{aligned}
\end{equation}
However,
\begin{equation}\label{eqn:fibonacci:100}
\begin{aligned}
\phi^2
&= \lr{ \frac{ 1 + \sqrt{5} }{2} }^2 \\
&= \frac{ 1 + 2 \sqrt{5} + 5 }{4} \\
&= \frac{ 3 + \sqrt{5} }{2},
\end{aligned}
\end{equation}
and
\begin{equation}\label{eqn:fibonacci:120}
\begin{aligned}
(1-\phi)^2
&= \lr{ \frac{ 1 – \sqrt{5} }{2} }^2 \\
&= \frac{ 1 – 2 \sqrt{5} + 5 }{4} \\
&= \frac{ 3 – \sqrt{5} }{2},
\end{aligned}
\end{equation}
so
\begin{equation}\label{eqn:fibonacci:140}
\sqrt{5} F_n = \phi^n – (1-\phi)^n.
\end{equation}

End proof.

References

[1] Steven Strogatz and Don Joffray. The calculus of friendship: What a teacher and a student learned about life while corresponding about math. Princeton University Press, 2009.

[2] James J Tattersall. Elementary number theory in nine chapters. Cambridge University Press, 2005.

Building my new “garage”

November 12, 2020 Home renos , , , , , , , ,

I managed to sneak in a day off of work (split over two days), and built a space for all the tools that I used to keep in my double car garage. We’ve been in the new downtown house now for a year, and had most of the old house cleared out except for the garage. You can accumulate a lot of stuff in 20 years of home ownership, and moving from a house with a double car garage to a no-garage house, was quite a challenge. After many panic-demic induced delays, we eventually finished the renos on the old house, and sold it.  I’m really enjoying the new neighbourhood, where I can walk to just about everything I need, but there’s a few things that I miss from the old house:

  1. The garage!
  2. Parking spaces (6 not including the garage — I won’t miss shovelling that driveway!)
  3. The pool.
  4. The hottub.

However, number 1 — the garage, has been the most challenging.  We’ve had stuff from the garage all over the house, in the sheds in the back yard, and a whole lot of it on the back deck under a tarp.  We replaced our washer and dryer with a stacking unit to maximize the space, and I’ve now built some heavy duty shelves next to it for all the tools and toolboxes:

I’ve drilled three rows of holes, each 2″ apart, so that I can adjust the height of the shelves.  I’ve fixed the middle and the top shelf for stability.  I also tacked in the shelf on the bottom with a couple screws and should put some sort of fixed back brace, or a bottom piece so that the side supports cannot spread.  That will have to be later, since I’m out of wood (I had to scrounge a bit and my top most adjustable shelf is not big enough — so that one is temporary too.)

We may redo the plumbing on the other side of the washer dryer too. We have some long multiple hose runs, one of which leaked at one point, because of a degraded washer.   It would be better to put one of those tidy washer/dryer plumbing boxes right in the wall near the washer dryer instead of the current leak ready to happen system.  That would allow for eliminating all the too-long hoses, and give us a chance to fully optimize the long laundry closet for storage.  That and the opposite storage unit is the closest that we will get to a “garage” in the new house.

In the 2o year accumulation of stuff, I have a whole lot of tools that actually need to go.  Some of these were dad’s, and I didn’t have the heart to toss them, but it would be better to find them homes with people that will actively use them.  At the bare minimum, some of these excess tools should go to people who actually have storage space to be hoarders, something that we can no longer do.  Now that I have things arrayed in an accessible fashion, it’s time for the big sort, and then the purge after the sort.