172 lines
7.2 KiB
Sed
172 lines
7.2 KiB
Sed
# Single step in multiplying two base10 numbers using only regexes


#


# Copyright (C) 2018 Mike Gerwitz


#


# This program is free software: you can redistribute it and/or modify


# it under the terms of the GNU General Public License as published by


# the Free Software Foundation, either version 3 of the License, or


# (at your option) any later version.


#


# This program is distributed in the hope that it will be useful,


# but WITHOUT ANY WARRANTY; without even the implied warranty of


# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


# GNU General Public License for more details.


#


# You should have received a copy of the GNU General Public License


# along with this program. If not, see <http://www.gnu.org/licenses/>.


#


# This script demonstrates how to multiply two 0padded 3digit base10


# numbers using nothing more than a series of regular expressions. It


# involves adding and subtracting from a series of registerseach


# invocation of the script performs a single addition step toward the final


# result.


#


# For a lighter introduction, first look at `base10inc.sed', which shows


# how to implement a basic increment on a single 3digit base10 number.


#


# This script uses four 3digit registers delimited by a single space (for


# legibility; no delimiters are necessary since the registers are


# fixedwidth). They are laid out as follows (extra spaces added for


# illustration purposes):


#


# 001 002 003 004


# 1st operand/ 2nd operand copy of accumulator src


# accumulator 1st operand (decrementing)


#


# The first and second registers hold the first and second operands (the two


# numbers to multiply). The first register doubles as the accumulatorit


# will hold the result of the calculation at each step. The third register


# is always a copy of the first operand; this is necessary since the first


# register is always changing. (Alternatively we could have made the third


# register the accumulator, but that makes the regexes a little messier.)


# The fourth register is the value that the accumulator takes _from_it


# initially is a copy of register three and is decremented at each


# step. The accumulator is incremented at each step.


#


# Once register four reaches zero, it is reset to the value of register


# three and register two is decremented. Once register two reaches `001',


# the calculation is finished and all but the first register (holding the


# accumulated result) are discarded.


#


# This script is designed to be run in a loop, allowing each step of the


# process to be observed, saved, and manipulated. This could easily be


# changed to use sed's branching features to loop and produce the result in


# a single invocation, but that makes introspection difficult (and the


# output a whole lot less interesting).


#


# TO USE: Provide two 0padded base10 integers delimited by a space, or a


# previous state of the system (its output). For example, to perform 5*3,


# provide this initial input:


#


# 005 003


#


# The output of the first invocation will be:


#


# 006 003 005 004


#


# To invoke with the animation script, you might do:


#


# $ ./animate base10mul.sed <( echo 005 003 )


#


# The process is further detailed below. Have fun!


##






# Input must begin with two 3digit base10 numbers. We'll ignore trailing


# data for now, since we will be using that as working memory.


/^[09]\{3\} [09]\{3\}/!q1




# If we do not have more than two numbers, then this is the first time we're


# being run and we need to set up our working memory. The leftmost number


# (the first operand) is going to serve as our accumulator, so we will


# duplicate that number. We also need to hold a copy of that operand to


# decrement as we increment the accumulator. So we start with three copies


# of the first operand in the form of `A B A A'.


s/^\([09]\{3\}\) .\{3\}$/& \1 \1/






# As a special case, if the second operand is `000', then the result


# is `000'. Set ourselves up so that the next check will terminate.


s/^\(...\) 000/000 001/






# If we have no more iterations to perform (if the second operand in


# register two is `001'), then we are done! If that's the case, clean up


# our output to display only the final result. The script will


# automatically exit with a nonzero status the next iteration because of


# the guard at the top of this script.


s/^\(...\) 001.*/\1/


/^... \+$/b








# We will be taking numbers from the last register. Increment the


# accumulator.


s/^\(..\)9/\1A/; s/^\(..\)8/\19/; s/^\(..\)7/\18/;


s/^\(..\)6/\17/; s/^\(..\)5/\16/; s/^\(..\)4/\15/;


s/^\(..\)3/\14/; s/^\(..\)2/\13/; s/^\(..\)1/\12/;


s/^\(..\)0/\11/;




# Accumulator 10s.


s/^\(.\)9A/\1A0/; s/^\(.\)8A/\190/; s/^\(.\)7A/\180/;


s/^\(.\)6A/\170/; s/^\(.\)5A/\160/; s/^\(.\)4A/\150/;


s/^\(.\)3A/\140/; s/^\(.\)2A/\130/; s/^\(.\)1A/\120/;


s/^\(.\)0A/\110/;




# Accumulator 100s


s/^9A/A0/; s/^8A/90/; s/^7A/80/;


s/^6A/70/; s/^5A/60/; s/^4A/50/;


s/^3A/40/; s/^2A/30/; s/^1A/20/;


s/^0A/10/;








# We now need to _decrement_ the last register (since the accumulator took a


# single number from it). This is very similar to incrementing, but instead


# of setting a carry flag on overflow, we set it on an _underflow_.


s/\(..\)0$/\1A/; s/\(..\)1$/\10/; s/\(..\)2$/\11/;


s/\(..\)3$/\12/; s/\(..\)4$/\13/; s/\(..\)5$/\14/;


s/\(..\)6$/\15/; s/\(..\)7$/\16/; s/\(..\)8$/\17/;


s/\(..\)9$/\18/;




# Accumulator 10s.


s/\(.\)0A$/\1A9/; s/\(.\)1A$/\109/; s/\(.\)2A$/\119/;


s/\(.\)3A$/\129/; s/\(.\)4A$/\139/; s/\(.\)5A$/\149/;


s/\(.\)6A$/\159/; s/\(.\)7A$/\169/; s/\(.\)8A$/\179/;


s/\(.\)9A$/\189/;




# Accumulator 100s. Note that we do not support going below 0.


s/1A\(.\)$/09\1/; s/2A\(.\)$/19\1/; s/3A\(.\)$/29\1/;


s/4A\(.\)$/39\1/; s/5A\(.\)$/49\1/; s/6A\(.\)$/59\1/;


s/7A\(.\)$/69\1/; s/8A\(.\)$/79\1/; s/9A\(.\)$/89\1/;








# If we end up with `000', then we have performed one multiplication


# step. Decrement the second operand (in the second register) to reflect


# this progress.


s/^\(... ..\)0\(.* 000\)/\1A\2/; s/^\(... ..\)1\(.* 000\)/\10\2/;


s/^\(... ..\)2\(.* 000\)/\11\2/; s/^\(... ..\)3\(.* 000\)/\12\2/;


s/^\(... ..\)4\(.* 000\)/\13\2/; s/^\(... ..\)5\(.* 000\)/\14\2/;


s/^\(... ..\)6\(.* 000\)/\15\2/; s/^\(... ..\)7\(.* 000\)/\16\2/;


s/^\(... ..\)8\(.* 000\)/\17\2/; s/^\(... ..\)9\(.* 000\)/\18\2/;




# Second register 10s.


s/^\(... .\)0A\(.* 000\)/\1A9\2/; s/^\(... .\)1A\(.* 000\)/\109\2/;


s/^\(... .\)2A\(.* 000\)/\119\2/; s/^\(... .\)3A\(.* 000\)/\129\2/;


s/^\(... .\)4A\(.* 000\)/\139\2/; s/^\(... .\)5A\(.* 000\)/\149\2/;


s/^\(... .\)6A\(.* 000\)/\159\2/; s/^\(... .\)7A\(.* 000\)/\169\2/;


s/^\(... .\)8A\(.* 000\)/\179\2/; s/^\(... .\)9A\(.* 000\)/\189\2/;




# Second register 100s. Note that we do not support going below 0.


s/^\(... \)1A\(.* 000\)/\109\2/; s/^\(... \)2A\(.* 000\)/\119\2/;


s/^\(... \)3A\(.* 000\)/\129\2/; s/^\(... \)4A\(.* 000\)/\139\2/;


s/^\(... \)5A\(.* 000\)/\149\2/; s/^\(... \)6A\(.* 000\)/\159\2/;


s/^\(... \)7A\(.* 000\)/\169\2/; s/^\(... \)8A\(.* 000\)/\179\2/;


s/^\(... \)9A\(.* 000\)/\189\2/;






# Otherwise, we must then prepare for the next round by copying the third


# register (the original first operand) back into the fourth.


s/\(...\) 000$/\1 \1/
