laurent_r

This blog is an answer to the first task (Disarium Numbers) of the Week 174 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Originally, the Perl Weekly Challenge called for solutions in Perl and Raku (also known as Perl 6 at the time). But, very soon, people started to provide solutions in other “guest” languages. See for example my blog post providing solutions to the task described below in about 18 different guest languages.

One of the languages I tried for the first time last week with Sylvester’s sequence is dc, and it turned out to be much more difficult and challenging than I initially thought. One of the problems is that there is only very limited documentation on this old programming language. So I thought it might be useful to describe in some details how I solved it. I provided detailed explanations in this other blog post. I’ll now do the same with the disarium number task of this week, which is a bit more complicated.

The Disarium Number Task of Perl Weekly Challenge 174

Write a script to generate first 19 Disarium Numbers.

A disarium number is an integer where the sum of each digit raised to the power of its position in the number, is equal to the number.

For example,

518 is a disarium number as (5 ** 1) + (1 ** 2) + (8 ** 3) => 5 + 1 + 512 => 518

Disarium Numbers in Some Other Languages

The dc language is difficult and poorly documented. Before we get to it, I want to illustrate the algorithm I’ll implement with some other more traditional languages.

You can find solutions to this problem in 17 programming languages in this other blog post. I’ll show two of them below.

Disarium Numbers in Raku

sub is-disarium($num) {
    my @digits = $num.comb;
    my $sum = [+] map { $^b ** ($^a + 1) }, @digits.kv;
    return $num == $sum;
}
my $count = 0;
my $i = 0;
while $count < 19 {
    ++$count and say $i if is-disarium($i);
    $i++;
    # say "i: $i";
}

This program displays the following output:

0
1
2
3
4
5
6
7
8
9
89
135
175
518
598
1306
1676
2427
2646798

Disarium Numbers in Perl

use strict;
use warnings;
use feature "say";

sub is_disarium {
    my $num = shift;
    my @digits = split '', $num;
    my $i = 1;
    my $sum = 0;
    $sum += $_ for map {  $_ ** $i++ } @digits;
    return $num == $sum;
}
my $i = 0;
my $count = 0;
while ($count < 19) {
    say $i and $count++ if is_disarium $i;
    $i++;
}

This Perl program displays the same output as the Raku program above.

Disarium program in awk

The dc language doesn’t have the powerful string functions of Raku, Perl, or Julia. Let me provide here an awk implementation, because awk also doesn’t have these string functions. In the while loop of the is_disarium function, we use the integer division and modulo operators to get each digit of the input integer in turn. We’ll have to do something similar in dc.

function is_disarium(num) {
    n = num
    sum = 0
    len = length(n)
    while (n > 0) {
        sum += (n % 10) ^ len
        n = int(n/10)
        len--
    }
    return (sum == num)
}

BEGIN {
    count = 0
    i = 0
    while (count < 19) {
        if (is_disarium(i)) {
            printf("%d\n", i)
            count++
        }
        i++
    }
}

This awk program displays the same output as the Raku program above.

Introducing dc

According to Wikipedia), dc (desk calculator) is a cross-platform reverse-Polish calculator which supports arbitrary-precision arithmetic. Written by Lorinda Cherry and Robert Morris at Bell Labs, it is one of the oldest Unix utilities, preceding even the invention of the C programming language. dc is docucumented in section 2 of the first ediion of Bell Labs’s Unix Programmer’s Manual published on Nov 3, 1971, so dc was probably written in 1970 or latest in 1971. Like other utilities of that vintage, it has a powerful set of features but terse syntax. Traditionally, the bc calculator program (with infix notation) was implemented on top of dc.

dc is the oldest surviving Unix language program. When its home Bell Labs received a PDP-11, dc—written in B—was the first language to run on the new computer, even before an assembler.

It uses reverse Polish notation (RPN) which was also used around the same time by Hewlett-Packard pocket calculators. Actually, the main reason I am interested with dc (despite its awful worse-than-assembler syntax) is that this is essentially the type of language with which I first learned to program back in the mid-1970s with a programmable pocket calculator.

RPN is a postfix notation in which you first specify the operands and then the operator.

$ echo '5 6 + p' | dc
11

As you can see, we first input the two operands (5 and 6), and then the + operator, and finally the p operator to print out the result of the addition. Prefix your number with an underscore if you want to specify a negative number (e.g. _5 for -5)

The spaces are not needed (except between 5 and 6) but improve readability. We could have written it this way:

$ echo '5 6+p' | dc
11

dc can also be used in interactive mode:

$ dc
5 6
+
p
11
q

or:

$ dc
5 6 + p q
11

This can be quite convenient to test chunks of code and we will use that feature.

We can also use the -e (or --expression) command-line option to specify a simple program between single quotes:

$ dc -e '5 6 + p'
11

dc uses a stack to perform its operations. Stacks are very commonly used data structure in computer science. A stack is a last in / first out data structure. Think of piled-up plates. When you put a clean plate on the stack, you usually put it on top; when you take one out, you also take it from the top. So, the first plate that you take out is the last one that you added. The dc stack implements the same idea: the first piece of data you take out is the last one you added. Adding a new piece of data onto the stack is usually called a push operation, and taking out one piece of data from the stack is called a pop operation.

The various commands above can be understood as follows:

$ dc
5   # push 5 to stack
6   # push 6 to stack
f   # display stack (displays 6 and 5). Useful for debugging
6
5
+   # pop two items from stack, add them and push result to stack
p   # print top item of the stack (prints 11)
11
q   # quit

Note that the # sign indicates the beginning of a comment (the rest of the line is ignored).

For full details on the dc syntax, please consult the dc GNU manual. We will describe here only the most common commands, those that we are likely to use for our program. The best tutorial I have found on dc is the Wikipedia dc page).

Printing Commands

p   Prints the value on the top of the stack, not altering the stack. 
n   Prints the value on the top of the stack, popping it off
f   Prints the entire contents of the stack without altering anything.

Stack Control

c   Clears the stack, rendering it empty
d   duplicate the value on top of the stack
r   Reverses the order of (swaps) the top two values on the stack.

Registers

dc provides at least 256 memory registers, each named by a single character. You can store a number in a register and retrieve it later.

sr  Pops the value off the top of the stack, stores it in register r. 
lr  Copies the value in register r, and pushes it onto the stack.
    This does not alter the contents of r.

Each register also contains its own stack. The current register value is the top of the register’s stack. If you want to use a register r as a stack, use Sr (with uppercase S) to push the top of stack value to r, and Lr (with uppercase L) to pop a value from r and push it on the main stack. We will not use the stack features of registers in this blog post.

Arithmetic

+   Pops two values off the stack, adds them, and pushes the result.
-   Pops two values, subtracts the first one popped from the second 
    one popped, and pushes the result. 
*   Pops two values, multiplies them, and pushes the result.
/   Pops two values, divides the second one popped from the first 
    one popped, and pushes the result. The number of fraction digits 
    is specified by the precision value. Default is integer division.
%   Pops two values, computes the remainder of the division that 
    the `/` command would do, and pushes that.
^   Pops two values and exponentiates, using the first value popped 
    as the exponent and the second popped as the base.

Strings

dc can operate on strings as well as on numbers. The only things you can do with strings are print them and execute them as macros (which means that the contents of the string are processed as dc commands).

For example, to print twice a string in the interactive mode:

$ dc
[Hello wolrd!]p
Hello wolrd!
p
Hello wolrd

or:

$ dc
[Hello wolrd!]pp
Hello wolrd!
Hello wolrd!

Now, let’s try to write a simple string containing dc statements to increment by 2 the value on the stack, and to run it as a macro (using the x command):

$ dc
20          # pushes 20 to stack
[2 + p] x   # [2 + p] is a string that means "push 2 to stack,
            # add the two top items of the stack and print result.
            # x runs the [2 + p] sting as a macro
22
q

Both registers and the stack can hold strings, and dc always knows whether any given object is a string or a number.

[ch] Makes a string containing "ch" and pushes it on the stack.
x   Pops the value from the top of the stack and executes it as a macro
>r  Pops two values off the stack and compares them assuming they are 
    numbers, executing the contents of register r as a macro if the 
    original top-of-stack is greater
<r  Similar but invokes the macro if the original top-of-stack is less
=r  Similar but invokes the macro if the original top-of-stack is equal

Macros

Macros are then implemented by allowing registers and stack entries to be strings as well as numbers. A string can be printed, but it can also be executed (i.e. processed as a sequence of dc commands). For instance, we can store a macro to add 3 and then multiply by 2 into register m:

[3 + 2 *] sm

and then (using the x command which executes the top of the stack) we can use it like this:

3 lm x p

This displays the following:

$ dc -e '[3 + 2 *] sm 3 lm x p'
12

For better understanding, this is a detailed account of what’s going on:

[    # start of macro definition
  3  # push 3 to stack
  +  # pop 2 values off the stack, add them and store result on stack
  2  # push 2 on stack
  *  # pop 2 values off the stack, multiply them, store result on stack
]    # end of macro definition
sm   # store the macro just defined in register m
3    # push 3 on stack
lm   # copy value in register m (the macro) onto the stack
x    # run the macro
p    # print the result (top of the stack)

Conditionals and Loops in dc

The =, >, !>, <, !<, != conditionals execute the subsequent macro when the two top values of the stack are equal, larger than, not larger than, etc. For example, in:

$ dc -e '[[smaller than]p] sm 6 5 <m'
smaller than

the macro stored in m runs (and prints “smaller than”) because 5 is smaller than 6. The < pops 5 and then 6 from the stack and runs the macro in register m because the first popped value (5) is smaller than the second popped value.

Let’s look at a simple countdown in this page in the Bash Hackers Wiki:

dc << EOF
[ li       # put our index i on the stack 
  p        # print it, to see what's going on
  1 -      # we decrement the index by one
  si       # store decremented index (i=i-1)
 0 li >L   # if i > 0 then execute recursively L
] sL       # store our macro with the name L
10 si      # let's give to our index the value 10
lLx        # and start our loop
EOF 

10
9
8
[ Lines omitted for brevity]
2
1

Basically, the macro is called a first time, and then calls itself recursively so long as the condition is satisfied.

Disarium Numbers in dc

Remember that we want to write something similar to the is_disarium function of our above-described awk program:

function is_disarium(num) {
    n = num
    sum = 0
    len = length(n)
    while (n > 0) {
        sum += (n % 10) ^ len
        n = int(n/10)
        len--
    }
    return (sum == num)
}

Our program will be composed essentially of four macros calling themselves or each other, and just a few additional code lines to start the whole process.

The Length Macro

The above is_disarium function uses the awk built-in length() function. There is no such built-in function in dc. So our first task will be to write our own length macro.

The way this macro will work is that we’re going to repeatedly divide (integer division) the input number by 10, until we get to 0. At each step through the process, we increment the length (register l) by one.

The length macro itself is stored in the L register, and the length “variable” in register l.

[10      # pushes 10 to stack
 /       # divides input by 10 and stores result on stack
 ll      # pushes length on stack
 1+      # adds one to stack (length)
 # p     # prints intermediate length (for debugging)
 sl      # saves length to register l
 d       # duplicates value (number) on top of stack
 0       # pushes 0 to stack
 <Lx     # executes recursively length macro (L) if number > 0
] sL     # end of macro, stores it in L

889 sn   # stores some input number in n
ln       # pushes number to stack
0sl      # stores 0 in register l (length)
lLx      # runs the macro once to start the loop
llp      # prints length final value

The last five lines in the code above (after the blank line) are not part of the macro, they are just some code to set up the environment before calling the macro: start with an input number (889 in the above example), initialize the length (register l) to 0, invokes the macro (stored in register L), and prints the length.

With an input number of 889, this program correctly prints out 3.

The Disarium Macro

This macro is more or less equivalent to the is_disarium function’s while loop of the awk program:

while (n > 0) {
    sum += (n % 10) ^ len
    n = int(n/10)
    len--
}

The disarium macro computes the number modulo 10, then computes the result to the length power, adds the obtained value to the sum so far; it also divides the number by 10 (integer division) and decrements the length by 1. At the end, it calls itself recursively if the resulting number is larger than 0.

The disarium macro is stored in register D. The sum is stored in register s, the length in register l, and the input number in register n.

[d      # duplicates value (number) on top of stack
10      # pushes 10 to stack
%       # pushes (number % 10) to stack
ll      # pushes length to stack
^       # computes (n % 10) ^ len
ls      # pushes sum to stack
+ss     # computes new sum and stores it in s
10/     # integer division number / 10
ll      # pushes length on stack
1-      # subtract 1 froml length
sl      # stores new length in l
d       # duplicates value (number) on top of stack
0       # pushes 0 to stack
<Dx     # executes recursively disarium macro (D) if number > 0
] sD    # stores disarium macro in D

88 sn   # stores number in n
ln      # pushes number to stack
0sl     # stores 0 in register l (length)
lLx     # runs the length macro
0ss     # initializes sum to 0
cln     # clear stack and pushes number onto it
lDx     # runs the Disarium macro
lsln    # pushes sum and number
f       # display stack (sum and number)

The 10 last code lines (after the blank line) are not part of the macro, but are needed to make a full dc program that can be tested independently (well you’ll also need the length macro described above). They initialize the input number to 88, the sum to 0, and the length to 0. Then we run the length macro (stored in L) and the disarium macro. At the end, we push the sum and the input number to the stack and can verify whether they are equal (in which case the input number is a disarium number) or not. With the input value of 88, the program displays:

88
72
0

The input number (88) and the sum (72 = 8 * 8 + 8) are not equal, so 88 is not a disarium number.

If we change the input number to 89, we get the following output:

89
89
0

The input number (89) and the sum (89 = 9 * 9 + 8) are equal, so 89 is a disarium number.

The Iteration Macro

We need to iterate over the subsequent integers and, for each of them, call the length macro and then the disarium macro to find out whether it is a disarium number.

The macro stores the current iteration variable into the number register (this is the number we will test), initializes length to 0, runs the length macro, initialize sum to 0 and runs the disarium macro once. Then it pushes sum and number to stack and compares them. If they are equal (input number is a disarium number), it runs the printing macro (see below). Finally, it compares the disarium number with 18, and calls itself recursively if the counter is smaller than 18.

The iteration macro is stored in the I (capital i) register. The sum is stored in register s, the length in register l, the input number in register n, the iteration variable in register i, and the disarium number counter in register c.

[li sn  # Stores iteration variable in number register
ln      # pushes number to stack
0sl     # stores 0 in register l (length)
lLx     # runs the length macro
0ss     # inititialize sum to 0
cln     # clear stack and pushes number onto it
lDx     # runs the Disarium macro once
lsln    # pushes sum and number
=P      # runs the printing macro if numbers are equal
li      # loads iteration variable
1+si    # increments iteration variable
lc18    # pushes counter and 18 on stack
>Ix     # runs recursively iteration macro if counter < 18
] sI    # end of iteration macro, stores it in I

We cannot run this macro at this point, because we need a small additional macro, the printing macro.

The Printing and Counting Macro

I’ve previously called it “printing macro” for the sake of brevity, but it is really a printing and counting macro. This macro runs only when input number and the computed sum are equal (i.e. when we have a disarium number). In that case, we need to do two things: print out the disarium number and increment by 1 the disarium number counter (so that we know when to stop the iteration macro).

The printing and counting macro is stored in the P register. The disarium number counter is stored in the c register, and the input number in register n.

[lc1+sc # increments disarium number counter
lnp     # print number
]sP     # Stores printing macro in P

The Final Disarium Number Program in dc

We can now put together all the pieces seen so far.

The macros are stored in upper-case letter registers:

• L: length of input number macro

• D: Disarium macro

• I: Iteration macro

• P: Printing and counting macro

The “variables” are stored in lower-case letter registers:

• n: Input number

• c: Disarium number counter

• l: Length of input number

• s: Sum

• i: Iteration variable

This is the full dc program:

# Macro for computing the input number length
[10      # pushes 10 to stack
 /       # divides input by 10 and stores result on stack
 ll      # push length on stack
 1+      # add one to stack (length)
 sl      # saves length to register l
 d       # duplicates value (number) on top of stack
 0       # pushes 0 to stack
 <Lx     # executes recursively length macro (L) if number > 0
] sL     # end of macro, store it in L

# Disarium macro
[d      # duplicates value (number) on top of stack
10      # pushes 10 to stack
%       # pushes (number % 10) to stack
ll      # pushes length to stack
^       # computes (n % 10) ^ len
ls      # pushes sum to stack
+ss     # computes new sum and stores it in s
10/     # integer division number / 10
ll      # pushes length on stack
1-      # subtract 1 froml length
sl      # stores new length in l
d       # duplicates value (number) on top of stack
0       # pushes 0 to stack
<Dx     # executes recursively disarium macro (D) if number > 0
] sD    # stores disarium macro in D

# Printing and counting macro
[lc1+sc # increments disarium number counter
lnp     # print number
]sP     # Stores printing macro in P

# Iteration macro
[li sn  # Stores iteration variable in number register
ln      # pushes number to stack
0sl     # stores 0 in register l (length)
lLx     # runs the length macro
0ss     # inititialize sum to 0
cln     # clear stack and pushes number onto it
lDx     # runs the Disarium macro once
lsln    # pushes sum and number
=P      # runs the printing macro if numbers are equal
li      # loads iteration variable
1+si    # increments iteration variable
lc18    # pushes counter and 18 on stack
>Ix     # runs recursively iteration macro counter < 18
] sI    # end of iteration macro, stores it in I

# Main
0si     # Initialize iteration variable
0sc     # Initialize disarium numbers counter
lIx     # running iteration macro the first time

As you can see, the program consists of the four macros defined previously, plus just 3 code lines (the “Main” part) to initialize the iteration variable, initialize the disarium number counter and launch the iteration macro.

This program displays the following output:

$ dc ./disarium.dc
0
1
2
3
4
5
6
7
8
9
89
135
175
518
598
1306
1676
2427

But, of course, formatting the program with abundant spaces and comments as above is way too easy. Real programmers will prefer this one-liner version (spread over two lines for formatting reasons):

$ dc -e '[10/ll1+sld0<Lx]sL[d10%ll^ls+ss10/ll1-sld0<Dx]sD[lc1+sc
lnp]sP[lisnln0sllLx0ssclnlDxlsln=Pli1+silc18>Ix]sI0si0sclIx'
0
1
2
3
[Lines omitted for brevity
598
1306
1676
2427

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on July 31, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.