basic

3 posts

BASIC - Narcissistic numbers

For our sample BASIC program, let's try to implement the Narcissistic numbers problem from Rosetta Code.

A narcissistic number is a integer where the sum of each digit raised to the power of the number of digits equals the number itself. For example, 153 is narcissistic: it has three digits 1, 5 and 3, and 1³ + 5³ + 3³ = 1 + 125 + 27 = 153.

The goal of the program is to print the first 25 narcissistic numbers.

First version

The algorithm is fairly simple

  • Look at each positive integer in turn
  • Find number of digits
  • Sum up each digit raised to the power of the number of digits
  • Compare to the number and if equals, print it
  • Stop after 25 narcissistic numbers found

To find the number of digits we can convert the number to a string and take its length. To extract each digit we need to divide by 10, take the integer part and multiply by 10 again and subtract the original number as there is no modulus operator.

100 rem UM BASIC program to print the first 25 narcissistic numbers  
110 let c = 0                /* Count of narcissistic numbers found  
120 *  
130 rem Start of loop to find and print narcissistic numbers  
140 for n = 0 to 10000000    /* Number to check for narcissism  
150 if c >= 25 then: stop    /* End after 25 numbers  
160 *  
170 let nn = nts(n)          /* Number as a string  
180 let d = len(nn)          /* Number of digits  
190 let x = n                /* Copy of number  
200 let y = 0                /* Result of narcissistic calculation  
210 *  
220 rem Start of loop to calculate narcissistic number  
230 for i = 1 to d           /* For each digit  
240 let x1 = int(x/10)       /* Get all but last digit of x  
250 let x0 = x - (10 * x1)   /* Get last digit of x  
260 let y = y + (x0 ** d)    /* Accumulate digit ** num digits  
270 let x = x1               /* Shift off last digit from x  
280 next i  
290 *  
300 if int(y) <> n then 400  /* Not a narcissistic number, jump next  
310 print n                  /* Print narcissistic number  
320 let c = c + 1            /* Increase count found  
330 *  
400 next n                   /* Try next number  
410 *  
500 stop                     /* Fall through  

And here's the output:

0 1 2 3 4 5 6 7 8 9 153 370 371 407 1634 8208 9474  
54748 92727 93084 548834 1741725 4210818 9800817 9926315  

Unfortunately this takes a long time to run - 6 minutes and 46 seconds of CPU time - so let's see how we can improve this.

Faster version

There are several optimisations we can try:

  • Precompute a ** b, for a and b between 0 and 9, as we do this for each digit in the inner loop and it is likely to be an expensive operation. The precomputed powers are stored in a 2D matrix p by the routine starting on line 600. This saves 123 seconds.
  • Exit early from the calculation inner loop when the accumulated total is larger than the number being tested. This saves 32 seconds.
  • Use integer comparison to find the number of digits rather than converting to a string. This saves 54 seconds.

Here's the final listing, taking 3m17s. There are probably further optimisations that can be made - any suggestions?

100 rem UM BASIC program to print the first 25 narcissistic numbers  
110 rem Second, faster version  
120 *  
130 let c = 0                /* Count of narcissistic numbers found  
140 dim p(9, 9)              /* p(x, y) will contain x ** y  
150 gosub 600                /* Precompute p  
160 *  
170 rem Start of loop to find and print narcissistic numbers  
180 for n = 0 to 10000000    /* Number to check for narcissism  
190 if c >= 25 then: stop    /* End after 25 numbers  
200 *  
210 gosub 700                /* Get number of digits in d  
220 let x = n                /* Copy of number  
230 let y = 0                /* Result of calculation  
240 *  
250 rem Start of loop to calculate narcissistic number  
260 for i = 1 to d           /* For each digit  
270 let x1 = int(x/10)       /* Get all but last digit of x  
280 let x0 = x - (10 * x1)   /* Get last digit of x  
290 let y = y + p(x0, d)     /* Accumulate digit ** num digits  
300 if y > n then 400        /* Bail out if too big already  
310 let x = x1               /* Shift off last digit from x  
320 next i                   /* Loop for next digit  
330 *  
340 if y <> n then 400       /* Not a narcissistic number, jump next  
350 print n                  /* Print narcissistic number  
360 let c = c + 1            /* Increase count found  
370 *  
400 next n                   /* Try next number  
410 *  
500 stop                     /* Fall through  
510 *  
520 *  
599 rem Subroutine to populate p(a, b) with a ** b  
600 for a = 0 to 9           /* Digit  
610 p(a, 0) = 0              /* a ** 0 = 0  
620 p(a, 1) = a              /* a ** 1 = a  
630 for b = 2 to 9           /* Power to raise to  
640 p(a, b) = p(a, b-1) * a  /* Calc next power in series  
650 next b                   /* Loop power  
660 next a                   /* Loop digit  
670 return  
698 *  
699 rem Subroutine to get number of digits in n  
700 if n >= 1000000 then 800  
710 if n >= 100000  then 810  
720 if n >= 10000   then 820  
730 if n >= 1000    then 830  
740 if n >= 100     then 840  
750 if n >= 10      then 850  
760 goto 860  
800 let d = 7  
801 return  
810 let d = 6  
811 return  
820 let d = 5  
821 return  
830 let d = 4  
831 return  
840 let d = 3  
841 return  
850 let d = 2  
851 return  
860 let d = 1  
861 return  

Closing thoughts on BASIC

The strength and weaknesses of the BASIC language are that it is, well, basic. With only a handful of features it is hard to get lost, but doing anything more complex than the above would be painful. From a modern programming viewpoint, the need for line numbers, restrictions on variable names and lack of types makes it quite different from what we would do now so despite some nostalgia for 80s home computing I can see why this is a bad choice for even a beginner's programming language today. But it's also clear to see how revolutionary BASIC was when first introduced and how it opened the door to programming for a whole new set of people.

Likewise, the self contained environment for UM BASIC makes it easy to start writing code without having to know much about MTS, but you lose the access to useful tools like a full screen editor. I think this, and the fact that better languages were available, explains why BASIC was not a popular choice for general users of MTS - according to Introduction to programming and debugging in MTS, only 2% by frequency of use in 1984.

Further information

There's more on the mathematics of narcissistic numbers at Wolfram MathWorld.

Source code for these programs can be found on Github.

BASIC - Language features

Like many who grew up in the 1980s, my first programming language experience was on BASIC (on the VIC-20, in my case) and although I haven't used it for 30 years I felt right at home.

The Wikipedia article defines three broad generations of BASIC

  • Early versions on mainframes, 1964-1980
  • Home computer ROM BASIC, 1980-1990
  • More structured versions on PCs, 1990-date

MTS BASIC falls firmly in the first camp, with a limited number of keywords, restrictions on numbers and names of variables, but with support for matrix operations that was not present in later versions of the language.

The below is a quick look at the main features in MTS BASIC; see the Further Information section for more complete guides.

Program format

Each line of the program must start with a line number - note this is different from line numbers in MTS native files and only integers are allowed.

Full line comments can be introduced with REM or *. To add a comment that lasts until the end of the line you can use /* (very confusing to C programmers!).

10 rem This is a comment  
20 * This also  
30 let x = 3 /* Line comment  
40 let y = 4  

Types and variables

BASIC has two data types (only one less than Javascript!) - floating point numbers and strings. Numeric variable names must start with a letter followed by one or two numbers; string variables names must have two identical letters followed by an optional number (ie AA - ZZ, AA1, AA2 etc). Maximum length of strings is 127 characters. Variables can be initialised with LET:

10 let A = 1.23  
20 let A1 = 3  
30 let AA = "Hello world"  

You can have arrays and matrices of numbers which can be indexed using (), eg a(1) or b(2,3). The size can be set using the DIM statement but if not given they are size 10. Indices start at 0. The below will print 100.

10 dim a(2,2)  
20 a(1,0) = 100  
30 a(1,1) = 200  
40 print a(1)  

Strings are implemented as vectors of cells containing strings, so AA is the same as AA(0) and you can also access AA(1), AA(2) etc.

Statements

INPUT will prompt for the user to enter a value which will be assigned to a variable; PRINT will display a variable or expression, using ; or , to control formatting.

  10 input a, b
  20 print a; b, (a+b)/2

: run
? 10
? 20
  10 20          15

INP and OUT are like INPUT and PRINT but also return the value assigned to the variable.

GOTO x will jump unconditionally to line x. Note you can't GOTO a non-executable line like a comment. There is also a rather hairy computed GOTO where they program will jump to a line based on the result of an expression.

10 goto 40  
20 print "This will be printed second"  
30 stop  
40 print "This will be printed first"  
45 let a=2  
50 goto (60,60,20,60) a+1  
60 print "This will not be printed"  

The IF .. THEN statement will calculate an expression and then either jump to another line or execute a statement. Note that there is no ELSE.

10 let a = 5  
20 if a > 1 then 40  
30 print "This will not be printed"  
40 if a <> 5 then: print "This will not be printed"  
50 if a = 5 then: print "This will be printed"  

Simple loops can be done with FOR .. NEXT with an optional STEP.

10 for i = 1 to 10  
20 for j = 0 to 10 step 2  
30 x = x + (i*j)  
40 next j  
50 next i  
60 print x  

GOSUB x will call a subroutine at line x; execution will resume from the current line when a RETURN statement is found.

It's possible to temporarily transfer execution to another program with CALL or permanently transfer with CHAIN.

Simple functions can be defined with DEF, eg DEF FNS(x)=x*x for a square function. Only one parameter is allowed and the function name can only be a single character A-Z.

STOP will end a program and PAUSE will prompt the user for input before continuing.

Library functions

BASIC comes with a number of library functions. Note that you have to assign results of these functions to variables rather than printing them directly - so in the example below I can't do PRINT CLS().

String operations include conversion to numbers (STN) and back (NTS) along with access to the surrounding environment such as UID for user ID and CLS for time of day.

10 let ss = cls()  
20 print ss  
30 let ss = uid()  
40 print ss  
: run
 0:59:02
 ST01

Numeric functions include mathematical support functions like ABS() and SIN().

Matrix and vector support is especially powerful, with the ability to enter, print and do matrix operations. The below will prompt for a 2x2 matrix, add it to its transpose and then print it.

10 dim x(2,2), y(2,2), z(2,2)  
20 mat input x  
30 mat let y = trn(x)  
40 mat let z = x + y  
50 mat print z  
: run
? 1,2
? 3,4
  2              5             
  5              8             

There is also limited support to read and write files - but these are special data files attached to the BASIC environment rather than general MTS files.

And that's pretty much it for BASIC. In the next post we'll look at a larger example of a MTS BASIC program.

Further information

MTS Volume 10 offers a complete description of the BASIC language and environment.

BASIC - Introduction

As a gentle start to this series we'll look at something suitably basic - the BASIC language itself.

The BASIC language

Originally developed at Dartmouth in 1964, BASIC is a simple unstructured language influenced by FORTRAN and ALGOL. It was designed to be an easy to learn language for people who were not experienced computer scientists. It achieved wide popularity in the 1980s when it was included in many home computers and in the 1990s-2000s was in common use on Windows as Visual Basic and Visual Basic.NET, which included object orientated features.

BASIC on MTS

The version of BASIC in MTS was developed at the University of Michigan and appears to date from the early 1970s, with the first version appearing in D2.0. The implementation is close to Dartmouth Basic, with some minor changes such as using ** instead of for exponentiation.

Prerequisites

No special installation instructions to get BASIC running - just do the standard D6.0 setup as described in this guide and then sign on as a regular user such as ST01.

Running BASIC

Type $run *BASIC to start. Unlike other compilers on MTS, this will put you in a self-contained environment where you can create, run, debug and organise BASIC programs.

When you start BASIC you will see the : prompt. Here you can enter commands, starting with /, to control the BASIC environment. Use /open NAME to create a new program called NAME. This will start a new file in memory that will last for the rest of the session; to save the current version to disk do /save. Note the files are saved in a special, sequential format that can only easily be read by BASIC.

To enter the actual program you can type lines starting with a line number. To correct lines you can retype it; there are also / commands such as /alter to do simple line editing. Type a line number on its own to delete it. As it is a separate environment you can't use tools like $edit to visually edit files; you could create a text file outside of BASIC and use /include FILE to import it, however.

To view the code, type /list; to execute the program, type /run. BASIC will then compile the source file and if there are no syntax errors start to execute it. If there are any run time errors you will enter the debugger which has a > prompt. Here you can /display variables, change them with /modify and either /continue or /stop execution.

To leave BASIC, type /bye, remembering to /save first if you want to keep your program. When you start BASIC again, use /permcatalog to view the programs on disk and /open to load one.

Hello world

Here's a terminal log of how to start BASIC and create a simple program.

# $run *basic
: /open hello
&  "HELLO" has been created.
: 10 for i = 1 to 5
: 20 print "Hello World!"
: 30 next i
: /run
  Hello World!
  Hello World!
  Hello World!
  Hello World!
  Hello World!
+  Program Ends
: /save
& Done
: /bye
&  Off at 21:53:35 on 11-17-14

In the next post we'll look at BASIC language features in more detail.

Further information

See the Wikipedia article for more details on the history of BASIC. In 2014, Dartmouth created the website BASIC at 50 which has some interesting background on the creation of the language. TIME did an article looking at BASIC's legacy.

For the MTS version, MTS Volume 10 offers a complete description.

There's also a great beginner's introduction called "Fundamental Use of the Michigan Terminal System (Including Simple MTS BASIC)" by Thomas J. Schriber from the UM Business School, which is available in the Hathi Trust archives or on Google Books.