Programming Challenge: Martian Calendar

This week, another programming challenge, but this time considerably tougher than the previous.

His Imperial Majesty, Xórgü of House Nand, decrees that the martian imperial court is in need of a new calendar. The current martian calendar counts 668 days, but it accumulates errors. The martian year, according to His Imperial Majesty’s most illustrious astronomers, is in fact 668.60 (martian) days long.

Surrogate Functions

In some optimizations problems, the objective-function is just too complicated to evaluate directly at every iteration, and in this case, we use surrogate functions, functions that mimic most of the properties of the true objective-function, but that is much simpler analytically and/or computationally.

Lately, I have done some thinking about what properties a surrogate function (or surrogate model) should have to be practical.

The Inversion Method (Generating Random Sequences IV)

In the first post of this series, I discussed how to generate permutations of sequences using the Fisher-Yates method and I explained (although indirectly) how a linear congruential generator works. In a second post, I explained how to generate 2D points uniformly and randomly distributed a triangle, discussing the method of rejection. In a third post, I’ve discussed how to generate points on a sphere.

All these methods have something in common: they are based on the uniform (pseudo)random generator, and they map uniform numbers onto a shape (or move numbers around, in the first case). What if we need another density function than uniform?

Linear Regression Revisited.

I always disliked when a book gives equations and formulas as if of fiat without providing justification or demonstration; and I don’t mind that they skip a few steps as long that I can fill in the blanks myself if I care to. Linear regression is one of those formula we see but we’d like to understand better.

So let us see how to derive the formulas for linear regression and see how they generalize to any number of unknowns.

Shellsort

The game is different whether we consider external data structures—that live partially or totally on disk or over the network—or internal data structures residing entirely in local memory. For one thing, none of the courses I had on data structures I had really prepared me to deal adequately with (large) external data structures; it was always assumed that the computer’s memory was somehow spacious enough to hold whatever data you needed.

However, when you’re dealing with files, you can’t really assume that you can access random locations to read, write, or exchange data at low cost, and you have to rethink your algorithms (or change plans altogether) to take the cost of slow external media into account. Sometimes an algorithm that doesn’t look all that useful in main memory suddenly makes more sense in external memory because of the way it scans its data. One of these algorithms is the Shellsort.

Lost+Found: Lego Antikythera Mechanism

Suggested Reading: Proof from THE BOOK

Martin Aigner, Günter M. Ziegler — Proofs from THE BOOK — 3rd ed., Springer, 2004, 240 pp. ISBN 3-540-40460-0

(Buy at Amazon.com)

Paul Erdős always refered to proofs that were particularly elegant or powerful as proofs from The Book, a book with a transfinite number of pages, held by God (in which he didn’t believe), containing all the most beautiful proofs of all mathematical theorems.

Suggested Reading: Mathematical Cranks

Underwook Dudley — Mathematical Cranks — The American Mathematical Association, 1992, 372 pp. ISBN 0-88385-507-0

(Buy at Amazon.com)

Everyone using the Internet knows about cranks. A typical crank is an individual putting forth a defective theory, usually mathematical or physical in nature, but refusing to see his errors or understanding what he missed; despite well intentioned explanations from (real) experts on the topic. The crank insists with denial and eventually aggressivity.

Random Points on a Sphere (Generating Random Sequences III)

Last week, we discussed how we could generate uniform random points in a triangle using a (tiny) bit of linear algebra, mostly the parallelogram rule, and a random variable uniform on . It required a tiny bit of math and was computationally very simple.

This time, let us see how we can generate uniformly distributed random points on a sphere.

Random Points in a Triangle (Generating Random Sequences II)

In the first post of this series, I discussed a method to generate a random (guaranteed) permutation. On another occasion, I presented a method to recycle expensive random bits. Today, I will discuss something I had to do recently: generate random points inside a triangle.