Esoteric multiplication and an (almost) failed exercise

In the multiverse of programming languages it's hard not to mention Brainf*ck, purposely written to have a minimal set of commands needed to (theoretically) program just about any problem out there thanks to its Turing completeness. The set is actually so minimal that I can include all of it, below. For non-programmers it would be useful to imagine an infinite linear magnetic tape with a read/write head able to move along it, like so:

Command    C-equivalent     Action

   >       ++ptr;           Move the head one position to the right
   <       --ptr;           Move the head one position to the left
   +       ++*ptr;          Increment the byte of data at the head position
   -       --*ptr;          Decrement the byte of data at the head position
   .       putchar(*ptr);   Write a keyed-in byte of data at the head position
   ,       *ptr=getchar();  Read and display the byte of data at the head position

   [       while(*ptr){     If the byte at the head position is zero, 
                             rather than executing the next command, 
                             jump forward to the matching ]
   ]       }                If the byte at the head position is non-zero, 
                             rather than executing the next command, 
                             jump back to the matching [

Well I mentioned it in conversations so often that it would have been a shame not to have tried it hands on. I took on a randomly chosen problem, namely writing a program that would multiply two single-digit numbers, totally out of the zone, somewhere in between spending last half an hour of the working day, thinking during my commute and in between playing and walking with the kid(s), and some half an hour debugging after the said kids went to sleep.

I got inspired by the addition code snippet, namely, [->+<], and tried to generalize it to summing several single digits in a row. My first example, [[->+<]>], expectedly resulted in an infinite loop; however a slightly more complicated [<[->+<]>>] ended up working fine.

My next challenge was how to replicate one of the operands in m*n an arbitrary number of times, i.e. to translate the memory layout [m n] into something like [m m ... m] where m would be repeated n times. After a few unsuccessful tries a working algorithm was:

1. Replicate one operand 1 time, then 2 times, then 3 times, ... all the way to m_max times. This is somewhat ugly but realizable using something like
   
   [- >>>>>>> >+>>>>>> >+>+>>>>> >+>+>+>>>> >+>+>+>+>>> >+>+>+>+>+>>
        <<<<<<<  <<<<<<<  <<<<<<<  <<<<<<< <<<<<<< <<<<<<<]
   
   
2. Replicate the second operand, decreasing it on every iteration, so that for n, zero is reached in front of n copies of m, like so
   [[- >>>>>>> + <<<<<<<] >>>>>>>-]
   
   
3. Apply our previously written "sum all numbers until zero" [<[->+<]>>]
   
   

Taken together and surrounded with some I/O, the final program ended up being

,------------------------------------------------> read and convert n
,------------------------------------------------> read and convert m
<[- >>>>>>> >+>>>>>> >+>+>>>>> >+>+>+>>>> >+>+>+>+>>> >+>+>+>+>+>>
     <<<<<<<  <<<<<<<  <<<<<<<  <<<<<<< <<<<<<< <<<<<<<] replicate m
<[[- >>>>>>> + <<<<<<<] >>>>>>>-]>> propagate n
[<[->+<]>>]<. sum n copies of m

Note that, for brevity, I have limited one of the operands to 5, however the expansion to an arbitrary number would be straightforward by increasing all stretches of >>>>>>> and increasing the number of replications from 5 to the desired maximum.

You can test it in a BrainF emulator for yourself that it works (screenshot).

For debugging you can use something like this visualizer, but note that it's heavily memory limited.

The real surprise was when I decided to compare my solution against the internet, dimly suspecting that there may be far superior alternatives out there. And indeed, as this StackOverflow discussion nicely points out, there is a MUCH more elegant code doing this. Here goes,

[
 >[>+>+<<-]
 >[<+>-]
 <<-]

Compared to this, my example above looks like such baaaad code :)

What has this taught me? Several things:

• Brainf*ck can be used as a measure of one's "internal memory capacity" for solving puzzles and math problems. Mine turns out to be pretty limited. I simply cannot, at least not quickly and entirely in my mind, come up with a program that requires you to keep track of more than 3 conditions at once (like 3 loops). Well, I kinda knew this already from my school-time profound hate of learning poems by heart.
  
• On the other hand, I was able to come up with a working solution, all by myself, in circumstances that were very very far from optimal.
  
• Learning curve is very important. Even in Brainf*ck, there are typical nuts-and-bolts programming tricks that make life so much easier once you've mastered them. I guess that just as I found it very difficult to stop thinking in higher-level languages such as (at least) the assembly, many people who never coded in their life would find it very difficult to grasp what we almost take for granted, such as i=i+1, or for-loops, or pointer arithmetic, or polymorphism, or templates.
  

I hope this exercise will make it a bit easier for me to explain programming to non-programmers.