Recently I stumbled across a question of “write a program to calculate the number of trailing zeros in n!” For example, 5! = 1 * 2 * 3 * 4 * 5 = 120. Thus, the number to get out of the program is 1. 10! is 3628800, and should get the result of 2.

Writing this in Java or C or Perl has its set of challenges and mostly revolves around knowing a particular trick (well, not really a trick, but rather some math that makes this a trivial program). Thus, it really isn’t that challenging of a problem.

However, doing this the naive way with a less familiar language can be a good challenge. For math challenges, dc is the tool that I enjoy.

dc uses a stack based language that is probably most familiar to people from the HP calculators of old that used reverse Polish notation. Instead of writing 2 + 2, instead one writes 2 2 +. There is a lot more that can be said about this, but it makes it very easy to implement a language, all you need is a stack.

So, lets write some code. First, we need to store the answer somewhere. The register ‘a’ is as good a place as any. It needs to be initialized before it can be used: 0 sa This stores the value 0 into the register a.

Because of some of the particulars of the language and conditionals, I need a way to increment the value in register a. This is done setting up a macro. Macros are strings that are stored in a given register. Strings are enclosed in []. To load a register onto the stack, the command sequence is lx where x is the register. So, [la 1 + sa] si This creates a macro that loads a, adds one to it, and stores the result (top item on the stack) back into register a. This macro is stored in register i.

Now we get into the fun parts… macros, logic and recursion.

The factorial macro is one I copied from somewhere awhile back before I really knew how it worked. [d 1 - d 1 1<F *]sF We take the top item on the stack and duplicate it (with d). Then we subtract one from that, and duplicate that. Then we push 1 onto the stack and if 1 is less than the item before on the stack, we call macro F… and then we multiply the top two items on the stack. This macro is stored in register F.

Thats a lot to take in in one go. Lets do 3!:

1. So, the stack looks like 3
2. Then we duplicate it… 3 3
3. Push 1 on the stack 3 3 1
4. Subtract top from the next and push that result back on the stack 4 3
5. Duplicate the top item 3 2 2
6. Push 1 on the stack 3 2 2 1
7. Pop top 2, if top is less than the next (1 < 2?), call F. Stack is 3 2
8. At this point we’re looping back to instruction 1… but the stack is 3 2
9. Duplicate the top item 3 2 2
10. Push 1, subtract it, 3 2 1
11. Push 1, test if 1 < 1? No? Ok…
12. Stack at this point is 3 2 1 – multiply top two items: 2 1 * and push that back on the stack. Stack is 3 2
13. Now, the multiply that was ‘left hanging’ from step 7 above, is called and 3 2 * pushes 6 on the stack

And there you have it… stack based factorial.

Now for the fun one.

The short form of this is “if the number modulo 10 is 0, increment a (that first macro), divide the number by 10, and do it again”

This is done with duplicate the number on the stack. 10 % takes the top number and does a modulo 10, and then duplicates *that* value (we need to do two tests against this value – each test consumes it once). If you started with 120, you’ve got 120 0 0 at this point. Push another 0 on there, and if they are the same call that increment macro.

Swap the two numbers… so 120 0 becomes 0 120. The code can really only work with the top number on the stack. Then divide it by 10 and we’ve got 0 12 and swap the two back giving 12 0. Then do another test for 0 and call the l macro, which this is what it is… this time with only 12 on the stack.

Then, all this needs to be executed…

lFx will load the F macro (factorial), and run it. Then llx runs the l macro… and then lap loads the a register (answer) and prints it.

Phew.

Putting it all together, this looks like:

You can run this on the command line with less spaces as:

That first -e 133 puts 133 on the stack, which sits around there until that lFx which runs it. Or you could stick a ‘?’ in front of the program to read the number from standard input.