Recent content on Paul's blog
This post provides a quick derivation of the fast Fibonacci doubling formulas, using the correspondence between Fibonacci numbers and the number of ways to climb $n$ steps taking 1 or 2 steps at a time. The Fibonacci numbers are a sequence $\mathrm{Fib}(i)$ defined by $\mathrm{Fib}(1)=\mathrm{Fib}(2)=1$ and $\mathrm{Fib}(n+2)=\mathrm{Fib}(n+1)+\mathrm{Fib}(n)$. The Fibonacci doubling formulas are:…
I’ve recently been programming seriously in C, after around 10 years in higher level languages (Go, Python, C++, and others). I’ve been using C11, the latest standard, whereas previously I was working in C89. I like programming in C. It’s not an easy language to write fluently because it doens’t provide many conveniences, it’s full of traps, and I’d avoid it if…
Computing large integer powers modulo some number is a somewhat common operation. For example, it’s used in RSA encryption. Usually, this is done using exponentiation by squaring, but this go program correctly prints the results of $n^{2^{64}}\ (\mathrm{mod}\ 115763)$ for $n$ from 1 to 20, seemingly naively: package main import "fmt" func main() { for n := 1; n <= 20; n++ { result := 1 for i…
Generation of random Latin Squares (such that each latin square of a given size is equally likely) is a deceptively difficult problem. This post describes my own implementation, loosely based on the Java implementation described by Ignacio Gallego Sagastume which implements the rather ingenious method of Jacobson and Matthews
As I was growing up in England in the 80s, there was a boom in home microcomputers, with the Commodore 64, the ZX Spectrum, and the BBC Micro being three popular choices. These provided an excellent and approachable introduction to programming, with many of my friends learning programming in BASIC and assembler. We taught ourselves the fundamentals of computing while we were playing, and at a…
This article describes how to use the Kelly criterion to make rational choices when confronted with a risky financial decision, and suggests a way to estimate the most you should be willing to pay for any particular sort of insurance. The Kelly criterion (which at its core is the idea that the logarithm of your wealth is a better measure of money’s value to you than its absolute value) is…
Programming since 1981, professionally since 2000. I’ve a PhD in programming language semantics but these days I prefer programming in Go, C, C++ and Python. I’ve worked mostly on games and large-scale server software. If you wish, you can email me at paul.hankin@pobox.com. I may not answer.
An earlier post described how to compute Fibonacci numbers in a single arithmetic expression. Faré Rideau, the author of a page of Fibonacci computations in Lisp , suggested in a private email a simple and efficient variant, that I believe is novel. For $X$ large enough, $\mathrm{Fib}_n = (X^{n+1}\ \mathrm{mod}\ (X^2-X-1))\ \mathrm{mod}\ X$. That means you can compute Fibonacci numbers efficiently…
I had never seen this mini-assembler-based educational computer before. wikipedia.org/Little_man_computer . I couldn’t find a good online emulator, so I wrote one: Little Man Computer Emulator . Enter the program on the left, click “Assemble”, enter some inputs if your program needs them, and then step through the execution. It’s probably got some bugs since it was a quick…
This blog post looks at closed-hand Chinese Poker, and describes a near-optimal strategy for it which is readily implementable on a computer.
Who would disagree that the run-time of mergesort is $O(n\mathrm{log},n)$ and it’s asymptotically optimal? Not many programmers I reckon, except perhaps to question whether it’s talking about a model of computation that’s not sufficiently close to a real computer, for example a quantum computer or one that performs arbitrary operations in parallel (possibly involving sticks of…
This code, somewhat surprisingly, generates Fibonacci numbers. def fib(n): return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1) In this blog post, I’ll explain where it comes from and how it works.