Pythagorean Triples

November 24, 2015

The Pythagorean theorem, linking the sides of a right triangle, is one of the most useful basic mathematical identities. It is also one of the more entertaining. Loomis, in his book The Pythagorean Proposition (1968), gives 370 different proofs of the theorem. However, we’ll more often interested in computing the length of the hypotenuse, or finding triples—three natural numbers that makes the theorem hold—than finding a new proof for it.

There is, of course, the smallest possible triple (defined as involving the smallest possible numbers) 3, 4, 5. But there are infinitely more triples. Let’s see how we can generate them.

Read the rest of this entry »

…And a Good One (Hash functions, part VI)

November 17, 2015

In the previous entries, we learned that a good hash function for look-ups should disperse bits as much as possible as well as being unpredictable, that is, behave more or less like a pseudo-random number generator. We had a few failed attempts, a few promising ones, and now, a good one.

Read the rest of this entry »

Rational approximations of π (Divertimento)

November 10, 2015

While reading on the rather precise approximation 355/113 for π, I’ve wondered how many useful approximation we could find.


Read the rest of this entry »

Busy doing Science

November 3, 2015

Sorry, no entry for this week… I’ve been busy doing science ¯\_(ツ)_/¯

Three (somewhat) Better Functions (Hash functions, part V)

October 27, 2015

Last week’s hash functions—the check-sum, Knuth’s, and gray—produced less than optimal results. A function based only on addition, such as the check-sum, cannot possibly produce very large numbers, and therefore fails to distribute item over a very large table. That’s why there’s a confusion step following the combination step, to spread the bits around the (machine-sized) word.

So the confusion step must explicitly shuffle the bits around (although, not necessarily a permutation) and make sure that the most- and least-significant bits gets thrown around. Let’s try a couple of things!

Read the rest of this entry »

Three bad functions (Hash functions, part IV)

October 20, 2015

Devising a good, fast, simple hash function isn’t easy. At all. It’s quite the challenge, in fact. Unsurprisingly, the first tries will be somewhat disappointing, but that shouldn’t keep you from trying. This week, let’s consider a couple of simple (and not very good) functions.

Read the rest of this entry »

Testing Hash functions (Hash functions, part III)

October 13, 2015

So, this week, let’s have a look at how we will test hash functions. Testing is necessary since it’s not because your hash function looks random that it is sufficiently random to be used for look-up.


Read the rest of this entry »


Get every new post delivered to your Inbox.

Join 96 other followers