Sleep Sort

The ingenious sleep sort algorithm makes use of the system (hardware) scheduler to sort a list of data. The original version was implemented with shell scipt:

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

example:

Of course, it can be implemented with any language that has sleep/schedule functions. A couple of examples have been shown in this wiki.

This algorithm is not as hilarious as it seems. It only takes O(n) in the idea case (ignore the time cost in scheduling and output). This is faster than fastest comparing sort algorithm such as quick sort, which takes O(n log n). The sleep time is proportional to the hardware time. It can be scaled down  dramatically. For example we can set the sleeping time to be the cpu clock period.

People have discussed the implementation of scheduling and argued that if the scheduling is achieved via priority queue it will eventually take O(n log n). But if we have sufficient "timers/schedulers", this algorithm is equivalent to bead sort.

Elemental Function and Array Valued Function in FORTRAN

Today, I "discovered" two features of FORTRAN for dealing with arrays.

It has been said arrays are the first class members in FORTRAN. Let v be an array. You can do
sin(v), which returns an array [sin(v(1)), sin(v(2)), ... ]

In order to enable the feature for user defined functions, there are two ways.
1. assign elemental attribute to a function;

elemental real function f(x)

implicit none

  real, intent(in) :: x

  f = x*x + sqrt(abs(x))/2. + 3./x;

end function

Now one can call f with array argument

2. use array valued function

real function f(x)

 implicit none

   real, intent(in) :: x(:);

   real :: f(size(x));

   f = x*x + sqrt(abs(x))/2. + 3./x;

 end function

Power of -1

To compute (-1)^n one has three options,
$ (-1)^n = (-1)^{\mod(n,2)} = 1-2 \times \mod(n,2) $

i=1,2,...10^8, time in second.

Falling of a slinky - it's shock wave

One probably has seen the above animation, the falling of a slinky. A slinky is a soft spring. In this animation, the down side of the slinky shows peculiar behavior during falling. There has been plenty of videos and articles to explain this. The point I want to emphasis is, this happens when the falling (which is not a free fall) speed is larger than the speed of sound (elastic wave) in the slinky. In other words, the falling induces a shock wave. 

Shock wave almost always has a sharp wave front. In the case of blast wave, the shock wave creates a visible wave front through the so-called shadow effect.

Shock wave from the Trinity Test

On the day of Pi - in honor of Zu Chong Zhi (祖沖之)

Yesterday, the 14th day of March, is known as the day of Pi because of its numerical similarity with Pi, the ratio of circle circumference and its diameter:
\[ \pi = 3.14159265758979... ... \]

The Book of Sui (history record of Sui dynasty) records Zu Chong Zhi's (祖沖之) estimate of Pi, called Yuan Zhou Lü (圆周率) in Chinese [2]:

And I translate it here:

Among the prominent ancient problems, the circumference is three if the circle diameter is one. This value is not accurate. From Liu Xin (劉歆), Zhang Heng (張衡), Liu Hui (劉徽), Wang Fan (王蕃), Pi Yan Zong (皮延宗) etc., new results have been reported. The value has been updated from time to time. Late in Song (劉宋) Dynasty, south Xu state (南徐州) [4] governor Zu Chong Zhi (祖沖之), further initiated the so-called fine approximation.

Assuming the circle diameter is one zhang(丈), its circumference is less than three zhang(丈) one chi(尺) four cun(寸) one fen(分) five li(厘) nine hao(豪) two miao(秒) seven hu(忽) and greater than three zhang(丈) one chi(尺) four cun(寸) one fen(分) five li(厘) nine hao(豪) two miao(秒) six hu(忽) [1]. The true value lies between these two numbers. As an approximation, the fine approximate (密律) is that for a circle with diameter one hundred thirteen its circumference is three hundred fifty five. The rought approximate (約律) is that for a circle with diameter seven, its circumference is twenty two. Zu also provided square root and square arithmetics, together with positive and negative numbers. His method is very precise, best in arithmetic. Zu wrote a monograph called Zhui Shu (綴術) [3], is so deep that not well understood among scholars. 

These texts clearly state Zu Chong Zhi's work on Pi, as early as the 5th century. This is a great achievement in mankind history of mathematics.

[1]: 丈尺寸分厘毫秒忽 are all decimalized length units, widely used in Greater China region (CJKV).

[2]: The reader need CJK fonts to display Chinese characters properly. Literally, 圆=circle, 周=circumference, 率=ratio. It's understood that the ratio is taken with respect to the diameter or 径.
[3]: Zhui Shu can be roughly translated as numerical methods. Zhui Shu had been chosen into a collection of mathematical textbooks since Tang Dynasty (唐). It was lost after Song Dynasty (宋) (A different Song Dynasty from Zu Chong Zhi's time).
[4]: In present day Zhejiang Province, China