ln n!

In the course of analyzing an algorithm, I used the simplifying hypothesis that the cost function is

.

That expression is cumbersome but we can get a really good simplified function to use as a proxy. Let’s see how.

OB Sqrt

I have discussed the problem of efficient square root calculation quite a few times. And yet, while reading Rudman’s The Babylonian Theorem, I found yet another square root algorithm. The Old Babylonian square root algorithm. Let’s have a look on how it works.

Eratosuite

The other day in class, we were looking at recurrence relations and how to solve them with the characteristic equation. Among the examples I gave was a recurrence that seemed to give a good number of primes numbers. Are there many of those? How do we find them?

Well, we need two things: a method of testing if a given number is prime, and a method of generating recurrences—parameters and initial conditions. Well, make that three: we also need to generate the suite generated by the recurrence relation. Let’s go!

Pythagorean Primes

Last Week, we had a look at Pythagorean triples. Remember: a Pythagorean triple is three natural numbers (positive integers) such that . Most of the times, even with and natural numbers, is irrational. Sometimes is prime; sometimes is. Is either frequent?

Pythagorean Triples

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.

Rational approximations of π (Divertimento)

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

π like an Egyptian

In the Rhind Mathematical Papyrus (RMP) we find that the Egyptians used the approximation

For . The RMP shows how to arrive at this result: you construct a grid and draw an octagon on it that approximates the circle. Turns out this irregular octagon as of the area of the bounding square. But the ancient Egyptians rounded that value, for reasons unknown, from 63 to 64 (I have a theory on why; but that may be a later post). This gives the above approximation.

King Solomon’s Bath

In 1 Kings 7 (King James version), we read the description of Solomon’s molten sea:

And he made a molten sea, ten cubits from the one brim to the other: it was round all about, and his height was five cubits: and a line of thirty cubits did compass it round about.

…which I take is some kind of bath. Superficially, it seems to state that , since the circumference of a circle of diameter given by . But what if “round about” doesn’t strictly means “perfect circle”?.

Comparing GPSes (yet more GPS data)

In a few other entries, I’ve toyed with GPS, either getting or parsing the data with Bash, assessing or using the GPS data. However, when we use GPS, we suppose that the precision varies by brand and model&mdashsome will have greater precision—but our intuition tells us that two GPS devices of the same brand and model should perform identically. That’s what we’re used to with, or at least expect from, computers. But what about USB GPS devices?

So I got two instances of the same model+brand GPS. Let them call them GPS-1 and GPS-2. Do they perform similarly?

Unfair Coin Tossing

Suppose you want a fair coin, one that yields heads and tails with equal probability, but only have a bizarre coin that yields a side more often than the other. Can we remove the bias?

John von Neumann gave us a surprisingly simple procedure to remove bias from a coin and yield a fair toss.