## O(1) algorithm for Cantor's enumeration of rational numbers

C code:

#include <stdio.h>
#include <math.h>

/* Prints the n-th fraction in Cantor's enumeration. */
void print_fraction(int n)
{
int d = (-1 + sqrt(1 + 8 * n)) / 2;  /* Diagonals to skip */
int e = n - d * (d + 1) / 2;         /* Extra steps after the skip.
*/
int v1 = e <= 1 ? d + e : d + 2 - e;
int v2 = e <= 1 ?     1 : e;

printf("%d / %d\n", d % 2 == 0 ? v1 : v2,
d % 2 == 0 ? v2 : v1);
}

int main()
{
size_t i;
for (i = 1; i < 20; i++) {
print_fraction(i);
}
}

Output:
1 / 1
1 / 2
2 / 1
3 / 1
2 / 2
1 / 3
1 / 4
2 / 3
3 / 2
4 / 1
5 / 1
4 / 2
3 / 3
2 / 4
1 / 5
1 / 6
2 / 5
3 / 4
4 / 3


## Finding the second incoming link to the second node in a loopy linked list

It is already given that the loop is formed at the second node of the linked list, i.e. the second node has two incoming links, one from the first and the other from the last node. The address of the last node that links to the second node and forms the loop needs to be found.

/* Solution to a problem asked at:
http://www.orkut.co.in/Main#CommMsgs?cmm=1027&tid=5470285126748556338

Author: Susam Pal
*/

#include <stdio.h>
#include <stdlib.h>

struct node {
int data;
struct node *next;
};

/* Detects the loop and returns the address to the last node that
links to the second node, i.e. head->next. Consumes O(1) memory
and O(n) time.
*/
struct node *last_node(struct node *head)
{
struct node *p1;
struct node *p2;

p1 = p2 = head->next;
while (p1->next != p2->next->next) {
p1 = p1->next;
p2 = p2->next->next;
}
return p1;
}

struct node *create_node(int data)
{
struct node *p;
p = (struct node *) malloc(sizeof *p);
p->data = data;
return p;
}

int main()
{
struct node *p;
struct node *second;
struct node *second_node;

p = head = create_node(1);
p = p->next = create_node(2);
p = p->next = create_node(3);
p = p->next = create_node(4);
p = p->next = create_node(5);
p = p->next = create_node(6);
p = p->next = create_node(7);
p->next = head->next; /* Loop to second node */

printf("Last node has address %p and data %d.\n", p, p->data);
return 0;
}

Output from my system:
Last node has address 0x7330d0 and data 7.

## Garbage value at the end of STAFResult::STAFString

#include <iostream>
#include <string>
using namespace std;

#include "STAF.h"
#include "STAFString.h"

int main(int argc, char **argv)
{
STAFString name("foo");
STAFHandlePtr handle;

int rc = STAFHandle::create(name, handle);
if (rc != 0) {
cerr << "Could not create STAF handle; error code: " << rc <<
endl;
return 1;
}

STAFResultPtr result = handle->submit("127.0.0.1",
"VAR",
"RESOLVE STRING
{STAF/Env/DUMMY}");
if (result->rc != 0) {
cerr << "Could not run STAF command; error code: " << rc <<
endl;
return 1;
}

STAFString output = result->result;
cout << "Output: " << output.buffer() << endl;
}

Output:
C:\MixedBag\debug>echo
%DUMMY%
Why__does__it__break

C:\MixedBag\debug>STAFExperiments.exe
Output: Why__does__it__break/Env/DUMMY}}

The '/Env/DUMMY' at the end is garbage. The results are not '\0'-terminated in the result-buffer. The correct way to get the output is as follows:
cout << "Output: " << string(output.buffer(), output.length()) << endl;


## Coefficient of variation function in PostgreSQL

Today, I learnt how to create an aggregate function in PostgreSQL function that wraps the functionality provided by other PostgreSQL aggregate functions. In this attempt, I created a cv() function that calculates the coefficient of variation. Effectively, cv(x) is equivalent to stddev(x) / avg(x).

### Table to be used for verifying the function

susam@nifty:~/math$createdb statistics susam@nifty:~/math$ cat perf.sql
CREATE TABLE performance
(
name VARCHAR,
duration DOUBLE PRECISION
);

INSERT INTO performance VALUES ('RAND', 101.0);
INSERT INTO performance VALUES ('ZERO', 157.0);
INSERT INTO performance VALUES ('NONE', 209.0);
INSERT INTO performance VALUES ('TEST', 176.0);
INSERT INTO performance VALUES ('UNIT', 197.0);
INSERT INTO performance VALUES ('LOAD', 193.0);
INSERT INTO performance VALUES ('FREE', 198.0);
susam@nifty:~/math$psql statistics psql (8.4.3) Type "help" for help. statistics=# \i perf.sql DROP TABLE CREATE TABLE INSERT 0 1 INSERT 0 1 INSERT 0 1 INSERT 0 1 INSERT 0 1 INSERT 0 1 INSERT 0 1 statistics=# select * from performance; name | duration ------+---------- RAND | 101 ZERO | 157 NONE | 209 TEST | 176 UNIT | 197 LOAD | 193 FREE | 198 (7 rows) statistics=#  ### Extracting details required to create the function statistics=# SELECT aggtransfn, aggfinalfn, aggtranstype::regtype, agginitval statistics-# FROM pg_aggregate statistics-# WHERE aggfnoid='stddev(double precision)'::regprocedure; aggtransfn | aggfinalfn | aggtranstype | agginitval --------------+--------------------+--------------------+------------ float8_accum | float8_stddev_samp | double precision[] | {0,0,0} (1 row) statistics=# SELECT aggtransfn, aggfinalfn, aggtranstype::regtype, agginitval statistics-# FROM pg_aggregate statistics-# WHERE aggfnoid='avg(double precision)'::regprocedure; aggtransfn | aggfinalfn | aggtranstype | agginitval --------------+------------+--------------------+------------ float8_accum | float8_avg | double precision[] | {0,0,0} (1 row) statistics=#  ### The function susam@nifty:~/math$ cat cv.sql
CREATE OR REPLACE FUNCTION finalcv(double precision[])
RETURNS double precision
AS $$SELECT float8_stddev_samp(1) / float8_avg(1);$$ LANGUAGE SQL;

CREATE AGGREGATE cv(double precision)
(
sfunc = float8_accum,
stype = double precision[],
finalfunc = finalcv,
initcond = '{0, 0, 0}'
);

susam@nifty:~/math$ ### Usage and verification: susam@nifty:~/math$ psql statistics
psql (8.4.3)
Type "help" for help.

statistics=# select stddev(duration), avg(duration) from performance;
stddev      |       avg
------------------+------------------
37.1682147873178 | 175.857142857143
(1 row)

statistics=# select stddev(duration) / avg(duration) as cv from performance;
cv
-------------------
0.211354592616754
(1 row)

statistics=# \i cv.sql
CREATE FUNCTION
CREATE AGGREGATE
statistics=# select cv(duration) from performance;
cv
-------------------
0.211354592616754
(1 row)

statistics=#


### Bessel's correction

I checked whether Bessel's correction was used in the stddev() function of PostgreSQL. Yes, it was used.

foo
bar


susam@swift:~\$perl -e 'print(("foo" =~ //) . "\n")' 1  ### Python susam@swift:~\$ python
Python 2.5.2 (r252:60911, Jan  4 2009, 21:59:32)
[GCC 4.3.2] on linux2
>>> re.compile('').search('foo')
<_sre.SRE_Match object at 0x7fc6c5a2c510>


### Java

susam@swift:~\$cat RegexExperiment.java import java.util.regex.Pattern; import java.util.regex.Matcher; public class RegexExperiment { public static void main(String[] args) { System.out.println(Pattern.compile("").matcher("foo").find()); } } susam@swift:~\$ javac RegexExperiment.java && java RegexExperiment
true


susam@swift:~\$mzscheme Welcome to MzScheme v4.0.1 [3m], Copyright (c) 2004-2008 PLT Scheme Inc. > (regexp-match "" "foo") ("")  ### LISP: susam@swift:~\$ clisp
i i i i i i i       ooooo    o        ooooooo   ooooo   ooooo
I I I I I I I      8     8   8           8     8     o  8    8
I  \ +' /  I      8         8           8     8        8    8
\  -+-'  /       8         8           8      ooooo   8oooo
-__|__-'        8         8           8           8  8
|            8     o   8           8     o     8  8
------+------       ooooo    8oooooo  ooo8ooo   ooooo   8

Welcome to GNU CLISP 2.44.1 (2008-02-23) <http://clisp.cons.org/>

Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2008

Type :h and hit Enter for context help.

[1]> (regexp:match "" "foo")
#S(REGEXP:MATCH :START 0 :END 0)


### libpcre3:

susam@swift:~\$ls -l /usr/lib/libpcre.so* lrwxrwxrwx 1 root root 17 May 3 15:15 /usr/lib/libpcre.so -> libpcre.so.3.12.1 lrwxrwxrwx 1 root root 17 Jan 6 14:57 /usr/lib/libpcre.so.3 -> libpcre.so.3.12.1 -rw-r--r-- 1 root root 162816 Jul 14 2008 /usr/lib/libpcre.so.3.12.1 susam@swift:~\$ cat pcre.c
#include <stdio.h>
#include <string.h>
#include <pcre.h>

#include <stdio.h>
#include <string.h>
#include <pcre.h>

int main(int argc, char **argv)
{
pcre *p;
char *re = "";
char *s  = "foo";
const char *errmsg;
int errpos;
int ovector[10];
int ret;

p = pcre_compile(re, 0, &errmsg, &errpos, NULL);
ret = pcre_exec(p, NULL, s, strlen(s), 0, 0,
ovector, sizeof ovector / sizeof *ovector);

printf(ret < 0 ? "no match\n" : "match\n");
}

susam@swift:~\\$ gcc -lpcre pcre.c && ./a.out
match
`