(archive 'newLISPer)

December 29, 2005

Easy peasy

Filed under: newLISP — newlisper @ 21:37
Tags:

One of the great things about being a Dad is that you get the chance to share the excitement and enthusiasm that young children have for the world around them – at least, before they grow cynical and jaded like us adults. Kids are full of wonder, and some of them are even interested in numbers and sums – for a while! Computers can be great tools for exploring.

For fun I decided to use newLISP to show some simple primary school mathematics to a receptive audience (of one). newLISP is actually quite suitable for this purpose, with its fast, simple, interactive, and non-mathematical syntax, and it was challenging for me to come up with the answers on the spot.

Perhaps only younger children would watch with wonder as the following expression scrolls inexorably through to the end:

(sequence 1 1000000)

But it is a real million! “Wow” was the appreciative response. It’s the printing and scrolling that takes the time, rather than the counting, on my machine, because:

(time (sequence 1 1000000)) ;- 279 milliseconds

although I think the computer’s cheating if it’s not printing the numbers out.

The sequence function also lets you specify a step other than 1 as an optional third argument.

(sequence 1 1000 7)

This is good for making sure that the computer knows its tables.

sequence has a big brother, series, which is good for showing what happens when you multiply rather than add. Sensibly, you don’t specify the upper limit this time, just the multiplying factor and the number of repeats:

(series 2 2 30)
;-> (2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384
32768 65536 131072 262144 524288 1048576 2097152
4194304 8388608 16777216 33554432 67108864 134217728
268435456 536870912 1073741824)

The factor function is extremely quick, but didn’t supply the information that the audience was hoping to see:

(println (factor 100))
;-> (2 2 5 5)

with cries of “What about 10, 25, and 50?”! Perhaps schools teach factors differently. But this version met with approval:

(define (factors n , factor-list)
    "return a list of all the factors of n"
(cond
    ((< n 4) nil ) ; don't bother if n is 1, 2, or 3
    (true
        (let (limit (/ n 2)) ; only do up to n/2
        (for (x 2 limit)
            (if (= (% n x) 0) ; add x to list of factors if no remainder
                (push x factor-list -1))))
            factor-list))) ; return list
(for (x 1 1000) (println x " " (factors x)))
;->
1 nil
2 nil
3 nil
4 (2)
5 nil
6 (2 3)
7 nil
8 (2 4)
9 (3)
10 (2 5)
11 nil
12 (2 3 4 6)
...

There’s been some discussions here, about whether 1 is a factor of everything, whether 1 is prime, and whether zero is even, to name just a few. You can’t always convince young people that these questions have been resolved by respected authorities hundreds of years ago. Notice the fudging in the first cond term, which allowed me to produce the required results.

But we can use the official factor function to write a function that tests whether a number is prime (another source of fascination for the budding young mathematician).

(These test functions are called predicates. newLISP provides a set of predicate functions whose names end with question marks. We can list them by using the filter function, looking through a list of symbols for names ending with “?”:

(println (filter (lambda (s) (ends-with (name s) "?" )) (symbols 'MAIN)))
; ->
(? NaN? array? atom? context? directory? empty? file? float? integer?
lambda? legal? list? macro? nil? primitive? quote? string? symbol?
true?)

I seem to remember that predicates in classic Lisp end with the letter “p”. newLISP’s idea of using a question mark seems a more natural solution.)

But back to the prime numbers. A prime number predicate can be just a simple test of how many numbers are returned by factor. All the prime numbers return themselves when tested with factor, so we see if length is equal to 1:

(define (prime? n)
    (=      (length (factor n))
            1))

And then we can easily find all the prime numbers up to a million:

(for (n 1 1000000)
    (println n " " (prime? n)))

which also takes the computer a minute or two! An internet search revealed that some people spend a lot of effort trying to calculate prime numbers quickly, so I think we should stop now.

Advertisements

1 Comment »

  1. >I seem to remember that predicates in classic Lisp end with the letter “p”. newLISP’s idea of using a question mark seems a more natural solution.I think that Scheme(rs) started using ‘?’ to end names of predicates — Lutz must have picked up on that.

    Comment by Rick Hanson — April 30, 2006 @ 02:04 | 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: