Mike Gerwitz

Free Software Hacker+Activist

aboutsummaryrefslogtreecommitdiffstats
blob: 522c70772e3ee8225dfc7159ab33c32896683d8c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
# Single step in multiplying two base-10 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 0-padded 3-digit base-10
# numbers using nothing more than a series of regular expressions.  It
# involves adding and subtracting from a series of registers---each
# invocation of the script performs a single addition step toward the final
# result.
#
# For a lighter introduction, first look at `base10-inc.sed', which shows
# how to implement a basic increment on a single 3-digit base-10 number.
#
# This script uses four 3-digit registers delimited by a single space (for
# legibility; no delimiters are necessary since the registers are
# fixed-width).  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 accumulator---it
# 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 0-padded base-10 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 base10-mul.sed <( echo 005 003 )
#
# The process is further detailed below.  Have fun!
##


# Input must begin with two 3-digit base-10 numbers.  We'll ignore trailing
# data for now, since we will be using that as working memory.
/^[0-9]\{3\} [0-9]\{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/^\([0-9]\{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 non-zero 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/