File: multiply.w

package info (click to toggle)
sgb 1:20030623-3
  • links: PTS
  • area: non-free
  • in suites: sarge
  • size: 1,868 kB
  • ctags: 28
  • sloc: makefile: 197; sh: 15
file content (310 lines) | stat: -rw-r--r-- 10,378 bytes parent folder | download | duplicates (6)
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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
% This file is part of the Stanford GraphBase (c) Stanford University 1993
@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!
@i gb_types.w

\def\title{MULTIPLY}

\prerequisite{GB\_\,GATES}
@* Introduction. This demonstration program uses graphs
constructed by the |prod| procedure in the {\sc GB\_\,GATES} module to produce
an interactive program called \.{multiply}, which multiplies and divides
small numbers the slow way---by simulating the behavior of
a logical circuit, one gate at a time.

The program assumes that \UNIX/ conventions are being used. Some code in
sections listed under `\UNIX/ dependencies' in the index might need to change
if this program is ported to other operating systems.

\def\<#1>{$\langle${\rm#1}$\rangle$}
To run the program under \UNIX/, say `\.{multiply} $m$ $n$ [|seed|]', where
$m$ and $n$ are the sizes of the numbers to be multiplied, in bits,
and where |seed| is given if and only if you want the multiplier
to be a special-purpose circuit for multiplying a given $m$-bit
number by a randomly chosen $n$-bit constant.

The program will prompt you for two numbers (or for just one, if the
random constant option has been selected), and it will use the gate
network to compute their product. Then it will ask for more input, and so on.

@ Here is the general layout of this program, as seen by the \CEE/ compiler:
@^UNIX dependencies@>

@p
#include "gb_graph.h" /* the standard GraphBase data structures */
#include "gb_gates.h" /* routines for gate graphs */
@h@#
@<Global variables@>@;
@<Handy subroutines@>@;
main(argc,argv)
  int argc; /* the number of command-line arguments */
  char *argv[]; /* an array of strings containing those arguments */
{
  @<Declare variables that ought to be in registers@>;
  @<Obtain |m|, |n|, and optional |seed| from the command line@>;
  @<Make sure |m| and |n| are valid; generate the |prod| graph |g|@>;
  if (seed<0) /* no seed given */
   printf("Here I am, ready to multiply %ld-bit numbers by %ld-bit numbers.\n",
       m,n);
  else {
    g=partial_gates(g,m,0L,seed,buffer);
    if (g) {
      @<Set |y| to the decimal value of the second input@>;
      printf("OK, I'm ready to multiply any %ld-bit number by %s.\n",m,y);
    }@+else { /* there was enough memory to make the original |g|, but
                not enough to reduce it; this probably can't happen,
                but who knows? */
      printf("Sorry, I couldn't process the graph (trouble code %ld)!\n",
         panic_code);
      return -9;
    }
  }
  printf("(I'm simulating a logic circuit with %ld gates, depth %ld.)\n",
     g->n,depth(g));
  while(1) {
    @<Prompt for one or two numbers; |break| if unsuccessful@>;
    @<Use the network to compute the product@>;
    printf("%sx%s=%s%s.\n",x,y,(strlen(x)+strlen(y)>35?"\n ":""),z);
  }
  return 0; /* normal exit */
}

@ @<Make sure |m| and |n| are valid; generate the |prod| graph |g|@>=
if (m<2) m=2;
if (n<2) n=2;
if (m>999 || n>999) {
  printf("Sorry, I'm set up only for precision less than 1000 bits.\n");
  return -1;
}
if ((g=prod(m,n))==NULL) {
  printf("Sorry, I couldn't generate the graph (not enough memory for %s)!\n",
    panic_code==no_room? "the gates": panic_code==alloc_fault? "the wires":
     "local optimization");
  return -3;
}

@ To figure the maximum length of strings |x| and |y|, we note that
$2^{999}\approx5.4\times10^{300}$.

@<Glob...@>=
Graph *g; /* graph that defines a logical network for multiplication */
long m,n; /* length of binary numbers to be multiplied */
long seed; /* optional seed value, or $-1$ */
char x[302], y[302], z[603]; /* input and output numbers, as decimal strings */
char buffer[2000]; /* workspace for communication between routines */

@ @<Declare variables...@>=
register char *p,*q,*r; /* pointers for string manipulation */
register long a,b; /* amounts being carried over while doing radix conversion */

@ @<Obtain |m|, |n|, and...@>=
@^UNIX dependencies@>
if (argc<3 || argc>4 || sscanf(argv[1],"%ld",&m)!=1 ||
              sscanf(argv[2],"%ld",&n)!=1) {
  fprintf(stderr,"Usage: %s m n [seed]\n",argv[0]);
  return -2;
}
if (m<0) m=-m; /* maybe the user attached |'-'| to the argument */
if (n<0) n=-n;
seed=-1;
if (argc==4 && sscanf(argv[3],"%ld",&seed)==1 && seed<0)
  seed=-seed;

@ This program may not be user-friendly, but at least it is polite.

@d prompt(s)
    {@+printf(s);@+fflush(stdout); /* make sure the user sees the prompt */
      if (fgets(buffer,999,stdin)==NULL) break;@+}
@d retry(s,t)
    {@+printf(s);@+goto t;@+}

@<Prompt...@>=
step1: prompt("\nNumber, please? ");
for (p=buffer;*p=='0';p++) ; /* bypass leading zeroes */
if (*p=='\n') {
  if (p>buffer) p--; /* zero is acceptable */
  else break; /* empty input terminates the run */
}
for (q=p;*q>='0' && *q<='9';q++) ; /* check for digits */
if (*q!='\n') retry(
    "Excuse me... I'm looking for a nonnegative sequence of decimal digits.",
      step1);
*q=0;
if (strlen(p)>301)
  retry("Sorry, that's too big.",step1);
strcpy(x,p);
if (seed<0) {
  @<Do the same thing for |y| instead of |x|@>;
}

@ @<Do the same...@>=
step2: prompt("Another? ");
for (p=buffer;*p=='0';p++) ; /* bypass leading zeroes */
if (*p=='\n') {
  if (p>buffer) p--; /* zero is acceptable */
  else break; /* empty input terminates the run */
}
for (q=p;*q>='0' && *q<='9';q++) ; /* check for digits */
if (*q!='\n') retry(
    "Excuse me... I'm looking for a nonnegative sequence of decimal digits.",
      step2);
*q=0;
if (strlen(p)>301)
  retry("Sorry, that's too big.",step2);
strcpy(y,p);

@ The binary value chosen at random by |partial_gates| appears as a
string of 0s and 1s in |buffer|, in little-endian order. We compute
the corresponding decimal value by repeated doubling.

If the value turns out to be zero, the whole network will have collapsed.
Otherwise, however, the |m| inputs from the first operand
will all remain present, because they all affect the output.

@<Set |y| to the decimal value of the second input@>=
*y='0';@+*(y+1)=0; /* now |y| is |"0"| */
for (r=buffer+strlen(buffer)-1;r>=buffer;r--) {
    /* we will set $y=2y+t$ where $t$ is the next bit, |*r| */
  if (*y>='5') a=0,p=y;
  else a=*y-'0',p=y+1;
  for (q=y;*p;a=b,p++,q++) {
    if (*p>='5') {
       b=*p-'5';
       *q=2*a+'1';
     }@+else {
       b=*p-'0';
       *q=2*a+'0';
     }
  }
  if (*r=='1') *q=2*a+'1';
  else *q=2*a+'0';
  *++q=0; /* terminate the string */
}
if (strcmp(y,"0")==0) {
  printf("Please try another seed value; %d makes the answer zero!\n",seed);
  return(-5);
}

@* Using the network. The reader of the code in the previous section
will have noticed that we are representing high-precision decimal
numbers as strings. We might as well do that, since the only
operations we need to perform on them are input, output, doubling, and
halving. In fact, arithmetic on strings is kind of fun, if you like
that sort of thing.

Here is a subroutine that converts a decimal string to a binary string.
The decimal string is big-endian as usual, but the binary string is
little-endian. The decimal string is decimated in the process; it
should end up empty, unless the original value was too big.

@<Handy subroutines@>=
decimal_to_binary(x,s,n)
  char *x; /* decimal string */
  char *s; /* binary string */
  long n; /* length of |s| */
{@+register long k;
  register char *p,*q; /* pointers for string manipulation */
  register long r; /* remainder */
  for (k=0;k<n;k++,s++) {
    if (*x==0) *s='0';
    else { /* we will divide |x| by 2 */
      if (*x>'1') p=x,r=0;
      else p=x+1,r=*x-'0';
      for (q=x;*p;p++,q++) {
        r=10*r+*p-'0';
        *q=(r>>1)+'0';
        r=r&1;
      }
      *q=0; /* terminate string |x| */
      *s='0'+r;
    }
  }
  *s=0; /* terminate the output string */
}

@ @<Use the network to compute the product@>=
strcpy(z,x);
decimal_to_binary(z,buffer,m);
if (*z) {
  printf("(Sorry, %s has more than %ld bits.)\n",x,m);
  continue;
}
if (seed<0) {
  strcpy(z,y);
  decimal_to_binary(z,buffer+m,n);
  if (*z) {
    printf("(Sorry, %s has more than %ld bits.)\n",y,n);
    continue;
  }
}
if (gate_eval(g,buffer,buffer)<0) {
  printf("??? An internal error occurred!");
  return 666; /* this can't happen */
}
@<Convert the binary number in |buffer| to the decimal string |z|@>;

@ The remaining task is almost identical to what we needed to do
when computing the value of |y| after a random seed was specified.
But this time the binary number in |buffer| is big-endian.

@<Convert the binary number in |buffer| to the decimal string |z|@>=
*z='0';@+*(z+1)=0;
for (r=buffer;*r;r++) {
    /* we'll set $z=2z+t$ where $t$ is the next bit, |*r| */
  if (*z>='5') a=0,p=z;
  else a=*z-'0',p=z+1;
  for (q=z;*p;a=b,p++,q++) {
    if (*p>='5') {
       b=*p-'5';
       *q=2*a+'1';
     }@+else {
       b=*p-'0';
       *q=2*a+'0';
     }
  }
  if (*r=='1') *q=2*a+'1';
  else *q=2*a+'0';
  *++q=0; /* terminate the string */
}

@* Calculating the depth. The depth of a gate network produced by {\sc
GB\_\,GATES} is easily discovered by making one pass over the
vertices.  An input gate or a constant has depth~0; every other gate
has depth one greater than the maximum of its inputs.

This routine is more general than it needs to be for the circuits output
by |prod|. The result of a latch is considered to have depth~0.

Utility field |u.I| is set to the depth of each individual gate.

@d dp u.I

@<Handy...@>=
long depth(g)
  Graph *g; /* graph with gates as vertices */
{@+register Vertex *v; /* the current vertex of interest */
  register Arc *a; /* the current arc of interest */
  long d; /* depth of current vertex */
  if (!g) return -1; /* no graph supplied! */
  for (v=g->vertices; v<g->vertices+g->n; v++) {
    switch (v->typ) { /* branch on type of gate */
    case 'I': case 'L': case 'C': v->dp=0;@+break;
    default: @<Set |d| to the maximum depth of an operand of |v|@>;
      v->dp=1+d;
    }
  }
  @<Set |d| to the maximum depth of an output of |g|@>;
  return d;
}

@ @<Set |d| to the maximum depth of an operand of |v|@>=
d=0;
for (a=v->arcs; a; a=a->next)
  if (a->tip->dp>d) d=a->tip->dp;

@ @<Set |d| to the maximum depth of an output of |g|@>=
d=0;
for (a=g->outs; a; a=a->next)
  if (!is_boolean(a->tip) && a->tip->dp>d) d=a->tip->dp;

@* Index. Finally, here's a list that shows where the identifiers of this
program are defined and used.