Dc (computer program)

Registers

In addition to these basic arithmetic and stack operations, dc includes support for macros, conditionals and storing of results for later retrieval.

The mechanism underlying macros and conditionals is the register, which in dc is a storage location with a single character name which can be stored to and retrieved from: sc pops the top of the stack and stores it in register c, and lc pushes the value of register c onto the stack. For example:

3 sc 4 lc * p 

Registers can also be treated as secondary stacks, so values can be pushed and popped between them and the main stack using the S and L commands.

Strings

String values are enclosed in [ and ] characters and may be pushed onto the stack and stored in registers. The a command converts the low order byte of the numeric value into an ASCII character, or if the top of the stack is a string it replaces it with the first character of the string. There are no ways to build up strings or perform string manipulation other than executing it with the x command, or printing it with the P command.

The # character begins a comment to the end of the line.

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). So for instance we can store a macro to add one and then multiply by 2 into register m:

[1 + 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 

Conditionals

Finally, we can use this macro mechanism to provide conditionals. The command =r pops two values from the stack, and executes the macro stored in register r only if they are equal. So this prints the string equal only if the top two values on the stack are of equal value:

[[equal]p] sm 5 5 =m 

Other conditionals are >, !>, <, !<, !=, which execute the specified macro if the top two values on the stack are greater, less than or equal to ("not greater"), less than, greater than or equal to ("not less than"), and not equals, respectively. Note that the order of the operands in inequality comparisons is the opposite of the order for arithmetic; 5 3 - evaluates to 5 - 3 = 2, but 5 3 <t runs the contents of the t register because 3 < 5.

Loops

Looping is then possible by defining a macro which (conditionally) reinvokes itself. A simple factorial of the top of the stack might be implemented as:

# F(x): return x! # if x-1 > 1 #     return x * F(x-1) # otherwise #     return x [d1-d1<F*]dsFxp 

The 1Q command exits from a macro, allowing an early return. q quits from two levels of macros (and dc itself if there are less than two levels on the call stack). z pushes the current stack depth before the z operation.

Summing the entire stack

This is implemented with a macro stored in register a which conditionally calls itself, performing an addition each time, until only one value remains on the stack. The z operator is used to push the number of entries in the stack onto the stack. The comparison operator > pops two values off the stack in making the comparison.

dc-e"1 2 4 8 16 100 0d[+z1<a]dsaxp"

And the result is 131.

Summing all dc expressions as lines from file

A bare number is a valid dc expression, so this can be used to sum a file where each line contains a single number.

This is again implemented with a macro stored in register a which conditionally calls itself, performing an addition each time, until only one value remains on the stack.

dc-e"0d[?+z1<a]dsaxp"<file 

The ? operator reads another command from the input stream. If the input line contains a decimal number, that value is added to the stack. When the input file reaches end of file, the command is null, and no value is added to the stack.

{echo"5";echo"7";}|dc-e"0d[?+z1<a]dsaxp"

And the result is 12.

The input lines can also be complex dc commands.

{echo"3 5 *";echo"4 3 *";echo"5dd++";}|dc-e"0d[?+z1<a]dsaxp"

And the result is 42.

Note that since dc supports arbitrary precision, there is no concern about numeric overflow or loss of precision, no matter how many lines the input stream contains, unlike a similarly concise solution in AWK.

Downsides of this solution are: the loop stops on encountering a blank line in the input stream (technically, any input line which does not add at least one numeric value to the stack); and, for handling negative numbers, leading instances of '-' to denote a negative sign must be change to '_' in the input stream, because of dc's nonstandard negative sign. The ? operator in dc does not provide a clean way to discern reading a blank line from reading end of file.

Unit conversion

As an example of a relatively simple program in dc, this command (in 1 line):

dc-e'[[Enter a number (metres), or 0 to exit]PAP]sh[q]sz[lhx?d0=zAk.0254/.5+0kC~1/rn[ feet ]Pn[ inches]PAPdx]dx'

converts distances from metres to feet and inches; the bulk of it is concerned with prompting for input, printing output in a suitable format and looping around to convert another number.

Greatest common divisor

As an example, here is an implementation of the Euclidean algorithm to find the GCD:

dc-e'??[dSarLa%d0<a]dsax+p'# shortest dc-e'[a=]P?[b=]P?[dSarLa%d0<a]dsax+[GCD:]Pp'# easier-to-read version

Factorial

Computing the factorial of an input value, ${\displaystyle n!=\prod _{i=1}^{n}i}$

dc-e'?[q]sQ[d1=Qd1-lFx*]dsFxp'

Quines in dc

There exist also quines in the programming language dc; programs that produce its source code as output.

dc-e'[91Pn[dx]93Pn]dx'  dc-e'[91PP93P[dx]P]dx'

Printing all prime numbers

dc-e'2p3p[dl!d2+s!%0=@l!l^!<#]s#[s/0ds^]s@[p]s&[ddvs^3s!l#x0<&2+l.x]ds.x'

This program was written by Michel Charpentier. It outputs the sequence of prime numbers. Note that shorter implementation is possible, which needs fourteen symbols fewer.

dc-e'2p3p[pq]s$[l!2+ds!l^<$dl!%0<#]s#[+dvs^1s!l#x2l.x]ds.x'

Integer factorization

dc-e'[n=]P?[p]s2[lip/dli%0=1dvsr]s12sid2%0=13sidvsr[dli%0=1lrli2+dsi!>.]ds.xd1<2'

This program was also written by Michel Charpentier. ^[6]

There is a shorter

dc-e"[n=]P?[lfp/dlf%0=Fdvsr]sF[dsf]sJdvsr2sf[dlf%0=Flfdd2%+1+sflr<Jd1<M]dsMx"

and a faster solution (try with the 200-bit number 2²⁰⁰-1 (input 2 200^1-)

dc-e"[n=]P?[lfp/dlf% 0=Fdvsr]sFdvsr2sfd2%0=F3sfd3%0=F5sf[dlf%0=Flfd4+sflr>M]sN[dlf%0=Flfd2+sflr>N]dsMx[p]sMd1<M"

Note that the latter can be sped up even more, if the access to a constant is replaced by a register access.

dc-e"[n=]P?[lfp/dlf%l0=Fdvsr]sF2s2dvsr2sf4s4d2%0=F3sfd3%0=F5sf[dlf%l0=Flfdl4+sflr>M]sN[dlf%l0=Flfdl2+sflr>N]dsMx[p]sMd1<M"

Calculating Pi

An implementation of the Chudnovsky algorithm in the programming language dc. The program will print better and better approximations as it runs. But as pi is a transcendental number, the program will continue until interrupted or resource exhaustion of the machine it is run on.

dc-e'_640320[0ksslk3^16lkd12+sk*-lm*lhd1+sh3^/smlxlj*sxll545140134+dsllm*lxlnk/ls+dls!=P]sP3^sj7sn[6sk1ddshsxsm13591409dsllPx10005v426880*ls/K3-k1/pcln14+snlMx]dsMx'

A fast divide and conquer implementation of the same formula that doubles in size each iteration. It evaluates a finite number if sums as an exact rational number and only performs one large division and square root per iteration. It is fast, but will still quickly slow down as the size of the fraction increases.

dc-e'1Sk1SR13591409dSBSP426880dSQ4/3^9*SC[0r-]s-[lkE*1-k10005vlQ*lP/nAan0k]dSox[Lkd1+Skdd1+Sk3^lC*SQ2*1-d3*d*4-*dSR545140134LB+dSB*lk2%0=-SP]dszx[LRLRdLP*LPLQdLQ*SQ*+SP*SR]sc[d1-d0<yd0<yd0=z0=zlcx]sy0[lcxlox1+lyxllx]dslx'

Diffie–Hellman key exchange

A more complex example of dc use embedded in a Perl script performs a Diffie–Hellman key exchange. This was popular as a signature block among cypherpunks during the ITAR debates, where the short script could be run with only Perl and dc, ubiquitous programs on Unix-like operating systems: ^[7]

#!/usr/bin/perl -- -export-a-crypto-system-sig Diffie-Hellman-2-lines($g,$e,$m)=@ARGV,$m||die"$0 gen exp mod\n";print`echo "16dio1[d2%Sa2/d0<X+d*La1=z\U$m%0]SX$e"[$g*]\EszlXx+p | dc`

A commented version is slightly easier to understand and shows how to use loops, conditionals, and the q command to return from a macro. With the GNU version of dc, the | command can be used to do arbitrary precision modular exponentiation without needing to write the X function.

#!/usr/bin/perlmy($g,$e,$m)=map{"\U$_"}@ARGV;die"$0 gen exp mod\n"unless$m;print`echo $g $e $m | dc -e '# Hex input and output16dio# Read m, e and g from stdin on one line?SmSeSg# Function z: return g * top of stack[lg*]sz# Function Q: remove the top of the stack and return 1[sb1q]sQ# Function X(e): recursively compute g^e % m# It is the same as Sm^Lm%, but handles arbitrarily large exponents.# Stack at entry: e# Stack at exit: g^e % m# Since e may be very large, this uses the property that g^e % m == #     if( e == 0 )#         return 1#     x = (g^(e/2)) ^ 2#     if( e % 2 == 1 )#         x *= g#     return x %[    d 0=Q   # return 1 if e==0 (otherwise, stack: e)    d 2% Sa # Store e%2 in a (stack: e)    2/      # compute e/2    lXx     # call X(e/2)    d*      # compute X(e/2)^2    La1=z   # multiply by g if e%2==1    lm %    # compute (g^e) % m] SXle          # Load e from the registerlXx         # compute g^e % mp           # Print the result'`;

Environment variables

If the environment variable DC_LINE_LENGTH exists and contains an integer that is greater than 1 and less than ${\displaystyle 2^{16}-1}$, the output of number digits (according to the output base) will be restricted to this value, inserting thereafter backslashes and newlines. The default line length is 70. The special value of 0 disables line breaks.