## Who has been given the cash changing problem?

Some class, somewhere, has obviously been given the recursive money changing problem as a piece of work, because I have had several hundred visits in the last week from people seeking to get a grip on it.

## An idea I saw on normblog

Norman Geras is a great man. He’s a social, not a computer, scientist, and this year I have been mainly reading computer books. Still, here’s an idea I have pinched off his website (he got it from here). Match the prompts to books you have read in the last year – in my case mainly computer books.

One time on holiday: Understanding the Linux Virtual Memory Manager

Weekends at my house are: Code Complete

My neighbour is: Programming Pearls

My boss is: The Mythical Man Month

My superhero secret identity is: The Annotated Turing

You wouldn’t like me when I’m angry because: Mussolini’s Italy

I’d win a gold medal in: The Little Schemer

I’d pay good money for: Structure and Interpretation of Computer Programs

If I were Prime Minister I would: Groovy in Action

When I don’t have good books, I: P, NP, and NP-Completeness

Loud talkers at the cinema should be: Albion’s Fatal Tree

## My first R program

Having used Groovy (which makes the scripting environment feel familiar) and some Scheme (via Structure and Interpretation of Computer Programs), R does feel completely alien, but it still feels like a steep learning curve.

But here’s my short script –

unpatched <- read.csv("~/unpatched.txt")
unpatchcons <- transform(unpatched, realm=realm*60 + reals)
attach(unpatchcons)
linelog<-lm(realm~size)
plot(size, realm, log="y")
abline(reg=linelog, untf=TRUE, col="blue",lty=3)
detach(unpatchcons)


And here’s the graph (of Linux kernel compile times) it generates – the blue line is obviously a very bad fit!

## Something more on Fibonacci numbers

My earlier blog about the Fibonacci series gets a lot of hits, so I thought I would write something more, as clearly there is interest.

Once again this is from “Structure and Interpretation of Computer Programs” (available for free here electronically):

Let $\psi = (1 - \sqrt{5})/2$ and $\phi = (1 + \sqrt{5}/2)$. Then $Fib(n) = (\phi^n - \psi^n)/\sqrt{5}$.

So $Fib(1) = (\frac{1}{2} +\frac{\sqrt{5}}{2} - \frac{1}{2} + \frac{\sqrt{5}}{2})/\sqrt{5} = 1$.

(1)$Fib(n) = (\phi^n - \psi^n)/\sqrt{5} = Fib(n - 1) + Fib(n - 2)$

(2) Then $Fib(n -1) + Fib( n - 2) = \frac{\phi^{n-1} - \psi^{n-1}}{\sqrt{5}} + \frac{\phi^{n-2} - \psi^{n-2}}{\sqrt{5}}$

(3) Simplifying (2) $Fib(n) = \frac{\phi^{n-1} - \psi^{n-1} + \phi^{n-2} - \psi^{n-2}}{\sqrt{5}}$

(4) Simplifying further – from (1): $\phi^n - \psi^n = \phi^{n-1} - \psi^{n-1} + \phi^{n-2} - \psi^{n-2}$

(5) $\phi^n - \psi^n = \phi^{n - 2}(\phi + 1) -\psi^{n- 2} - \psi^{n - 1}$

(6) We know that $\phi^2 = (\phi + 1)$ so we can restate (5) as $\phi^n - \psi^n = \phi^n - \psi^{n - 2} - \psi^{n - 1}$

So (7) $\psi^n = \psi^{n - 2} + \psi^{n - 1}$

But $\psi^2 = \psi + 1$ also and (7) can be restated as $\psi^n = \psi^{n-2}(\psi + 1) = \psi^{n-2}\psi^2 = \psi^n$

In other words, $Fib(n) = (\phi^n - \psi^n)/\sqrt{5}$.

## The lambda calculus and closures in Groovy

No sooner had I written about the lambda calculus and Structure and Interpretation of Computer Programs than I sat in a lecture on closures in Groovy and was presented with a structure like this (which multiplies two numbers, in this case 3 and 4):

Which immediately reminded me of one of Alonzo Church‘s formulations of lambdas – eg:

More to come…

## Coming up… the lambda calculus

Another thing that The Annotated Turing taught me is what all those lambdas that I have seen over the last 25 years were about, or at least it introduced me to what they were about.

So I have just ordered a copy of Structure and Interpretation of Computer Programs: and I can guess that some blog posts will eventually follow.

Oh no. Maybe I am turning into a LISP hacker – having finally reached the age that all these guys were when I first became aware of them (older, actually).