Month: April 2011

Something more on Fibonacci numbers


Pascal triangle Fibonacci
Image via Wikipedia

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} .

Related Articles

Further thoughts on “Natty Narwhal”


Official Ubuntu circle with wordmark. Replace ...
Image via Wikipedia

There are six computers in the house running Ubuntu (two are laptops) so there still a few more upgrades to go, but the process is underway (caching makes subsequent upgrades much faster).

The good news is that the upgrade to one machine – usually run as a headless email/web/squid server fixed a few configuration problems there, so not everything is bad.

The most annoying things remain (in no particular order) with Unity:

1. Lost the applets from the desktop. Knowing the temperature outside was occasionally useful and knowing the CPU temperature could sometimes be a pointer to a runaway process on the box.

2. Not being able to switch desktops with a single mouse click.

3. Not being able to see what applications I am running.

4. Not being to switch applications  with a single mouse click.

Maybe all these are fixable?

Related Articles

Ubuntu 11.04: first impressions


Ubuntu 11.04 Natty Narwhal
Image by pexatar via Flickr

Sad to say these are that I don’t care for it very much.

The “Unity” interface is just ugly and it reminds me of the way Microsoft shifted their Office menus so that, three years on from first using it I still don’t know where familiar and useful things are.

Why does it have Ubuntu One and Ubuntu Software Centre icons in pride of place? I have never made much use of either and frankly it smacks of somebody forcing their wares on me – the sort of thing that is likely to go down like a cup of cold sick in the Linux community.

Maybe there are lots of other good things here, but I cannot find them thanks to Unity. I cannot even find my bookmarks in Firefox the way that has been messed with.

So, not good so far.

Related Articles

Cyclic Redundancy Checks


Andrew S. Tanenbaum. Picture made with permiss...
Image via Wikipedia

If you have ever downloaded any software from the internet you are quite likely to have seen a reference to a “CRC” – a cyclic redundancy check.

I have been reading about them as I plough on through Andrew Tanenbaum‘s (pictured) Computer Networks: so here is an explanation based closely on his text (though it’s not a copy except where indicated)…

CRCs rely on some properties of polynomial arithmetic, namely polynomials with the coefficients 0 or 1 only.

We say that a k-bit\ frame is a list of coefficients for a polynomial with k terms ie for a polynomial ranging from x^{k-1} to x^0   (which is said to have degree\ k-1 ).

So 11001101 represents x^7 + x^6 +x^3 + x^2 + x^0 .

Polynomial arithmetic is a form of modulo-2 arithmetic “according to the rules of algebraic field theory” (that’s what it says in the book!). In practise what this means is that there are no “carry-overs” and addition and subtraction are identical and the same as exclusive or (XOR).

Hence 11011 + 10111 = 01100 while 10011 - 01011 = 11000 and so on…

To use a CRC a sender and receiver must agree a generator polynomial: in fact these are now generally standardised and IEEE 802 (network protocols) defines:

x^{32}+x^{26}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x+1

(the last two terms are of course equivalent to x^1+x^0 ).

1. Let us call this generator polynomial G(x) and let M(x) represent the polynomial (ie the sequence of 0s and 1s) we wish to transmit (with m bits) – M(x) must have more bits than G(x) .

2. Let r be the degree of G(x) – so we append r zero bits to the lower end of the frame, which now has m + r bits and is M(x)x^r (or M(x)2^r ).

3. Divide M(x)x^r by G(x) using modulo 2 division.

4. Subtract the remainder (which will always be r or fewer bits (as G(x) is of degree r) from the M(x)x^r string (again using modulo 2 subtraction). This gives the checksummed frame to be transmitted – we shall call this T(x) .

If the frame is transmitted correctly then when it is received it should be cleanly divisible by G(x) (as taking away the remainder in step 4 should leave us with a cleanly divisible frame). The additional checksum is merely the additional r bits at the end.

The power of the checksum relies on some of its mathematical properties – it will always detect single bit errors if G(x) contains more than one term – as the bad frame is now T(x) + E(x) where E(x) is the error but in this case E(x) = x^i where i is the “bad bit” but with a two-termed G(x) , x^i/[x^m + x^n] \neq 0 for any i, m, n.

Similarly, if there are two errors then E(x) = x^i + x^j = x^j(x^{i-j} + 1) so if G(x) does not cleanly divide x^k + 1 where k can be any value from 1 to the maximum of i -j (ie  the frame length) then any two bit error would be detected.

Similarly, if there are an odd number of errors then E(x) cannot be divisible by a G(x) that contains the terms x + 1. We can show by a reductio ad absurdum proof:

1. We know that an E(x) must be capable of evaluating to one: eg x^i + x^j + x^k must evaluate to 1 if x = 1. But if E(x) is divisible by (x + 1) then E(x) = (x + 1)F(x) , but if x = 1 then, modulo 2, x + 1 = 1 + 1 = 0 so E(x) = 0.

To really fool the system the error pattern would have to match G(x) which is, assuming all transmission errors are equally likely (in fact they are not, but we will ignore that for now), has a probability (again, the book says) of \frac{1}{2}^{r -1}   which is pretty small for the IEEE picked G(x) . (The GNU calculator says it is zero – so it’s too small to register there!)

Related Articles

Do universities fail science students?


President Barack Obama talks with Stephen Hawk...
Image via Wikipedia

There is a very interesting article on the THES website today – “So last century” – which says that universities are failing students because they teach them in such a compartmentalised way.

Whether the study is conducted by the CBI in the UK or by commercial for-profit educational providers drumming up business for their remedial post-baccalaureate job-training services, everyone seems to acknowledge that today’s students are good test-takers but lack the workplace essentials necessary for the 21st century. These include people skills (especially in diverse global contexts), communication skills, collaborative skills, analytical skills, networking skills, an ability to synthesise information across a wide range of evidence, and even the most elementary skills, such as how to write a great job application letter and curriculum vitae or represent their character and talent at a job interview. No wonder they face the career centre with such trepidation.

Well, while the article is well written and an interesting read I think it is fundamentally wrong.

My objection is not just the standard, liberal, view that actually universities are not meant to be factories turning out people fit for labour (albeit higher labour) – though it is partly that. Good employers invest in their employees in any case and do not expect them to be delivered for free as the fully formed article.

I certainly do not believe that there was some golden age where graduates were being turned out with all these skills either. One only has to look at the somewhat doolally behaviour – from Newton onwards – of some of the greatest scientists to know that academic excellence and socialisation are always the easiest of bedfellows.

But it is more fundamental – degrees have to be specialised, certainly in science, because they also have to be, at least partially, grounded in research and a preparation for research.

My first degree was in Astrophysics. “Communication skills, collaborative skills…” and all the rest of it have nothing very much to do with cosmology and every minute that would be spent teaching me about them would be a minute wasted in preparing me for being an astrophysist.

The fact I never became an astrophysist is hardly the point – there would not have been much point to an astrophysics degree if it at least did not offer that path.

Science degrees need to be specialised because science is ever-more complex and specialised. Some scientists think this may be a temporary thing – in A Brief History Of Time Stephen Hawking suggests that further scientific advance might simplify our theories – but there is no sign of that at present.

So, if universities are to produce scientists they have to focus on science and not think of themselves as pre-office work trainers.

Related Articles

Looks like a great book


Relational model Data items organized as a set...
Image via Wikipedia

My copy of C. J. Date‘s SQL and Relational Theory: How to Write Accurate SQL Code turned up today – I have only read one chapter so far but already I have a feeling that it is going to have been worth every penny.

Date is concerned not to write another SQL primer but to give those with some SQL experience a good grounding in the relational model and the set theory on which it is based. It just feels more like a proper scientific/mathematical text book and it also seems to be well written.

Very pleased with the purchase and will keep you all posted on how it goes: at the moment I am just wishing I had bought it months ago.

Related Articles

Relational division again


Relational divisionTake the same relational database tables as before:

RESTAURANT(RT_ID, NAME, TYPE, LOCATION)
PROXIMITY(RT1_ID, RT2_ID, DISTANCE)
USER(U_ID, NAME, EMAIL)
REVIEW(U_ID, RT_ID, RT_DATE, RATING, COMMENT)

Find the names of the reviewers who reviewed all the restaurants in Earlsfield.

In relational algebra:

\Pi _{NAME} ( USER \Join REVIEW ) \div \Pi _{RT\_ID} ( \sigma _{LOCATION = 'Earlsfield'} (RESTAURANT))

But what about SQL? As I wrote of relational division when I started the blog:

one has to implement a “double not exists” query

In this case that means “find the name of any reviewer for whom there is no Earlsfield restaurant not reviewed by that reviewer”:

SELECT NAME
FROM USER
WHERE NOT EXISTS (
SELECT *
FROM RESTAURANT
WHERE LOCATION=’Earlsfield’ AND
NOT EXISTS (
SELECT *
FROM REVIEW
WHERE REVIEW.U_ID = USER.U_ID AND
REVIEW.RT_ID = RESTAURANT.RT_ID))

At least, I hope so! I am finding this all quite heavy going – and have ordered a book – SQL and Relational Theory: How to Write Accurate SQL Code – in the hope that it will help makes things clearer. Any other recommendations gratefully received.

Update: It does work, amazingly enough.

Related Articles

Relational algebra problem


An illustration of Relational model concepts, ...
Image via Wikipedia

Have a relational database with the following tables

RESTAURANT(RT_ID, NAME, TYPE, LOCATION)
PROXIMITY(RT1_ID, RT2_ID, DISTANCE)
USER(U_ID, NAME, EMAIL)
REVIEW(U_ID, RT_ID, RT_DATE, RATING, COMMENT)

What’s the relational algebra for “name of any user who has never given Chez Brian a rating lower than 5”?

\Pi _{NAME} (USER) - \Pi _{NAME} ( \sigma _{RESTNAME='Chez\ Brian' \wedge RATING < 5}( \rho (RESTAURANT(NAME \rightarrow RESTNAME), RESTAURANT) \Join REVIEW) \Join USER)

Is this right?

Related Articles