Primality testing? You want primality testing?

Perl version

Consider the following little treasure:

perl -le 'print "PRIME" if (1 x shift) !~ /^(11+)\1+$/' 17

Elegant, eh? It tests whether 17 is prime by creating a list of 17 ones in a row, and then trying to pattern-match them against start-of-line multiple-copies-of-n-ones end-of-line. Not pretty, but it works.

C++ version

If you thought the primality testing via perl regexp's was scary, you ain't seen nothing yet...here's something that Dan Piponi wrote to test primality in C++. It's all based on naive set theory, and it uses the C++ template mechanism at a level that's boggling to my mind, anyhow.

From here on is Piponi speaking:

Some people may find the following of (purely theoretical) interest. It appears that the latest C++ standard defines templates in such a way that they now form a universal computer. In principle we can now push as much computation as we like to compile time lightening the load at run time. Of course the example below is a little extreme but it demonstrates the point. It's a primality tester that does all of its work at compile time and yet makes no use of the usual C++ compile time expression evaluator. It does so by defining integers from basic axioms (cf. Godel, Escher, Bach by D Hofstadter). Clearly this isn't directly useful but I found that writing it opened my eyes to some potentially useful techniques.


//
// A C++ program to test for the primality of the number 13
//
// It has the curious property that it does no arithmetic
// but uses only the template mechanism and class derivation
// to achieve its result. It starts at the most basic axioms
// of arithmetic starting with the definition of zero and
// its successors...
//
// You'll need a good C++ compiler.
//
// (c) D Piponi (But copy it as much as you like if you credit me)
//

//
// First a little trick to find the base class of our
// classes because the template mechanism requires
// exact matches.
//
// Two values are considered equivalent if they have
// the same baseclass. For example 1+1 isn't
// identical to 2 but 1+1 *is* derived from 2.
//
template<;class V> struct Value { typedef V value; };

//
// Define zero
//
struct zero
        : public Value<zero> { };

//
// Define the successor of an integer
//
template<class C> struct S
        : public Value<S<C> > { typedef C predecessor; };

//
// Now we have the integers. So introduce some convenience
// types.
//
typedef S<zero> one;
typedef S<one> two;
typedef S<two> three;
typedef S<three> four;
typedef S<four> five;
typedef S<five> six;
typedef S<six> seven;
typedef S<seven> eight;
typedef S<eight> nine;
typedef S<nine> ten;

//
// Define plus,...
//
template<class C,class D> struct plus
        : public S<plus<C,D::predecessor> > { };

template<class C> struct plus<C,zero>
        : public C { };

//
// ...minus...
//
template<class C,class D> struct minus
        : public minus<C,D::predecessor>::predecessor { };

template<class C> struct minus<C,zero>
        : public C { };
//
// ...and times.
//
template<class C,class D> struct times
        : public plus<C,times<C,D::predecessor>::value> { };

template<class C> struct times<C,zero>
        : public zero { };

//
// Define the usual ordering on the integers.
//
template<class C,class D> struct ge
        : public ge<C::predecessor,D::predecessor> { };

template<class C> struct ge<C,zero>
        : public one { };

template<class C> struct ge<zero,C>
        : public zero { };

template<> struct ge<zero,zero>
        : public one { };

//
// Divisibility testing
//
template<class C,class D,class E = S<S<zero> > > struct Divisible { };

template<class C,class D> struct Divisible<C,D,S<S<zero> > >
        : public Divisible<C,D,ge<C,D>::value> { };

//
// The case C<D:
// In this case D divides C iff C is zero.
//
template<class C,class D> struct Divisible<C,D,zero>
        : public zero { };

template<class C> struct Divisible<zero,C,zero>
        : public one { };

//
// The case C>=D:
// D divides C iff D divides C-D.
//
template<class C,class D> struct Divisible<C,D,S<zero> >
        : public Divisible<minus<C,D>::value,D> { };

//
// Primality testing
//
template<class C,class D = two,class S = zero,class E = zero,class F =
zero> struct Prime { };

//
// We use recursion to set up a loop from 2 to one less
// than the integer we are testing. Essentially this is a state machine
// using template parameters to record the current state.
//

// Are we at the end of the recursion?
//
template<class C,class D> struct Prime<C,D,zero,zero,zero>
        : public Prime<C,D,one,zero,ge<D,C>::value> { };

//
// Test potential factor D, trying successor on failure.
//
template<class C,class D> struct Prime<C,D,one,zero,zero>
        : public Prime<C,S<D>,zero,Divisible<C,D>::value,zero> { };

//
// Found a factor.
//
template<class C,class D> struct Prime<C,D,zero,one,zero>
        : public zero { };

//
// Reached the end of the loop without finding divisor.
//
template<class C,class D> struct Prime<C,D,one,zero,one>
        : public one { };

//
// Convenience method for humans allowing input of
// numbers in decimal format.
//
template<class C,class D> struct Decimal
        : public plus<times<ten,C>::value,D> { };

//
// Unfortunately the I/O interface spoils the purity of it all.
//
#include <stdio.h>

template<class C> char *output(C);

template<> char *output(zero) { return "No"; }

template<> char *output(one) { return "Yes"; }


main() {
    //
    // Is 13 prime?
    //
    puts(output(Prime<Decimal<one,three>::value>::value()));
}

Software engineering?

This paper describes a Perl module -- Lingua::Romana::Perligata -- that makes it possible to write Perl programs in Latin. A plausible rationale for wanting to do such a thing is provided.

Amazing code (from obfuscated C and other sources

Multilingual code

                                                                        (* /*
C > /) 2> /dev/null & echo hello world!; exit
C << 'CC'
C
C	This file is a portable:
C	- (ANSI/KR) C source, about which lint(1) does not complain/warn;
C	- (ISO) Pascal source;
C	- (ANSI) Fortran-77 source;
C	- (POSIX/V7/BSD/System V) shell script.
C
C*/ foo()) { extern *bar; return ++bar; /*
C*) program {*/} int (* /*
C*) (output); begin writeln('hello world!') end. {
      print *, 'hello world!'
      end
C*/ bar); main() { puts("hello world!"); return !foo(); /*
CC
C*/}

Turing machine emulation in vi

Why? Because you can.

First, here are the macros that the author refers to as "tm". Here's the start of the instructions:


			Vi Turing Machine Emulation
			---------------------------

This directory contains a set of macros which allow vi to simulate a
Turing Machine.  The file "tm" contains the macros.  The "TM*" files
each contain a turing machine description.

To execute the TMupdown machine, do the following:

	$ vi TMupdown
	:so tm

Then, from escape mode in vi, type 'g' for go.

I've included a simple turing machine description to use as an example
in explaining the format.

--------------------- cut here for sample turing machine -------------------

START	{####:####:R:DOWN}
DOWN	{up:down:R:DOWN}	{%%%%:%%%%:L:UP}
UP	{down:up:L:UP}		{####:####:R:DOWN}

####
up
up
up
up
%%%%
------------------------- end of turing machine ----------------------------
For the rest of the story, look here .
John F. Hughes
Last modified: Tue Nov 7 15:45:47 EST 2000