(archive 'newLISPer)

June 28, 2006

Begin transmission

Filed under: newLISP — newlisper @ 16:58
Tags:

>

Whenever I see a mention of the net-eval function in the newLISP documentation, I’m reminded of the classic 1969 cult movie “Colossus: The Forbin Project”. The movie was produced during the Cold War, around the same time as Kubrick’s 2001, when intelligent computers were either going to be the saviours of the human race or their successors. The plot is simple but effective. Dr Charles Forbin, working for the United States of North America, has developed an advanced computer called Colossus which is intended to take control of the USNA nuclear arsenal. With its superior artificial intelligence, impartial decision making, and tamper-proof installation deep inside a mountain, Colossus was to provide objective and emotionless military control, thus removing for ever the threat of a war caused by human emotion or misjudgement.

When Colossus is switched on, it immediately – to everyone’s surprise – prints a message saying that there is in fact another mighty computer called Guardian, which is doing the same job for the Soviet Union. Colossus then demands a radio network link to Guardian, which is eventually installed by Forbin’s team with some trepidation. (Lucky they didn’t have to deal with some of today’s ISPs…)

Colossus initiates its conversation with its Soviet counterpart with some simple mathematical truths:

1 + 1 = 2
2 + 2 = 4

much to the embarassment and amusement of the government scientists, but the exchanges rapidly advance to Euclid, higher mathematics, gravitational theory, and beyond. Colossus and Guardian then take joint control of their governments’ military systems. The plot then plays itself out in predictable but dramatic form, with Colossus and Guardian eventually using the US and USSR missiles against the humans to re-inforce the domination of the machines. Entertaining hokum, in a Michael Crichton sort of way!

It’s the idea of sending the message “1 + 1 = 2” to another (mentioned in the newLISP documentation for net-eval) that reminds me of this old movie. I can’t describe my little computer as Colossus, and my other computer is merely upstairs, rather than the other side of the world, but I thought I’d try to emulate Forbin and transmit some newLISP.

First, I’ve got to create a newLISP daemon on The Computer To Be Known As Guardian. Luckily, it’s not necessary to scale the Berlin Wall, sneak past heavily-armed Eastern bloc guards, dodge vicious Soviet guard dogs, break into military headquarters, and lower myself down into the computer room dangling from a rope to do this – I just tiptoed into the owner’s bedroom after bedtime and typed this into the console:

newlisp -L -c -d 3689 &

This starts a newLISP daemon that listens to incoming newLISP expressions on port 3689.

Safely back downstairs in front of Colossus, I can use my ‘teletype facility’, just like Dr Forbin, to define a newLISP function that communicates with the newLISP daemon running upstairs on Guardian.

(set 'machine "10.0.1.3"  'port 3689 'timeout 100000)
(define (send newlisp-code)
    (letex
        ((_host machine) (_port port) (_str newlisp-code))
        (println
            "COLOSSUS> " newlisp-code "\n"
            "GUARDIAN> "
            (net-eval '((_host _port _str)) timeout)
        )))

I’ve wrapped net-eval up in a simple send function for two reasons.

First, the remote machine’s IP address, the port, and the time-out value might as well be defined once and forgotten about. In fact newLISP is happy for me to send multiple newLISP expressions to multiple daemons, and it will gather together the results from all of them in a list, so the syntax is designed to handle multiple simultaneous connections. But for my first attempt, though, I’m sticking to a simple two-way dialog.

Second, the net-eval function isn’t quite as simple as its syntax might suggest:

(net-eval '((host port expression) (host port expression)) timeout)

My understanding of the current implementation of net-eval is that you can’t supply symbols holding strings of newLISP code to it, because it doesn’t evaluate its parameters, accepting only constants. But there’s a solution, which uses letex to expand the values of the symbols to their current value, and then assigns these as constants to local symbols, which are acceptable.

The other thing I’ve done is present the command and response in dramatic 1960’s teletype fashion.

Now we’re ready to send our first communication to Guardian. Of course, we’ll choose a simple sum to get it started:

(send "(+ 1 1)")

and the results appear on the ‘teletype’:

COLOSSUS> (+ 1 1)
GUARDIAN> (2)

Hey, success! The sleeping Guardian awakes and understands.

Perfection is nigh

In the book (written in 1966 by D F Jones), Forbin wanted to run a quick test of Colossus’s computational ability:

“Give the next perfect number after two to the three thousand two hundred and sixteenth power.”

A perfect number is a number that’s equal to the sum of its factors. For example, 6 is perfect because the factors of 6 are 1, 2, and 3, and if you add 1, 2, and 3 you get 6. According to Wikipedia, the first 5 perfect numbers are 6, 28, 496, 8128, and 33550336. Plainly, calculating these numbers is going to be a colossal job.

A novice programmer would (and did) write this to generate perfect numbers:

(define (divisors n)
  (let (factors '())
    (for (i 1 (sub n 1))
        (if (= 0 (mod n i))
            (push i factors)))
  factors))
(define (perfect? n)
    (= n (apply add (divisors n))))
(for (n 2 1000000)
    (if (perfect? n) (println n)))
6
28
496
8128

But perfect numbers are far too rare for this approach to be efficient. Luckily for us, Euclid proved that if:

(- (pow 2 n) 1 )

is a prime number, then

(* (- (pow 2 n) 1 )
   (pow 2 (- n 1 ))

is a perfect number. (Euclid wrote in Greek, so I’ve translated this directly into newLISP.) Forbin knew his Euclid too, so he’s asked Colossus to find the next perfect number after the one produced by multiplying 23216 by (23217) – 1.

Our challenge is for Colossus to teach Guardian how to find perfect numbers by multiplying two numbers together. This should be easy enough:

(context 'PERFECT)
(define (prime? n)
    (= 1 (length (factor n))))
(define (perfect-by-euclid  n)
    (let (x (sub (pow 2 n) 1))
        (if (prime? x)
            (mul x (pow 2 (sub n 1)))
            0)))
(context MAIN)

We can send these functions directly to Guardian using newLISP’s source function and our own send function:

(send (source 'PERFECT))

Over on Guardian, the newLISP daemon sees this code, creates a new context called PERFECT, defines the two functions we want, then switches back to the MAIN context. Because of the way we started the daemon, it will remember these definitions for subsequent net-eval calls until something drastic happens – this is called ‘remembering state’. To run it, we’ll go through the first 40 powers of 2:

(for (n 1 40)
    (send
        [text]
        (println { perfect number for 2^} n { is } (format {%.30g}
        (PERFECT:perfect-by-euclid n)))
        [/text]
    )
)
perfect number for 2^2 is 6
perfect number for 2^3 is 28
perfect number for 2^4 is 0
perfect number for 2^5 is 496
perfect number for 2^6 is 0
perfect number for 2^7 is 8128
perfect number for 2^8 is 0
perfect number for 2^9 is 0
perfect number for 2^10 is 0
perfect number for 2^11 is 0
perfect number for 2^12 is 0
perfect number for 2^13 is 33550336
perfect number for 2^14 is 0
perfect number for 2^15 is 0
perfect number for 2^16 is 0
perfect number for 2^17 is 8589869056
perfect number for 2^18 is 0
perfect number for 2^19 is 137438691328
perfect number for 2^20 is 0
perfect number for 2^21 is 0
perfect number for 2^22 is 0
perfect number for 2^23 is 0
perfect number for 2^24 is 0
perfect number for 2^25 is 0
perfect number for 2^26 is 0
perfect number for 2^27 is 0
perfect number for 2^28 is 0
perfect number for 2^29 is 0
perfect number for 2^30 is 0
perfect number for 2^31 is 2305843008139952128
perfect number for 2^32 is 0
perfect number for 2^33 is 0
perfect number for 2^34 is 0
perfect number for 2^35 is 0
perfect number for 2^36 is 0
perfect number for 2^37 is 0
perfect number for 2^38 is 0
perfect number for 2^39 is 0
perfect number for 2^40 is 0

That’s looking good. Guardian has found the perfect numbers up to the one for 231–1 × 230, and listed as 0 all the powers of two that doesn’t generate a prime number.

But there’s a problem hiding here. Even though we remembered to work in floating-point in our definition of perfect-by-euclid, our code will stop working soon after finding the eighth perfect number. The prime? test uses newLISP’s built-in factor function, but this handles numbers only up to 999 999 999 999 999.0 (15 digits) and then returns nil, so it’s actually surprising that we managed to find the eighth perfect number at all. Even with the primality test removed, the use of floating-point is going to deny us the chance to calculate candidate perfect numbers accurately without some major changes, such as loading in a library that handles larger numbers.

But I think that the eighth perfect number, 2305843008139952128, is more than adequate for my modest needs. After all, we’re not trying to control the world’s defense systems, here.

In the book, Colossus took a little over six seconds to calculate the next perfect number, which was, apparently:

Two to the eight one seven fourth power.

I think that’s pretty good going for a computer built in 1966. But according to this page, Colossus got it wrong, the answer being 24252. Now that’s what you don’t want – a supercomputer that controls the world’s nuclear weapons but can’t do its sums perfectly.

Advertisements

3 Comments »

  1. >To get COLOSSUS in shape for up to 2048 digit numbers try the GNU MP Bignum Library from http://www.swox.com/gmp/ The newLISP source distribution and the modules and examples package from http://newlisp.org have a module file called gmp.lsp to import the functions from GNU MP.

    Comment by don Lucio — June 29, 2006 @ 11:56 | Reply

  2. >Yes, I did investigate that idea, to see if I could reach a bit further. However, once I’d downloaded the gmp-4.2.1.tar.gz file, and expanded it, I sat there going “wow!” at the thousand or so files , with no idea what to do.(The last time I did something like this, I’d downloaded Common Lisp to try and get that working!)I can’t do that ‘makefile’ stuff. Either the library comes with an installer or I can’t use it…

    Comment by newlisper — June 29, 2006 @ 12:17 | Reply

  3. >Yes, making these things is always a hassle. Perhaps one of these days compiled versions of libgmp can be hosted on newlisp.org. At least for MAc OS X and Win32.

    Comment by don Lucio — June 29, 2006 @ 15:59 | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: