Circuits

circuits.c

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define DEBUG(str) //printf(str)
typedef struct
{
   int order;
   float *coeff;
}poly;

void print(poly a)
{
   int i;
   int no_output = 1;
   for(i = a.order; i >= 0; i--)
   {
      if(a.coeff[i] == 0)
         continue;
      printf("%+.2fx^%d", a.coeff[i], i);
      no_output = 0;
   }
   if(no_output)
   {
      printf("0");
   }
   printf("\n");
}

poly clone(poly a)
{
   poly c;
   int i, n;
   c.order = a.order;
   for(i = 0; i <= c.order; i++ )
   {
      c.coeff[i] = a.coeff[i];
   }
   DEBUG("Clone");
   return c;
}
poly multiply(poly a, poly b)
{
   poly res;
   int i, j, n, o1 = a.order, o2 = b.order;
   res.order = o1 + o2;
   res.coeff = (float *)malloc(sizeof(float) * (res.order + 1));
   for(i = 0; i <= res.order; i++)
      res.coeff[i] = 0;
   for(i = 0; i <= o1; i++)
      for(j = 0; j <= o2; j++)
         res.coeff[i+j] += a.coeff[i] * b.coeff[j];
   DEBUG("Multiply");
   return res;
}

poly add(poly a, poly b)
{
   int i, o1 = a.order, o2 = b.order;
   poly res;
   res.order = (o1>o2)?o1:o2;
   res.coeff = (float *)malloc(sizeof(float) * (res.order + 1));
   for(i = 0; i <= o1 && i <= o2; i++)
   {
      res.coeff[i] = a.coeff[i] + b.coeff[i];
   }
   while(i <= o1)
   {
      res.coeff[i] = a.coeff[i];
      i++;
   }
   while(i <= o2)
   {
      res.coeff[i] = b.coeff[i];
      i++;
   }
   res.order = i-1;
   DEBUG("Add");
   return res;
}

poly subtract(poly a, poly b)
{
   int i, o1 = a.order, o2 = b.order;
   poly res;
   res.order = (o1>o2)?o1:o2;
   res.coeff = (float *)malloc(sizeof(float) * (res.order + 1));
   for(i = 0; i <= o1 && i <= o2; i++)
   {
      res.coeff[i] = a.coeff[i] - b.coeff[i];
   }
   while(i <= o1)
   {
      res.coeff[i] = a.coeff[i];
      i++;
   }
   while(i <= o2)
   {
      res.coeff[i] = - b.coeff[i];
      i++;
   }
   res.order = i-1;
   DEBUG("Subtract");
   return res;
}

poly generate_node_x()
{
   poly new_node;
   new_node.order = 1;
   new_node.coeff = (float *)malloc(sizeof(float)*2);
   new_node.coeff[0] = 0;
   new_node.coeff[1] = 1;
   DEBUG("NewNode");
   return new_node;
}

#define AND(a,b) multiply(a,b)
#define OR(a,b) add(a,subtract(b,multiply(a,b)))

double f(poly p, double x)
{
   int i;
   double res = 0;
   if(x == 0)
      return p.coeff[0];
   for(i = p.order; i > 0; i--)
   {
      res += p.coeff[i];
      res *= x;
   }
   res += p.coeff[0];
   return res;
}

double FalsiMethod(poly p, double s, double t, double e, int m)
{
    int n, side = 0;
    double r, fr, fs = f(p, s), ft = f(p, t);
    for(n = 1; n <= m; n++)
    {
        r = (fs*t - ft*s) / (fs - ft);
        if (fabs(t-s) < e*fabs(t+s)) break;
        fr = f(p, r);
 
        if (fr * ft > 0)
        {
          t = r; ft = fr;
          if (side==-1) fs /= 2;
          side = -1;
        }
        else if (fs * fr > 0)
        {
          s = r;  fs = fr;
          if (side==+1) ft /= 2;
          side = +1;
        }
        else break;
    }
    return r;
}

double SecantMethod(poly p, double xn_1, double xn, double e, int m)
{
    int n;
    double d;
    for (n = 1; n <= m; n++)
    {
        d = (xn - xn_1) / (f(p, xn) - f(p, xn_1)) * f(p, xn);
        if (fabs(d) < e)
            return xn;
        xn_1 = xn;
        xn = xn - d;
    }
    return xn;
}

int main()
{
   int t, n, i, x, y, z;
   //int done=0, fixedpos;
   poly node[100], ex;
   scanf("%d", &t);
   while(t--)
   {
      scanf("%d", &n);
      for(i = 1; i <= n; i++)
      {
         scanf("%d", &x);
         switch(x)
         {
            case 0:
               node[i] = generate_node_x();
               break;
            case 1:
               scanf("%d %d", &y, &z);
               node[i] = OR(node[y], node[z]);
               break;
            case 2:
               scanf("%d %d", &y, &z);
               node[i] = AND(node[y], node[z]);
               break;
         }
      }
      ex = node[i-1];
      ex.coeff[0] -= 0.5;
      /*
      fixedpos = (f(ex,0) > 0);
      t = 1;
      while(!done)
      {
         t = t/2;
         if(fixedpos && f(t) < 0)
      }
      */
      printf("%.5f\n", SecantMethod(ex, 0, 1, 5E-6, 100));
   }
   return 0;
}