summaryrefslogtreecommitdiff
path: root/support/graphbase/multiply.w
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /support/graphbase/multiply.w
Initial commit
Diffstat (limited to 'support/graphbase/multiply.w')
-rw-r--r--support/graphbase/multiply.w314
1 files changed, 314 insertions, 0 deletions
diff --git a/support/graphbase/multiply.w b/support/graphbase/multiply.w
new file mode 100644
index 0000000000..15ea0a1567
--- /dev/null
+++ b/support/graphbase/multiply.w
@@ -0,0 +1,314 @@
+% This file is part of the Stanford GraphBase (c) Stanford University 1992
+\def\title{MULTIPLY}
+@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!
+
+\prerequisite{GB\_\thinspace GATES}
+@* Introduction. This demonstration program uses graphs
+constructed by the |prod| procedure in the |gb_gates| module to produce
+an interactive program called \.{multiply}, which multiplies and divides
+small numbers the slow way (i.e., 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 may 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.
+
+@ We use the data types \&{Vertex}, \&{Arc}, and \&{Graph} defined
+in |gb_graph|.
+
+@f Vertex int
+@f Arc int
+@f Graph int
+
+@ 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 */
+@#
+@<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 %d-bit numbers by %d-bit numbers.\n",
+ m,n);
+ else {
+ g=partial_gates(g,m,0,seed,buffer);
+ if (g) {
+ @<Set |y| to the decimal value of the second input@>;
+ printf("OK, I'm ready to multiply any %d-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 %d)!\n",
+ panic_code);
+ return -9;
+ }
+ }
+ printf("(I'm simulating a logic circuit with %d gates, depth %d.)\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.\n",x,y,z);
+ }
+}
+
+@ @<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 */
+int 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 int a,b; /* amounts being carried over while doing radix conversion */
+
+@ @<Obtain |m|, |n|, and...@>=
+@^UNIX dependencies@>
+if (argc<3 || sscanf(argv[1],"%d",&m)!=1 ||
+ sscanf(argv[2],"%d",&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>3 && sscanf(argv[3],"%d",&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("\nAnother? ");
+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 */
+ int n; /* length of |s| */
+{@+register int k;
+ register char *p,*q; /* pointers for string manipulation */
+ register int 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 %d 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 %d 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 |gb_gates|
+is easily obtained in one pass. 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...@>=
+int depth(g)
+ Graph *g; /* graph with gates as vertices */
+{@+register Vertex *v; /* the current vertex of interest */
+ Vertex *u, *uu; /* additional vertices being examined */
+ register Arc *a; /* the current arc of interest */
+ int 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.
+