Difference between revisions of "Moscow 5"

From CDOT Wiki
Jump to: navigation, search
(Created page with '== Assignment 1 == This is a KenKen puzzle solver using a brute force algorithm implementing recursive backtracking to solve a KenKen puzzle. The program creates a possible map …')
 
(→‎Assignment 1)
 
Line 1: Line 1:
 
== Assignment 1 ==
 
== Assignment 1 ==
  
−
This is a KenKen puzzle solver using a brute force algorithm implementing recursive backtracking to solve a KenKen puzzle. The program creates a possible map of solutions and sequencially substitutes possible valid inputs into the solution map accordingly. When a solution is found to be a failure the program exits the recursive loop back to the last stable solution and continues with the solution map.
+
This is a Pi calculator that calculates pi up to n digits using the arctan formula pi=16arctan(1/5)-4arctan(1/239) as the main formula along with another variation of the formula based on the same method.
  
 
<br/>
 
<br/>
  
−
Source: [[https://github.com/thlmille/KenKenSolver KenKen Solver]]
+
 
  
 
<br/>
 
<br/>
Line 13: Line 13:
 
<br/>
 
<br/>
  
−
The update_possible method:
+
The arctan method:
 
<big><pre>
 
<big><pre>
−
// Iterate through solution we have so far, and
 
  
−
//  remove possibilities from possible map
+
void arctan(int multiplier, int denom, int sign)
 +
{
 +
      INDEXER x;
 +
      LONG remain, temp, divisor, denom2;
 +
      SHORT NotZero = 1;
 +
      INDEXER adv;
  
−
void puzzle::update_possible () {
+
      for (x = 0; x < size; x++)
 +
            powers[x] = 0;
  
−
  for (int i = 1; i <= this->size; ++i) {
+
      divisor = 1;
 +
      denom2 = (LONG)denom;denom2 *= denom2;
 +
      adv = 0;
  
−
    for (int j = 1; j <= this->size; ++j) {
+
      remain = (LONG)multiplier * denom;
 +
      while (NotZero)
 +
      {
 +
            for (x = adv; x < size; x++)
 +
            {
 +
                  temp = (LONG)powers[x] + remain;
 +
                  powers[x] = (SHORT)(temp / denom2);
 +
                  remain = (temp - (denom2 * (LONG)powers[x])) * BASE;
 +
            }
  
−
      if (this->solution[i][j] != 0) {
+
            remain = 0;
 +
            for (x = adv; x < size; x++)
 +
            {
 +
                  temp = (LONG)powers[x] + remain;
 +
                  term[x] = (SHORT)(temp / divisor);
 +
                  remain = (temp - (divisor * (LONG)term[x])) * BASE;
 +
            }
 +
            remain = 0;
  
−
this->possible[make_pair(i, j)].clear();
+
            if (sign > 0)
 +
            {
 +
                  LONG carry, sum;
  
−
int taken = this->solution[i][j];
+
                  carry = 0;
 +
                  for (x = size - 1; x >=0; x--)
 +
                  {
 +
                        sum = (LONG)pi[x] + (LONG)term[x] + carry;
 +
                        carry = 0;
 +
                        if (sum >= BASE)
 +
                        {
 +
                              carry = 1;
 +
                              sum -= BASE;
 +
                        }
 +
                        pi[x] = (SHORT)sum;
 +
                  }
 +
            }
 +
            else
 +
            {
 +
                  LONG borrow, sum;
  
−
update_possible_row(taken, i);
+
                  borrow = 0;
 +
                  for (x = size - 1; x >= 0; x--)
 +
                  {
 +
                        sum = (LONG)pi[x] - (LONG)term[x] - borrow;
 +
                        borrow = 0;
 +
                        if (sum < 0)
 +
                        {
 +
                              borrow = 1;
 +
                              sum += BASE;
 +
                        }
 +
                        pi[x] = (SHORT)sum;
 +
                  }
 +
            }
  
−
update_possible_column(taken, j);
+
            sign = -sign;
 +
            divisor += 2;
 +
            NotZero = 0;
 +
            for (x = adv; x < size; x++)
 +
            {
 +
                  if (powers[x])
 +
                  {
 +
                        NotZero = 1;
 +
                        break;
 +
                  }
 +
            }
  
 +
            if (NotZero)
 +
            {
 +
                  while (powers[adv] == 0)
 +
                        adv++;
 +
            }
 +
            /* We can skip ones that are already 0 */
 
       }
 
       }
−
 
−
    }
 
−
 
−
  }
 
−
 
 
}
 
}

Latest revision as of 10:49, 6 December 2012

Assignment 1

This is a Pi calculator that calculates pi up to n digits using the arctan formula pi=16arctan(1/5)-4arctan(1/239) as the main formula along with another variation of the formula based on the same method.




We will be optimizing the following functions:


The arctan method: 


void arctan(int multiplier, int denom, int sign)
{
      INDEXER x;
      LONG remain, temp, divisor, denom2;
      SHORT NotZero = 1;
      INDEXER adv;

      for (x = 0; x < size; x++)
            powers[x] = 0;

      divisor = 1;
      denom2 = (LONG)denom;denom2 *= denom2;
      adv = 0;

      remain = (LONG)multiplier * denom;
      while (NotZero)
      {
            for (x = adv; x < size; x++)
            {
                  temp = (LONG)powers[x] + remain;
                  powers[x] = (SHORT)(temp / denom2);
                  remain = (temp - (denom2 * (LONG)powers[x])) * BASE;
            }

            remain = 0;
            for (x = adv; x < size; x++)
            {
                  temp = (LONG)powers[x] + remain;
                  term[x] = (SHORT)(temp / divisor);
                  remain = (temp - (divisor * (LONG)term[x])) * BASE;
            }
            remain = 0;

            if (sign > 0)
            {
                  LONG carry, sum;

                  carry = 0;
                  for (x = size - 1; x >=0; x--)
                  {
                        sum = (LONG)pi[x] + (LONG)term[x] + carry;
                        carry = 0;
                        if (sum >= BASE)
                        {
                              carry = 1;
                              sum -= BASE;
                        }
                        pi[x] = (SHORT)sum;
                  }
            }
            else
            {
                  LONG borrow, sum;

                  borrow = 0;
                  for (x = size - 1; x >= 0; x--)
                  {
                        sum = (LONG)pi[x] - (LONG)term[x] - borrow;
                        borrow = 0;
                        if (sum < 0)
                        {
                              borrow = 1;
                              sum += BASE;
                        }
                        pi[x] = (SHORT)sum;
                  }
            }

            sign = -sign;
            divisor += 2;
            NotZero = 0;
            for (x = adv; x < size; x++)
            {
                  if (powers[x])
                  {
                        NotZero = 1;
                        break;
                  }
            }

            if (NotZero)
            {
                  while (powers[adv] == 0)
                        adv++;
            }
            /* We can skip ones that are already 0 */
      }
}

Retrieved from "https://wiki.cdot.senecapolytechnic.ca/w/index.php?title=Moscow_5&oldid=91853"