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

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:

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.

Comments

comments powered by Disqus