A Fast Algorithm for Computing Fibonacci Numbers

I came across an algorithm for computing Fibonacci numbers in a paper by Takahashi Daisuke; the paper’s in Japanese, but the pseudocode of the algorithm is plain enough that it’s easy to understand, even if I can’t read any of the explanation. I’ve implemented it in python, and it’s decidedly slower than the Fibonacci function in Mathematica, though that’s to be expected. My implementation takes quite a few seconds to compute F(2^20) but is quick for numbers below about F(2^15), with the additional benefits of not computing absurdly huge floats or recursing a million times.

The algorithm is apparently a refinement of another (perhaps well-known?) algorithm, which computes Fibonacci numbers from the product of Lucas numbers. I’ll have to look into it to see just how it works.

Edit: After some investigation, a large part of Mathematica’s apparent advantage is in its faster display, rather than faster computation, though Mathematica does still beat my python program by a rather huge amount–Mathematica computes Fibonacci[2^23] in about 0.2 seconds, while my program takes just over five seconds. This disparity increases as the argument grows larger. Also, found an English version of that paper. Neat.

O Calculus

Alexandre Borovik at Mathematics under the Microscope has posted a letter Donald Knuth sent to the Notices in March 1998. In it, Dr. Knuth proposed teaching calculus using big O notation. I certainly think that students could benefit from calculus being taught differently, but I admit that I don’t know what changes ought to be made, or whether Dr. Knuth’s proposal would be beneficial.

Whether the O Calculus idea is used or not, the letter is worth reading: it is always beneficial to explore other ways of doing and understanding things.

Pathetic Innumeracy

MarkCC from Good Math, Bad Math has discussed an article in the Manchester Evening News about a lottery scratch-off game in Britain. The premise is that the purchasers are given a target temperature, and they want to scratch off to find temperatures that are lower than the target.

But they can’t do it. People don’t understand negative numbers. In the particular case given, it seems fairly unforgivable, since temperature is something people experience every day. In fact, I remember in first grade (when I would have been 7 years old), being asked some question like “What is five minus six?”, and understanding the significance of negative numbers.

I want to speak of something else, though. It’s the usage of ‘smaller’ to describe order. This was brought up in the comments, and I really think that people should stop talking about -10 as being ‘smaller’ than -5. Yes, -10 is ‘less than’ -5 in the usual order on the reals, but, to me, ‘smaller’ seems to imply a statement about magnitude, not order. When I’m confronted with the term ‘smaller’, I often find that I need to consider carefully whether it is magnitude or order that is being discussed, because both can happen even in very similar contexts.

Consider limits, for example. What is the behavior of f(x) as x approaches minus infinity? How about as x approaches zero? Now, which of these could be spoken of as being the behavior of f(x) as x becomes very small? For my money, x becoming very small means x approaching zero, but it’s not hard to imagine that someone might mean x approaching minus infinity. And, in particular, there is no problem speaking of the limit from the right as x approaches zero as being ‘x getting smaller’, but what about the limit from the left? Then x is increasing, but maybe also getting smaller.

The imprecision of language is something that is problematic in math as well as ‘the real world’, and is apparently extra-troublesome when they intersect. In math we often use many different terms to mean the same thing (or the same term to mean many different things), and for this reason I’ve always found textbooks that make a point of mentioning alternate terminology to be very helpful. It would be nice if we could all agree on things and choose nice, distinct terms, though. Well, perhaps one day.

Checkers solved

According to Alexandre Borovik at Mathematics under the Microscope, checkers has been solved: perfect play yields a draw. The link to the abstract that he gave isn’t loading for me, so I can’t tell if there is any more to it than that (e.g. “Checkers solved! Cancer found to be a subset of checkers.”), but this is both an interesting and unfortunate thing for me.

I don’t play much checkers, and when I do play I don’t always win (or draw). I usually comfort myself when I perform poorly in games by reminding myself that even computers have trouble with such things. Now that checkers has been solved, any failures are only my own. Of course, there are other games to play: chess and go are considerably more complicated, so I understand; unfortunately I’m only average at chess and quite bad at go. No worse than the situation with checkers, I suppose, but still unpleasant.

I could always play tic-tac-toe, I suppose–it too yields a draw, but I am fairly sure I can play it perfectly. I wonder what similarities there are between games (for some suitably restricted definition of ‘games’) in which perfect play results in a draw. I confess I know nothing substantial about game theory. Perhaps I’ll look into Monday; it would be nice to be able to say with a straight face that checkers and tic-tac-toe are basically the same game, although I think that will not be the result of my study. Still, one can always dream.

The Man Who Mistook etc.

I completed The Man Who Mistook His Wife for a Hat yesterday, so I can now give my opinions on the work as a whole. I still feel that it was a good book, but some of the sections were less interesting than others (although none were entirely dull), and it did have slow moments; I admit that I skimmed over a paragraph here and there. One thing I want to remember from this: a book by Robert Silverberg called Thorns was referred to in a footnote, and I think that I may read it.

I’m getting further and further behind on Wikipedia–I keep seeing pages and thinking ‘Oh, I need to fix that later,’ and then just adding it to the end of the growing list of things that I may not get to any time soon.

I’m not making much progress mathematically, either. I’ve not read any more of the analysis books I acquired, despite having a deadline since I got them via ILL. Part of the problem is that I cannot realistically finish HAF before I’ve got to return it, so I have trouble gathering the willpower to return to it.

Not only am I behind in my private studies, I’ve got work piling upon me from classes, as well. I’ve a cryptography test to complete, a programming assignment to both start and finish, and a problem set from analysis all to be done by the end of the weekend. It’s probably less than eight hours of work, even if I take my time, but it still irritates me.

To make matters worse, I’ve decided (for no good reason, I’m sure) that it might be neat to be able to submit patches to MediaWiki (which I believe anyone can do). This wouldn’t be a problem except that actually doing it would involve learning PHP, a language of which I know nothing, as well as studying the MediaWiki code. I may not even be capable of it (at present), since I’ve little experience with coding outside of mathematical things which are generally more procedural. Probably I won’t end up doing this, but that just means that I’ll have substituted surrender for defeat, which is an unpleasant choice to make.

The Man Who Mistook His Wife for a Hat

I picked up a copy of The Man Who Mistook His Wife for a Hat by Oliver Sacks recently, and I’ve been enjoying it quite a bit. It’s a compilation of case histories of patients with neurological damage (the title is from a case of a man with visual agnosia). The stories are interesting and occasionally amusing. When I’ve finished, I may post a summary of whichever story I like best, but they’re all quite good, I think.

I’ve made little progress on Between Silk and Cyanide since I last wrote of it, nor have I begun any other other books.

Regarding Wikipedia: I thought that I might take a look at articles on high schools, since they seem to get vandalised rather a lot, and are generally of low quality. I improved (slightly) Aberdeen High School, but it wasn’t very pleasant. Perhaps the worst of it was simply my unfamiliarity with the standard layout for schools and the high school infobox. But even discounting this, it was annoying, since the only news article I could readily find that had useful information about a fire mentioned in the article was subscription-only, and I could by no means change that. It is things like this that reassure me that Wikipedia’s mission to provide access to the sum of human knowledge to everyone is important: the idea of locking that information up behind a subscription just seems awful.

I may try to work on some other school articles later. They don’t rank very high on my ‘things that really need improved’ list, but they are relatively easy to improve, due mostly to the poor quality common to so many of them.

As for my mathematical endeavours: I’ve made little progress into the Handbook of Analysis and its Foundations (HAF), due mostly to other things taking up my time, and it may be pushed further back. I’ve had Rudin‘s Principles of Mathematical Analysis recommended to me, so I’ve picked up a copy of that to give it a look. It begins by developing the reals from the rationals via Dedekind cuts, which is nice, but I haven’t read past that yet. I’ll have to try to read it while struggling through HAF and also reading Ross’s Elementary Analysis: The Theory of Calculus, which is the assigned text for the analysis course I’m taking.

I don’t actually like Ross’s book very much, but it’s reasonably clear and simple. The fact is that I don’t like the subject very much, but I am interested in topology, based on what little I know of it, so some knowledge of this is necessary and useful.

That’ll do for now. I need to stop before I spend more time writing about my books than reading them.

Shame as a motivator

I’ve finally begun writing the article on rook theory for wikipedia that I’ve been putting off for a month or two. It turns out that my pride can only handle so much procrastination, which I suppose is a good thing. I’ve only managed a couple of paragraphs so far, but there’s an article that I’ll want to reference in the library, so I may increase it by a couple of paragraphs by the end of the day.

I finished reading Dragonflight by Anne McCaffrey last night. I seem to recall it being longer, but it may be that I moved directly to the second book last time, and didn’t think of the length of the book. It’s possible, too, that I’m reading more quickly now, due to massively more practice, but I’ve no good way to measure that.

This morning I read an article from the APA website: Unskilled and Unaware of It: How Difficulties in Recognizing One’s Own Incompetence Lead to Inflated Self-Assessments (this is a PDF). Now, how could I resist reading something with a title like that? It was mentioned on wikien-l and turned out to be an interesting read. The title serves as a pretty good executive summary of the article, since much of the rest is just data and an explanation of the testing methods. The important result is that people who are especially incompetent are unable to realize this fact, and are also unable to recognize competence in others.

On an unrelated note, I’ve been working my way through Handbook of Analysis and Its Foundations by Schechter. I think I’m averaging around six pages an hour, which either means that I’m very bad at math or that the book is very good. Obviously, I’m hoping for the latter. I’ve gained a few new perspectives and not a little actual new knowledge from the book, so I may record them here later. But now, it is time for class.

Books

I got a copy of The Dragonriders of Pern, an omnibus containing the first three Pern books by Anne McCaffrey, as well as Handbook of Analysis and Its Foundations by Eric Schechter.

The Pern book is great, just as it was the first time I read it; I hope that I’ll be able to get the others in the series once I’ve finished with it.

The analysis book seems to be pretty cool. I’ve only read the first chapter so far, but I like what I’ve seen. The first chapter covers basics: what is an operation, what is ZF set theory, products of sets, etc. In particular, the idea of considering a product of sets as a collection of functions is something I’ve never seen before that seems like it may be interesting, possibly. I’ll have to see whether (and how) it’s used later in the book.

I’m thinking of making a study of compass and straightedge constructions. I understand that there is some algebra of these constructions, or something, but I’m not familiar with it. I’ll pick up a book from the library some time and look into it.

The Lathe of Heaven

I’ve just (yesterday) finished reading The Lathe of Heaven by Ursula K. Le Guin. It’s a sci-fi novel about a man whose dreams have the power to change reality. It was enjoyable, but I found that it wasn’t always clear just what was going on, and why (then again, this may have been intentional, since the main character also seemed confused). It was worth reading once, anyway.

As far as math is concerned: I’ve discovered that I hate category theory. It seems like it ought to be good for something, but I’m just not sure how it all works, or even what some of the terminology and notation means. I’ve still got one category theory book which I may try to read a bit more, but I’ve little motivation at this point.

I’ve got a test tomorrow in statistics, a class which I haven’t been attending since the first week of the term. However, it’s a very introductory course. The topics to be covered on the exam (as far as I can tell) are binomial distribution, normal distribution, and the prerequisite knowledge for these like mean, median, standard deviation, etc. I’ll discover tomorrow whether my ‘sleep now, study later’ policy was a good idea.

Also: my computer hates me. I’m not sure why, but sometimes it just slows down so that even typing into notepad is unbearably slow (i.e. I finish typing a sentence and have to wait 5-10 seconds for the text to catch up). Even as I type this, I’m getting a bit ahead of the text on screen. Sometimes, though, the computer works fine. Unfortunately, the ‘unbearably slow’ times seem to outweigh the ‘fine’ times, so I will need to do something. My solution at the moment is to download an Ubuntu live dvd and just boot into that to do everything. It’ll probably be faster, by and large, than what I’m suffering through now, and it’ll prevent me from needing to do anything drastic to my computer. I really would like to just format my drive and install a copy of debian, but I fear that there’s some windows-only thing that I’ll need, so I keep putting it off. Well, here’s to procrastination. I’ll fill in the rest of what I meant to write tomorrow. For now, fiction and my bed beckon.

Update (2007-09-12): The computer problem was due to overheating. Cleaning the fans thoroughly fixed it.