From e0c6872cf40896c7be36b11dcc744620f10adf1d Mon Sep 17 00:00:00 2001 From: Norbert Preining Date: Mon, 2 Sep 2019 13:46:59 +0900 Subject: Initial commit --- support/graphbase/multiply.w | 314 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 314 insertions(+) create mode 100644 support/graphbase/multiply.w (limited to 'support/graphbase/multiply.w') 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 */ +@# +@@; +@@; +main(argc,argv) + int argc; /* the number of command-line arguments */ + char *argv[]; /* an array of strings containing those arguments */ +{ + @; + @; + @; + 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) { + @; + 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) { + @; + @; + printf("%sx%s=%s.\n",x,y,z); + } +} + +@ @= +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}$. + +@= +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 */ + +@ @= +register char *p,*q,*r; /* pointers for string manipulation */ +register int a,b; /* amounts being carried over while doing radix conversion */ + +@ @= +@^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;@+} + +@= +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) { + @; +} + +@ @= +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. + +@= +*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. + +@= +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'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 */ +} + +@ @= +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 */ +} +@; + +@ 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. + +@= +*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 + +@= +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; vvertices+g->n; v++) { + switch (v->typ) { /* branch on type of gate */ + case 'I': case 'L': case 'C': v->dp=0;@+break; + default: @; + v->dp=1+d; + } + } + @; + return d; +} + +@ @= +d=0; +for (a=v->arcs; a; a=a->next) + if (a->tip->dp>d) d=a->tip->dp; + +@ @= +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. + -- cgit v1.2.3