Sunday, March 27, 2011

K_v(x)

I have just wasted about three hours of sunday afternoon trying to compute a modified bessel function of second kind of fractional order (also known as hyperbolic Bessel function). I hope that this tiny C++ snippet will be googlable, and it will save a few minutes of someone's live:

#include <boost/math/special_functions/bessel.hpp>
#include <iostream>

(...)

double v = 5.0/3.0;  /* an order of Bessel function */
double x = 2.5;      /* an argument of bessel function */
double r;            /* will contain a value */

r = boost::math::cyl_bessel_k(v, x);
std::cout<<r<<std::endl;

Just in case someone is interested what is a modified Bessel function, this is an integral representation of Bessel funtion of order v:

Saturday, December 18, 2010

Turing completeness II

Well, as I wrote in the previous post, sed is a Turing complete language. We can use it to implement some simple algorithms, or even a dc interpreter. But what does it really mean? How complex tasks may we achieve using plain sed?

What about writing some game?

While browsing web, I came across a classic Tetris game written in pure sed.

Save this file to something like tetris.sed. Depending on your system, you may need to adjust shebang. For example if you are using PLD Linux, change "#!/usr/bin/sed" to "#!/bin/sed". chmod a+x it, and run it. Unfortunately main loop is controlled by input lines, so you need to press ENTER few times to allow things to happen. It seems to be the strong limitation of sed.

Don't you think it is awesome?

In case you can not get it work (or you just don't trust any piece of code that people publish on the web), there is an amazing video of tetris.sed in action:



Since there is no way to display any graphics in pure sed, we are limited to rogue-like games. Now I'm waiting for ADOM being rewritten in sed!

Saturday, October 23, 2010

Turing completeness

sed is a very powerful tool. A simple sed statement may turn a cat into cement. Observe: echo cat | sed statement
I was asked by mariom@ircnet whether is it possible to implement the Euklidean algorithm (the one that computes the greatest common divisor) in awk. awk is a Turing complete language, so the answer is yes, it is possible. There is a snippet proposed by mariom:

{
    a = $1;
    b = $2;
    while (b != 0) {
        c = a % b;
        a = b;
        b = c;
    }
    print a
}

Anyway, my response was that it is possible even in sed. Is it? Of course! Sed is a Turing complete language. Though I had no idea how to write it in sed. I use sed for simple substitutions only, but I could not admit that!

I started googling for arithmetic operations in sed and I found a dc implementation in pure sed. So the next question is how to implement the Euklidean algorithm in dc. It turned out to be quite simple, see:
[lalb%sclbsalcsblb0<F]sF sasblFxlap
This code assumes that there are two integers on the stack. So you can test it with something like that:
echo '20 25 [lalb%sclbsalcsblb0<F]sF sasblFxlap' | dc
Let's analyze what is happening there. There is F macro that is equivalent of "while" loop in awk code. It loads the values of a and b registers on the stack. Then replaces them with their reminder and saves it in the c registers.
lbsalcsb
statement just copies the value of b to a and c to b. Finaly it compares the value of b with 0. If former is greater it executes F (note: recurrence. It is the only way to implement a loop in dc). Otherwise it quits.
sasblFxlap
statement is an entry point. It saves values from stack in the a and b registers, then executes F and prints the content of the a register. So this sed script is an equivalent of awk script that executes Euklidean algothm.

Now it is enough to embed the dc script into dc.sed, et voila! Enjoy: Euclidean algorithm implemented in pure sed.