TriForce

From CDOT Wiki
Revision as of 10:48, 8 March 2019 by Vincent Terpstra (talk | contribs) (Assignment 1: Julia Sets)
Jump to: navigation, search


GPU610/DPS915 | Student List | Group and Project Index | Student Resources | Glossary

TriForce

Team Members

  1. David Ferri, Sudoku Solver
  2. Vincent Terpstra, Julia Sets
  3. Raymond Kiguru, EasyBMP

Email All

Progress

Assignment 1: Sudoku Solver

Sudoku Solver Profiling

Source code from: https://www.geeksforgeeks.org/sudoku-backtracking-7/

Original Code:

// A Backtracking program  in C++ to solve Sudoku problem 
#include <stdio.h> 
 
// UNASSIGNED is used for empty cells in sudoku grid 
#define UNASSIGNED 0 
 
// N is used for the size of Sudoku grid. Size will be NxN 
#define N 9 
 
// This function finds an entry in grid that is still unassigned 
bool FindUnassignedLocation(int grid[N][N], int &row, int &col); 
 
// Checks whether it will be legal to assign num to the given row, col 
bool isSafe(int grid[N][N], int row, int col, int num); 
 
/* Takes a partially filled-in grid and attempts to assign values to 
  all unassigned locations in such a way to meet the requirements 
  for Sudoku solution (non-duplication across rows, columns, and boxes) */
bool SolveSudoku(int grid[N][N]) 
{ 
   int row, col; 
 
   // If there is no unassigned location, we are done 
   if (!FindUnassignedLocation(grid, row, col)) 
      return true; // success! 
 
   // consider digits 1 to 9 
   for (int num = 1; num <= 9; num++) 
   { 
       // if looks promising 
       if (isSafe(grid, row, col, num)) 
       { 
           // make tentative assignment 
           grid[row][col] = num; 
 
           // return, if success, yay! 
           if (SolveSudoku(grid)) 
               return true; 
 
           // failure, unmake & try again 
           grid[row][col] = UNASSIGNED; 
       } 
   } 
   return false; // this triggers backtracking 
} 
 
/* Searches the grid to find an entry that is still unassigned. If 
   found, the reference parameters row, col will be set the location 
   that is unassigned, and true is returned. If no unassigned entries 
   remain, false is returned. */
bool FindUnassignedLocation(int grid[N][N], int &row, int &col) 
{ 
   for (row = 0; row < N; row++) 
       for (col = 0; col < N; col++) 
           if (grid[row][col] == UNASSIGNED) 
               return true; 
   return false; 
} 
 
/* Returns a boolean which indicates whether an assigned entry 
  in the specified row matches the given number. */
bool UsedInRow(int grid[N][N], int row, int num) 
{ 
   for (int col = 0; col < N; col++) 
       if (grid[row][col] == num) 
           return true; 
   return false; 
} 
 
/* Returns a boolean which indicates whether an assigned entry 
  in the specified column matches the given number. */
bool UsedInCol(int grid[N][N], int col, int num) 
{ 
   for (int row = 0; row < N; row++) 
       if (grid[row][col] == num) 
           return true; 
   return false; 
} 
 
/* Returns a boolean which indicates whether an assigned entry 
  within the specified 3x3 box matches the given number. */
bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num) 
{ 
   for (int row = 0; row < 3; row++) 
       for (int col = 0; col < 3; col++) 
           if (grid[row+boxStartRow][col+boxStartCol] == num) 
               return true; 
   return false; 
} 
 
/* Returns a boolean which indicates whether it will be legal to assign 
  num to the given row,col location. */
bool isSafe(int grid[N][N], int row, int col, int num) 
{ 
   /* Check if 'num' is not already placed in current row, 
      current column and current 3x3 box */
   return !UsedInRow(grid, row, num) && 
          !UsedInCol(grid, col, num) && 
          !UsedInBox(grid, row - row%3 , col - col%3, num)&& 
           grid[row][col]==UNASSIGNED; 
} 
 
/* A utility function to print grid  */
void printGrid(int grid[N][N]) 
{ 
   for (int row = 0; row < N; row++) 
   { 
      for (int col = 0; col < N; col++) 
            printf("%2d", grid[row][col]); 
       printf("\n"); 
   } 
} 
 
/* Driver Program to test above functions */
int main() 
{ 
   // 0 means unassigned cells 
   int grid[N][N] = {{3, 0, 6, 5, 0, 8, 4, 0, 0}, 
                     {5, 2, 0, 0, 0, 0, 0, 0, 0}, 
                     {0, 8, 7, 0, 0, 0, 0, 3, 1}, 
                     {0, 0, 3, 0, 1, 0, 0, 8, 0}, 
                     {9, 0, 0, 8, 6, 3, 0, 0, 5}, 
                     {0, 5, 0, 0, 9, 0, 6, 0, 0}, 
                     {1, 3, 0, 0, 0, 0, 2, 5, 0}, 
                     {0, 0, 0, 0, 0, 0, 0, 7, 4}, 
                     {0, 0, 5, 2, 0, 6, 3, 0, 0}}; 
   if (SolveSudoku(grid) == true) 
         printGrid(grid); 
   else
        printf("No solution exists"); 
 
   return 0; 
} 


$ g++ sudokuC.cpp  -std=c++0x -o Sudoku
$ ./Sudoku
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9
$ gprof -p -b ./Sudoku gmon.out > 9x9.flt


// A Backtracking program  in C++ to solve Sudoku problem 
#include <stdio.h> 
 
// UNASSIGNED is used for empty cells in sudoku grid 
#define UNASSIGNED 0 
 
// N is used for the size of Sudoku grid. Size will be NxN 
#define N 16 
 
// This function finds an entry in grid that is still unassigned 
bool FindUnassignedLocation(int grid[N][N], int &row, int &col); 
 
// Checks whether it will be legal to assign num to the given row, col 
bool isSafe(int grid[N][N], int row, int col, int num); 
 
/* Takes a partially filled-in grid and attempts to assign values to 
 all unassigned locations in such a way to meet the requirements 
 for Sudoku solution (non-duplication across rows, columns, and boxes) */
bool SolveSudoku(int grid[N][N]) 
{ 
   int row, col; 
 
   // If there is no unassigned location, we are done 
   if (!FindUnassignedLocation(grid, row, col)) 
      return true; // success! 
 
   // consider digits 1 to 16
   for (int num = 1; num <= 16; num++) 
   { 
       // if looks promising 
       if (isSafe(grid, row, col, num)) 
       { 
           // make tentative assignment 
           grid[row][col] = num; 
 
           // return, if success, yay! 
           if (SolveSudoku(grid)) 
               return true; 
 
           // failure, unmake & try again 
           grid[row][col] = UNASSIGNED; 
       } 
   } 
   return false; // this triggers backtracking 
} 
 
/* Searches the grid to find an entry that is still unassigned. If 
  found, the reference parameters row, col will be set the location 
  that is unassigned, and true is returned. If no unassigned entries 
  remain, false is returned. */
bool FindUnassignedLocation(int grid[N][N], int &row, int &col) 
{ 
   for (row = 0; row < N; row++) 
       for (col = 0; col < N; col++) 
           if (grid[row][col] == UNASSIGNED) 
               return true; 
   return false; 
} 
 
/* Returns a boolean which indicates whether an assigned entry 
  in the specified row matches the given number. */
bool UsedInRow(int grid[N][N], int row, int num) 
{ 
   for (int col = 0; col < N; col++) 
       if (grid[row][col] == num) 
           return true; 
   return false; 
} 
 
/* Returns a boolean which indicates whether an assigned entry 
  in the specified column matches the given number. */
bool UsedInCol(int grid[N][N], int col, int num) 
{ 
   for (int row = 0; row < N; row++) 
       if (grid[row][col] == num) 
           return true; 
   return false; 
} 
 
/* Returns a boolean which indicates whether an assigned entry 
   within the specified 4x4 box matches the given number. */
 bool UsedInBox(int grid[N][N], int boxStartRow, int boxStartCol, int num) 
 { 
   for (int row = 0; row < 4; row++) 
       for (int col = 0; col < 4; col++) 
           if (grid[row+boxStartRow][col+boxStartCol] == num) 
               return true; 
   return false; 
 } 
 
/* Returns a boolean which indicates whether it will be legal to assign 
   num to the given row,col location. */
   bool isSafe(int grid[N][N], int row, int col, int num) 
{ 
   /* Check if 'num' is not already placed in current row, 
      current column and current 4x4 box */
   return !UsedInRow(grid, row, num) &&
           !UsedInCol(grid, col, num) &&
           !UsedInBox(grid, row - row%4 , col - col%4, num)&& 
           grid[row][col]==UNASSIGNED; 
} 
 
/* A utility function to print grid  */
void printGrid(int grid[N][N]) 
{ 
   for (int row = 0; row < N; row++) 
   { 
      for (int col = 0; col < N; col++) 
            printf("%2d", grid[row][col]); 
       printf("\n"); 
   } 
} 
 
/* Driver Program to test above functions */
int main() 
{ 
   //https://puzzlemadness.co.uk/16by16giantsudoku/
   // 0 means unassigned cells 
   int grid[N][N] = {{0,  8,   0,  0,  0,  0,  0,  3,  0,  0,  0, 10,  9,  7, 11, 0}, 
                     {0,  9,  15, 13,  0, 10,  0,  0,  2,  6,  8, 16,  0,  0,  0, 0}, 				  
                     {0,  0,  16,  0, 15,  0,  8,  0,  9,  0,  0,  0,  6,  0,  2, 0}, 				  
                     {1,  0,   2,  0,  9, 11,  4,  6, 15,  3,  5,  7,  0,  0, 12, 0}, 					  
                     {16, 6,   4,  0,  5,  2,  0,  0,  1,  0,  0,  0, 11,  0,  0, 12},						  
                     {5,  11,  0,  0,  0,  3,  0, 15,  0, 16,  0, 13,  0,  1,  0, 8}, 					  
                     {0,  0,   3,  0,  0,  6, 11, 14,  0,  5,  7,  0,  0,  9,  0, 0}, 				  
                     {0,  0,   0, 14,  8,  0, 10,  0,  0, 11, 12,  0,  0,  0,  0, 0},				  
                     {0,  7,  13,  0,  0,  0,  0, 12,  0,  8,  9,  0,  0,  0,  3, 0},				  
                     {0,  0,  11,  9,  0,  7,  0,  0,  0,  0,  0, 12,  0,  8, 16, 5},
                     {0,  0,  10,  0, 11, 13,  0,  0,  0,  0,  0,  3, 12,  0,  6, 0},				  
                     {0,  5,   0,  0, 10, 15,  0,  1,  7,  2,  0,  0, 14, 11,  0, 0},				  
                     {0,  0,   5,  0,  0, 12, 14,  0,  0, 10,  0,  0, 15,  0,  0, 4},					  
                     {9,  0,  14,  6,  0,  0,  1,  0, 16,  0,  2,  0,  3,  0, 13, 0},					  
                     {8,  13,  0,  4,  0,  0,  0,  0, 12,  7,  3,  0,  0,  6,  0, 0},				  
                     {0,  16, 12,  0,  0,  5,  0,  9,  0, 13, 14,  4,  1,  0,  0, 0}}; 
   if (SolveSudoku(grid) == true) 
         printGrid(grid); 
   else
        printf("No solution exists"); 
 
   return 0; 
}

25x25 Puzzle:

   int grid[N][N] = {{1,  0,   4,  0, 25,  0, 19,  0,  0,  10,  21, 8,  0,  14, 0,  6,  12,   9,  0,  0,  0,  0,  0,  0,  5}, 
                     {5,  0,  19, 23, 24,  0, 22,  12,  0,  0,  16, 6,  0,  20,  0,  18,  0,   25,  14,  13,  10, 11,  0,  1,  15}, 
                     {0,  0,   0,  0,  0,  0,  21,  5,  0,  20,  11,  10,  0,  1,  0,  4,  8,   24,  23,  15,  18,  0,  16,  22,  19},				  
                     {0,  7,  21,  8, 18,  0,  0,  0, 11,  0,  5,  0,  0,  24, 0,  0,  0,   17,  22,  1,  9,  6,  25,  0,  0}, 					  
                     {0, 13,  15,  0, 22, 14,  0,  18,  0,  16,  0,  0, 0,  4,  0,  0,  0,   19,  0,  0,  0,  24,  20,  21,  17},				  
                     {12, 0,  11,  0,  6,  0,  0, 0,  0, 15,  0, 0,  0,  0,  21,  25,  19,   0,  4,  0,  22,  14,  0,  20,  0},				  
                     {8,  0,   0, 21,  0, 16, 0, 0,  0,  2,  0,  3,  0,  0,  0,  0,  17,   23,  18,  22,  0,  0,  0,  24,  6},  
                     {4,  0,  14, 18,  7,  9, 0,  22,  21, 19, 0,  0,  0,  2,  0,  5,  0,   0,  0,  6,  16,  15,  0,  11,  12},				  
                     {22, 0,  24,  0, 23,  0,  0, 11,  0,  7,  0,  0,  4,  0,  14,  0,  2,   12,  0,  8,  5,  19,  0,  25,  9},
		      {20, 0,   0,  0,  5,  0,  0,  0,  0,  17,  9, 0,  12,  18, 0,  1,  0,   0,  7,  24,  0,  0,  0,  13,  4},					  
 		      {13, 0,   0,  5,  0,  2,  23,  14,  4,  18,  22,  0, 17,  0,  0,  20,  0,   1,  9,  21,  12,  0,  0,  8,  11},					  
 		      {14, 23,  0, 24,  0,  0,  0,  0,  0,  0,  0,  0, 20, 25,  0,  3,  4,   13,  0,  11,  21,  9,  5,  18,  22},			  
 		      {7,  0,   0, 11, 17, 20, 24,  0,  0, 0,  3,  4, 1,  12,  0,  0,  6,   14,  0,  5,  25,  13,  0,  0,  0},	  
 		      {0,  0,  16,  9,  0, 17,  11,  7, 10,  25,  0,  0,  0,  13, 6,  0,  0,   18,  0,  0,  19,  4,  0,  0,  20},  
 		      {6,  15,  0, 19,  4, 13,  0,  0, 5,  0,  18,  11,  0,  0,  9,  8,  22,   16,  25,  10,  7,  0,  0,  0,  0},  
                      {0,  0,   0,  2,  0,  0, 10, 19,  3,  0,  1,  0,  22,  9,  4,  11,  15,   0,  20,  0,  0,  8,  23,  0,  25}, 				       
 		      {0,  24,  8, 13,  1,  0, 0,  4,  20, 0, 17,  14,  0,  0,  18,  0,  16,   22,  5,  0,  11,  0,  10,  0,  0}, 
                      {23, 10,  0,  0,  0,  0,  0, 0,  18,  0,  6,  0,  16,  0,  0,  17,  1,   0,  13,  0,  0,  3,  19,  12,  0}, 
 		      {25,  5,  0, 14, 11,  0,  17,  0,  8,  24,  13, 0,  19,  23, 15,  9,  0,   0,  12,  0,  20,  0,  22,  0,  7},					  
 		      {0,   0, 17,  4,  0, 22,  15,  0,  23,  11,  12,  25, 0,  0,  0,  0,  18,   8,  0,  7,  0,  0,  14,  0,  13},				  
 		      {19,  6, 23, 22,  8,  0,  0,  1,  25,  4,  14,  2, 0, 3,  7,  13,  10,   11,  16,  0,  0,  0,  0,  0,  0},				  
 		      {0,   4,  0, 17,  0,  3, 0,  24,  0, 8,  20,  23, 11,  10,  25,  22,  0,   0,  0,  12,  13,  2,  18,  6,  0},					  
 		      {0,   0,  7, 16,  0,  0,  6,  17, 2,  21,  0,  18,  0,  0, 0,  19,  0,   0,  8,  0,  0,  0,  0,  4,  0},					  
 		      {18,  9, 25,  1,  2, 11,  0,  0, 13,  22,  4,  0,  21,  0,  5,  0,  23,   7,  0,  0,  15,  0,  3,  0,  8},						  
 		      {0,  21, 10,  0,  0, 12,  0,  20,  16, 0, 19,  0,  0,  0,  0,  15,  14,   4,  2,  18,  23,  25,  11,  7,  0}}; 


For 9x9 Sudoku Puzzle (3x3 squares)

Flat profile:
Each sample counts as 0.01 seconds.
 no time accumulated

  %   cumulative   self              self     total           
 time   seconds   seconds    calls  Ts/call  Ts/call  name    
  0.00      0.00     0.00     6732     0.00     0.00  isSafe(int (*) [9], int, int, int)
  0.00      0.00     0.00     6732     0.00     0.00  UsedInRow(int (*) [9], int, int)
  0.00      0.00     0.00     2185     0.00     0.00  UsedInCol(int (*) [9], int, int)
  0.00      0.00     0.00     1078     0.00     0.00  UsedInBox(int (*) [9], int, int, int)
  0.00      0.00     0.00      770     0.00     0.00  FindUnassignedLocation(int (*) [9], int&, int&)
  0.00      0.00     0.00        1     0.00     0.00  SolveSudoku(int (*) [9])
  0.00      0.00     0.00        1     0.00     0.00  printGrid(int (*) [9])

For 16x16 Sudoku Puzzle (4x4 squares) Puzzle from: [1]

Flat profile:
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 39.04     15.00    15.00 28071636     0.00     0.00  FindUnassignedLocation(int (*) [16], int&, int&)
 36.19     28.90    13.90 449145092     0.00     0.00  UsedInRow(int (*) [16], int, int)
 10.60     32.97     4.07 120354547     0.00     0.00  UsedInCol(int (*) [16], int, int)
  4.97     34.88     1.91 41212484     0.00     0.00  UsedInBox(int (*) [16], int, int, int)
  4.59     36.65     1.76        1     1.76    38.39  SolveSudoku(int (*) [16])
  4.55     38.39     1.75 449145092     0.00     0.00  isSafe(int (*) [16], int, int, int)
  0.01     38.40     0.01                             frame_dummy
  0.00     38.40     0.00        1     0.00     0.00  printGrid(int (*) [16])

For 25x25 Sudoku Puzzle (5x5 squares) Puzzle from: http://www.sudoku-download.net/sudoku_25x25.php

Flat profile:
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  Ks/call  Ks/call  name    
 48.76   1052.18  1052.18 425478951     0.00     0.00  UsedInRow(int (*) [25], int, int)
 25.24   1596.81   544.63 876012758     0.00     0.00  FindUnassignedLocation(int (*) [25], int&, int&)
 12.48   1866.03   269.21 590817023     0.00     0.00  UsedInCol(int (*) [25], int, int)
  4.83   1970.24   104.21 425478951     0.00     0.00  isSafe(int (*) [25], int, int, int)
  4.79   2073.51   103.27        1     0.10     2.17  SolveSudoku(int (*) [25])
  4.35   2167.39    93.89 1355081265     0.00     0.00  UsedInBox(int (*) [25], int, int, int)
  0.01   2167.56     0.17                             frame_dummy
  0.00   2167.56     0.00        1     0.00     0.00  printGrid(int (*) [25])

Assignment 1: EasyBMP

EasyBMP Bitmap image library (Sample Program: Image to black and white renderer)

Library: http://easybmp.sourceforge.net/

Sample code:
/**/
#include "EasyBMP.h"

using namespace std;
int main(int argc, char* argv[]) {
        // Create a new Bitmap image with EasyBMP
        BMP Background;
        Background.ReadFromFile(argv[1]);
        BMP Output;
        int picWidth = Background.TellWidth();
        int picHeight = Background.TellHeight();
        Output.SetSize(Background.TellWidth(), Background.TellHeight());
        Output.SetBitDepth(1);
        for (int i = 1; i < picWidth - 1; ++i) {
                for (int j = 1; j < picHeight - 1; ++j) {
                        int col = (Background(i, j)->Blue + Background(i, j)->Green + 10 * Background(i, j)->Red) / 12;
                        if (col > 127) {
                                Output(i, j)->Red = 255;
                                Output(i, j)->Blue = 255;
                                Output(i, j)->Green = 255;
                        }
                        else {
                               Output(i, j)->Red = 0;
                               Output(i, j)->Blue = 0;
                               Output(i, j)->Green = 0;
                        }
                }
        }
        Output.WriteToFile(argv[2]);
        return 0;
}
/**/

The program was compiled using the following commands:

g++ -c -pg -g BW.cpp EasyBMP.cpp
g++ -pg BW.o EasyBMP.o -o BW
rm *.o

Attempted to run the program with a number of files (8K resolution):

Cabin small.jpg Cabin2 small.jpg

Flat profile (Cabin):
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 31.38      1.74     1.74 33177600     0.00     0.00  BMP::FindClosestColor(RGBApixel&)
 23.52      3.04     1.30 198921624    0.00     0.00  BMP::operator()(int, int)
  9.95      3.59     0.55        2     0.28     0.28  BMP::SetSize(int, int)
  7.60      4.01     0.42 41663472     0.00     0.00  BMP::GetColor(int)
  6.87      4.39     0.38                             main
  5.43      4.69     0.30 74841076     0.00     0.00  IntPow(int, int)
  3.62      4.89     0.20 74841072     0.00     0.00  BMP::TellNumberOfColors()
  3.35      5.07     0.19     4320     0.00     0.00  BMP::Write1bitRow(unsigned char*, int, int)
  2.53      5.21     0.14 124990416    0.00     0.00  IntSquare(int)
  2.17      5.33     0.12     4320     0.00     0.00  BMP::Read24bitRow(unsigned char*, int, int)
  1.63      5.42     0.09        2     0.05     0.05  BMP::~BMP()
  0.90      5.47     0.05                             GetEasyBMPwarningState()
  0.72      5.51     0.04        1     0.04     0.04  _GLOBAL__sub_I_EasyBMPwarnings
  0.18      5.52     0.01        2     0.01     0.01  BMP::TellWidth()
  0.18      5.53     0.01        1     0.01     2.99  BMP::WriteToFile(char const*)
  0.00      5.53     0.00       16     0.00     0.00  SafeFread(char*, int, int, _IO_FILE*)
  0.00      5.53     0.00        6     0.00     0.00  IsBigEndian()
  0.00      5.53     0.00        2     0.00     0.00  EasyBMPcheckDataSize()
  0.00      5.53     0.00        2     0.00     0.00  BMP::TellHeight()
  0.00      5.53     0.00        2     0.00     0.00  BMP::SetBitDepth(int)
  0.00      5.53     0.00        2     0.00     0.00  BMP::BMP()
  0.00      5.53     0.00        2     0.00     0.00  BMFH::BMFH()
  0.00      5.53     0.00        2     0.00     0.00  BMIH::BMIH()
  0.00      5.53     0.00        1     0.00     0.00  _GLOBAL__sub_I_main
  0.00      5.53     0.00        1     0.00     0.00  __static_initialization_and_destruction_0(int, int)
  0.00      5.53     0.00        1     0.00     0.00  __static_initialization_and_destruction_0(int, int)
  0.00      5.53     0.00        1     0.00     0.40  BMP::ReadFromFile(char const*)
  0.00      5.53     0.00        1     0.00     0.00  BMP::CreateStandardColorTable()
Flat profile (Lake):
Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total
 time   seconds   seconds    calls   s/call   s/call  name
 30.60      1.71     1.71 33177600     0.00     0.00  BMP::FindClosestColor(RGBApixel&)
 21.12      2.89     1.18 198921624    0.00     0.00  BMP::operator()(int, int)
 10.20      3.46     0.57        2     0.29     0.29  BMP::SetSize(int, int)
  8.59      3.94     0.48                             main
  6.26      4.29     0.35 76982189     0.00     0.00  IntPow(int, int)
  6.08      4.63     0.34 43804585     0.00     0.00  BMP::GetColor(int)
  5.55      4.94     0.31 76982185     0.00     0.00  BMP::TellNumberOfColors()
  3.76      5.15     0.21     4320     0.00     0.00  BMP::Write1bitRow(unsigned char*, int, int)
  3.76      5.36     0.21 131413755    0.00     0.00  IntSquare(int)
  2.15      5.48     0.12     4320     0.00     0.00  BMP::Read24bitRow(unsigned char*, int, int)
  1.07      5.54     0.06        2     0.03     0.03  BMP::~BMP()
  0.54      5.57     0.03                             GetEasyBMPwarningState()
  0.36      5.59     0.02        1     0.02     0.02  _GLOBAL__sub_I_EasyBMPwarnings
  0.00      5.59     0.00       16     0.00     0.00  SafeFread(char*, int, int, _IO_FILE*)
  0.00      5.59     0.00        6     0.00     0.00  IsBigEndian()
  0.00      5.59     0.00        2     0.00     0.00  EasyBMPcheckDataSize()
  0.00      5.59     0.00        2     0.00     0.00  BMP::TellHeight()
  0.00      5.59     0.00        2     0.00     0.00  BMP::SetBitDepth(int)
  0.00      5.59     0.00        2     0.00     0.00  BMP::TellWidth()
  0.00      5.59     0.00        2     0.00     0.00  BMP::BMP()
  0.00      5.59     0.00        2     0.00     0.00  BMFH::BMFH()
  0.00      5.59     0.00        2     0.00     0.00  BMIH::BMIH()
  0.00      5.59     0.00        1     0.00     0.00  _GLOBAL__sub_I_main
  0.00      5.59     0.00        1     0.00     0.00  __static_initialization_and_destruction_0(int, int)
  0.00      5.59     0.00        1     0.00     0.00  __static_initialization_and_destruction_0(int, int)
  0.00      5.59     0.00        1     0.00     3.13  BMP::WriteToFile(char const*)
  0.00      5.59     0.00        1     0.00     0.41  BMP::ReadFromFile(char const*)
  0.00      5.59     0.00        1     0.00     0.00  BMP::CreateStandardColorTable()

Assignment 1: Julia Sets

This portion of the assignment focuses on Julia sets with the quadratic formula:

 fc(z) = z^2 + c;
 Where c and z are complex numbers

Psuedo code

 for(Pixel pix in image){
     pix.color = colorFunction(escapeValue(pix.loc, julia));
 }
 escapeValue(Complex loc, Complex julia){
     int cycles = 0;
     while(|loc| <=2 && ++cycles < MAXCYCLES){
        loc = loc * loc + julia;
     }
     return cycles;
 }
Julia.cpp
 /**
  * Julia.cpp
  * Vincent Terpstra
  * Feb 18 / 2019
  * Functions to display a Julia set
  */
 #include <iostream>
 #include <math.h>
 #include "Bitmap.h"
 #define MAXCYCLES 1000
 #define ITER 1
 #define PI 3.14159
 void calcJulia(int* array, int width, int height, float jR, float jI);
 void createBMP(int* array, int width, int height);
 int main(int size, const char ** args) {
     int height = (size > 1) ? atoi(args[1]) : 1000;
     int width = height / 2 * 3;
     int * array = new int[height * width];
     //Initial Julia Point value
       float jI = -0.4f;
       float jR =  0.6f;
     //for rotating the Julia point around the origin
       float angle = 2.0f / ITER * PI;
       float cosA = cos(angle);
       float sinA = sin(angle);
     for(int i = 0; i < ITER; i++){
         calcJulia(array, width, height, jI, jR);
         createBMP(array, width, height);
 
         //rotate the Julia point
         float tmp = jI;
         jI = cosA * jI - sinA * jR;
         jR = cosA * jR + sinA * tmp;
     }
 
     delete[] array;
     return 0;
 }
 /**
  * calcDepth
  *      finds the escape value of the Julia set
  *      inputs sR, sI: starting position on the map
  *          jR, jI: values of the julia set
  *      exits when |s| > 2 or reached MAXCYCLES
  *      return the escape value or MAXCYCLES
  */
 int calcDepth(float sR, float sI, const float jR, const float jI){
     int cycle = 0;
     while(sR * sR + sI * sI <= 4 && ++cycle < MAXCYCLES){
         // s(next) = s * s + j
         float tmp = sR;
         sR = sR * sR - sI * sI + jR;
         sI = 2 * tmp * sI + jI;
     }
     return cycle;
 }
 /**
  * calcJulia
  *  Function to calculate the values from (-1.5, 1.5),(-1, 1) in the Julia set
  *      saves the values onto the array
  */
 void calcJulia(int * array, int width, int height, const float jR, const float jI){
   float delta = 2 / (float)height;
   float x, y = -1;
   for(int i = 0; i < height; i++){
       x = -1.5f;
       for(int j = 0; j < width; j++){
           *array++ = calcDepth(x, y, jR, jI);
           x+=delta;
       }
       y += delta;
   }
 }
 struct Pix {
   float val;
   int r, g, b;
   Pix(float val, int r, int g, int b) : 
       val(val), r(r), g(g), b(b) {}
 };
 bool lerp(float clr, Pix& first, Pix& second, Bitmap & map);
 /**
  * createBMP
  *  maps the values in the array to a .bmp file
  *  linear interpolates between color values
  */
 void createBMP(int * array, int width, int height){
   static int idx = 0;
   char name[] = "julia000.bmp";
       name[5] = (idx / 100) + '0';
       name[6] = ((idx / 10) % 10) + '0';
       name[7] = (idx % 10) + '0';
   Bitmap map (name, width, height);
   //idx++;
   const int pix = width * height;
   struct Pix 
       clr0(0, 20, 20, 30),
       clr1(10, 20, 10, 100),
       clr2(180, 20, 170, 205), 
       clr3(MAXCYCLES, 0, 0, 0);
   const int * pMax = array + width * height;
   while(array < pMax){
       float clr = *array++;
       bool draw = 
           lerp(clr, clr0, clr1, map) || 
           lerp(clr, clr1, clr2, map) || 
           lerp(clr, clr2, clr3, map);
   }
 }
 /**
  * Function to linearly interpolate color values and draw to the Bitmap
  */
 bool lerp(float clr, Pix& first, Pix& second, Bitmap & map){
   if(clr <= second.val){
       float diff = (clr - first.val) / (second.val - first.val);
       map.addColor(
         first.b + diff * (second.b - first.b),
         first.g + diff * (second.g - first.g),
         first.r + diff * (second.r - first.r)
       );
       return true;
   }
   return false;
 }

To view the full c++ code github link

 This code is tested using the parameters 
 Range R(-1.5, 1.5) I(-1, 1)
 MAXCYCLES 1000
 Julia values = .72 * e^(i*θ): θ[0, 2π] : 100 intervals
Flat Profiles
Width: 750 Height: 500
Flat profile:
Each sample counts as 0.01 seconds.
 %   cumulative   self              self     total
time   seconds   seconds    calls  ns/call  ns/call  name
96.00     20.87    20.87                             calcJulia(int*, int, int, float, float)
 2.08     21.32     0.45 37500000    12.04    12.04  Bitmap::addColor(int, int, int)
 1.75     21.70     0.38 49447183     7.71    16.84  lerp(float, Pix&, Pix&, Bitmap&)
 0.46     21.80     0.10                             createBMP(int*, int, int)
 0.00     21.80     0.00      100     0.00     0.00  generateBitmapImage(unsigned char*, int, int, char const*)
 0.00     21.80     0.00      100     0.00     0.00  createBitmapFileHeader(int, int, int)
 0.00     21.80     0.00      100     0.00     0.00  createBitmapInfoHeader(int, int)
 0.00     21.80     0.00      100     0.00     0.00  Bitmap::Bitmap(char const*, int, int)
 0.00     21.80     0.00      100     0.00     0.00  Bitmap::~Bitmap()
 0.00     21.80     0.00        1     0.00     0.00  _GLOBAL__sub_I_main
Width: 1500 Height: 1000
Flat profile:
Each sample counts as 0.01 seconds.
 %   cumulative   self              self     total
time   seconds   seconds    calls  us/call  us/call  name
97.05     84.67    84.67                             calcJulia(int*, int, int, float, float)
 1.66     86.12     1.45 150000000     0.01     0.01  Bitmap::addColor(int, int, int)
 1.12     87.09     0.97 197791886     0.00     0.01  lerp(float, Pix&, Pix&, Bitmap&)
 0.37     87.41     0.32                             createBMP(int*, int, int)
 0.01     87.42     0.01      100    50.17    50.17  Bitmap::Bitmap(char const*, int, int)
 0.00     87.42     0.00      100     0.00     0.00  generateBitmapImage(unsigned char*, int, int, char const*)
 0.00     87.42     0.00      100     0.00     0.00  createBitmapFileHeader(int, int, int)
 0.00     87.42     0.00      100     0.00     0.00  createBitmapInfoHeader(int, int)
 0.00     87.42     0.00      100     0.00     0.00  Bitmap::~Bitmap()
 0.00     87.42     0.00        1     0.00     0.00  _GLOBAL__sub_I_main
 Width: 2250 Height: 1500
 Flat profile:
 Each sample counts as 0.01 seconds.
 %   cumulative   self              self     total
time   seconds   seconds    calls  us/call  us/call  name
96.39    189.55   189.55                             calcJulia(int*, int, int, float, float)
 1.89    193.27     3.72 337500000     0.01     0.01  Bitmap::addColor(int, int, int)
 1.49    196.20     2.93 445028641     0.01     0.01  lerp(float, Pix&, Pix&, Bitmap&)
 0.45    197.09     0.89                             createBMP(int*, int, int)
 0.01    197.11     0.02      100   150.51   150.51  Bitmap::Bitmap(char const*, int, int)
 0.00    197.11     0.00      100     0.00     0.00  generateBitmapImage(unsigned char*, int, int, char const*)
 0.00    197.11     0.00      100     0.00     0.00  createBitmapFileHeader(int, int, int)
 0.00    197.11     0.00      100     0.00     0.00  createBitmapInfoHeader(int, int)
 0.00    197.11     0.00      100     0.00     0.00  Bitmap::~Bitmap()
 0.00    197.11     0.00        1     0.00     0.00  _GLOBAL__sub_I_main
 Width: 3000 Height: 2000
 Flat profile:
 Each sample counts as 0.01 seconds.
 %   cumulative   self              self     total
time   seconds   seconds    calls  us/call  us/call  name
95.74    332.96   332.96                             calcJulia(int*, int, int, float, float)
 2.79    342.68     9.72 600000000     0.02     0.02  Bitmap::addColor(int, int, int)
 1.28    347.14     4.46 791167185     0.01     0.02  lerp(float, Pix&, Pix&, Bitmap&)
 0.44    348.66     1.52                             createBMP(int*, int, int)
 0.01    348.69     0.03      100   250.84   250.84  Bitmap::Bitmap(char const*, int, int)
 0.00    348.69     0.00      100     0.00     0.00  generateBitmapImage(unsigned char*, int, int, char const*)
 0.00    348.69     0.00      100     0.00     0.00  createBitmapFileHeader(int, int, int)
 0.00    348.69     0.00      100     0.00     0.00  createBitmapInfoHeader(int, int)
 0.00    348.69     0.00      100     0.00     0.00  Bitmap::~Bitmap()
 0.00    348.69     0.00        1     0.00     0.00  _GLOBAL__sub_I_main
Call Graphs
Call graph


granularity: each sample hit covers 2 byte(s) for 0.05% of 21.80 seconds

index % time self children called name

                                                <spontaneous>

[1] 96.0 20.93 0.00 calcJulia(int*, int, int, float, float) [1]


                                                <spontaneous>

[2] 4.0 0.14 0.73 createBMP(int*, int, int) [2]

               0.33    0.40 49447183/49447183     lerp(float, Pix&, Pix&, Bitmap&) [3]
               0.00    0.00     100/100         Bitmap::Bitmap(char const*, int, int) [15]
               0.00    0.00     100/100         Bitmap::~Bitmap() [16]

               0.33    0.40 49447183/49447183     createBMP(int*, int, int) [2]

[3] 3.4 0.33 0.40 49447183 lerp(float, Pix&, Pix&, Bitmap&) [3]

               0.40    0.00 37500000/37500000     Bitmap::addColor(int, int, int) [4]

               0.40    0.00 37500000/37500000     lerp(float, Pix&, Pix&, Bitmap&) [3]

[4] 1.8 0.40 0.00 37500000 Bitmap::addColor(int, int, int) [4]


               0.00    0.00     100/100         Bitmap::~Bitmap() [16]

[12] 0.0 0.00 0.00 100 generateBitmapImage(unsigned char*, int, int, char const*) [12]

               0.00    0.00     100/100         createBitmapFileHeader(int, int, int) [13]
               0.00    0.00     100/100         createBitmapInfoHeader(int, int) [14]

               0.00    0.00     100/100         generateBitmapImage(unsigned char*, int, int, char const*) [12]

[13] 0.0 0.00 0.00 100 createBitmapFileHeader(int, int, int) [13]


               0.00    0.00     100/100         generateBitmapImage(unsigned char*, int, int, char const*) [12]

[14] 0.0 0.00 0.00 100 createBitmapInfoHeader(int, int) [14]


               0.00    0.00     100/100         createBMP(int*, int, int) [2]

[15] 0.0 0.00 0.00 100 Bitmap::Bitmap(char const*, int, int) [15]


               0.00    0.00     100/100         createBMP(int*, int, int) [2]

[16] 0.0 0.00 0.00 100 Bitmap::~Bitmap() [16]

               0.00    0.00     100/100         generateBitmapImage(unsigned char*, int, int, char const*) [12]

               0.00    0.00       1/1           __libc_csu_init [25]

[17] 0.0 0.00 0.00 1 _GLOBAL__sub_I_main [17]


^L Index by function name

 [17] _GLOBAL__sub_I_main (julia.cpp) [3] lerp(float, Pix&, Pix&, Bitmap&) [15] Bitmap::Bitmap(char const*, int, int)
 [12] generateBitmapImage(unsigned char*, int, int, char const*) [1] calcJulia(int*, int, int, float, float) [16] Bitmap::~Bitmap()
 [13] createBitmapFileHeader(int, int, int) [2] createBMP(int*, int, int)
 [14] createBitmapInfoHeader(int, int) [4] Bitmap::addColor(int, int, int)
Call graph


granularity: each sample hit covers 2 byte(s) for 0.01% of 87.23 seconds

index % time self children called name

                                                <spontaneous>

[1] 96.0 83.70 0.00 calcJulia(int*, int, int, float, float) [1]


                                                <spontaneous>

[2] 4.0 0.37 3.16 createBMP(int*, int, int) [2]

               1.39    1.76 197791886/197791886     lerp(float, Pix&, Pix&, Bitmap&) [3]
               0.01    0.00     100/100         Bitmap::Bitmap(char const*, int, int) [5]
               0.00    0.00     100/100         Bitmap::~Bitmap() [16]

               1.39    1.76 197791886/197791886     createBMP(int*, int, int) [2]

[3] 3.6 1.39 1.76 197791886 lerp(float, Pix&, Pix&, Bitmap&) [3]

               1.76    0.00 150000000/150000000     Bitmap::addColor(int, int, int) [4]

               1.76    0.00 150000000/150000000     lerp(float, Pix&, Pix&, Bitmap&) [3]

[4] 2.0 1.76 0.00 150000000 Bitmap::addColor(int, int, int) [4]


               0.01    0.00     100/100         createBMP(int*, int, int) [2]

[5] 0.0 0.01 0.00 100 Bitmap::Bitmap(char const*, int, int) [5]


               0.00    0.00     100/100         Bitmap::~Bitmap() [16]

[13] 0.0 0.00 0.00 100 generateBitmapImage(unsigned char*, int, int, char const*) [13]

               0.00    0.00     100/100         createBitmapFileHeader(int, int, int) [14]
               0.00    0.00     100/100         createBitmapInfoHeader(int, int) [15]

               0.00    0.00     100/100         generateBitmapImage(unsigned char*, int, int, char const*) [13]

[14] 0.0 0.00 0.00 100 createBitmapFileHeader(int, int, int) [14]


               0.00    0.00     100/100         generateBitmapImage(unsigned char*, int, int, char const*) [13]

[15] 0.0 0.00 0.00 100 createBitmapInfoHeader(int, int) [15]


               0.00    0.00     100/100         createBMP(int*, int, int) [2]

[16] 0.0 0.00 0.00 100 Bitmap::~Bitmap() [16]

               0.00    0.00     100/100         generateBitmapImage(unsigned char*, int, int, char const*) [13]

               0.00    0.00       1/1           __libc_csu_init [25]

[17] 0.0 0.00 0.00 1 _GLOBAL__sub_I_main [17]


^L Index by function name

 [17] _GLOBAL__sub_I_main (julia.cpp) [3] lerp(float, Pix&, Pix&, Bitmap&) [5] Bitmap::Bitmap(char const*, int, int)
 [13] generateBitmapImage(unsigned char*, int, int, char const*) [1] calcJulia(int*, int, int, float, float) [16] Bitmap::~Bitmap()
 [14] createBitmapFileHeader(int, int, int) [2] createBMP(int*, int, int)
 [15] createBitmapInfoHeader(int, int) [4] Bitmap::addColor(int, int, int)
                       Call graph


granularity: each sample hit covers 2 byte(s) for 0.01% of 196.08 seconds

index % time self children called name

                                                <spontaneous>

[1] 96.0 188.22 0.00 calcJulia(int*, int, int, float, float) [1]


                                                <spontaneous>

[2] 4.0 0.95 6.91 createBMP(int*, int, int) [2]

               2.78    4.12 445028641/445028641     lerp(float, Pix&, Pix&, Bitmap&) [3]
               0.00    0.01     100/100         Bitmap::~Bitmap() [6]
               0.01    0.00     100/100         Bitmap::Bitmap(char const*, int, int) [7]

               2.78    4.12 445028641/445028641     createBMP(int*, int, int) [2]

[3] 3.5 2.78 4.12 445028641 lerp(float, Pix&, Pix&, Bitmap&) [3]

               4.12    0.00 337500000/337500000     Bitmap::addColor(int, int, int) [4]

               4.12    0.00 337500000/337500000     lerp(float, Pix&, Pix&, Bitmap&) [3]

[4] 2.1 4.12 0.00 337500000 Bitmap::addColor(int, int, int) [4]


               0.01    0.00     100/100         Bitmap::~Bitmap() [6]

[5] 0.0 0.01 0.00 100 generateBitmapImage(unsigned char*, int, int, char const*) [5]

               0.00    0.00     100/100         createBitmapFileHeader(int, int, int) [15]
               0.00    0.00     100/100         createBitmapInfoHeader(int, int) [16]

               0.00    0.01     100/100         createBMP(int*, int, int) [2]

[6] 0.0 0.00 0.01 100 Bitmap::~Bitmap() [6]

               0.01    0.00     100/100         generateBitmapImage(unsigned char*, int, int, char const*) [5]

               0.01    0.00     100/100         createBMP(int*, int, int) [2]

[7] 0.0 0.01 0.00 100 Bitmap::Bitmap(char const*, int, int) [7]


               0.00    0.00     100/100         generateBitmapImage(unsigned char*, int, int, char const*) [5]

[15] 0.0 0.00 0.00 100 createBitmapFileHeader(int, int, int) [15]


               0.00    0.00     100/100         generateBitmapImage(unsigned char*, int, int, char const*) [5]

[16] 0.0 0.00 0.00 100 createBitmapInfoHeader(int, int) [16]


               0.00    0.00       1/1           __libc_csu_init [25]

[17] 0.0 0.00 0.00 1 _GLOBAL__sub_I_main [17]


^L Index by function name

 [17] _GLOBAL__sub_I_main (julia.cpp) [3] lerp(float, Pix&, Pix&, Bitmap&) [7] Bitmap::Bitmap(char const*, int, int)
  [5] generateBitmapImage(unsigned char*, int, int, char const*) [1] calcJulia(int*, int, int, float, float) [6] Bitmap::~Bitmap()
 [15] createBitmapFileHeader(int, int, int) [2] createBMP(int*, int, int)
 [16] createBitmapInfoHeader(int, int) [4] Bitmap::addColor(int, int, int)
Call graph


granularity: each sample hit covers 2 byte(s) for 0.00% of 347.05 seconds

index % time self children called name

                                                <spontaneous>

[1] 96.1 333.37 0.00 calcJulia(int*, int, int, float, float) [1]


                                                <spontaneous>

[2] 3.9 1.21 12.47 createBMP(int*, int, int) [2]

               5.74    6.73 791167185/791167185     lerp(float, Pix&, Pix&, Bitmap&) [3]
               0.01    0.00     100/100         Bitmap::Bitmap(char const*, int, int) [5]
               0.00    0.00     100/100         Bitmap::~Bitmap() [16]

               5.74    6.73 791167185/791167185     createBMP(int*, int, int) [2]

[3] 3.6 5.74 6.73 791167185 lerp(float, Pix&, Pix&, Bitmap&) [3]

               6.73    0.00 600000000/600000000     Bitmap::addColor(int, int, int) [4]

               6.73    0.00 600000000/600000000     lerp(float, Pix&, Pix&, Bitmap&) [3]

[4] 1.9 6.73 0.00 600000000 Bitmap::addColor(int, int, int) [4]


               0.01    0.00     100/100         createBMP(int*, int, int) [2]

[5] 0.0 0.01 0.00 100 Bitmap::Bitmap(char const*, int, int) [5]


               0.00    0.00     100/100         Bitmap::~Bitmap() [16]

[13] 0.0 0.00 0.00 100 generateBitmapImage(unsigned char*, int, int, char const*) [13]

               0.00    0.00     100/100         createBitmapFileHeader(int, int, int) [14]
               0.00    0.00     100/100         createBitmapInfoHeader(int, int) [15]

               0.00    0.00     100/100         generateBitmapImage(unsigned char*, int, int, char const*) [13]

[14] 0.0 0.00 0.00 100 createBitmapFileHeader(int, int, int) [14]


               0.00    0.00     100/100         generateBitmapImage(unsigned char*, int, int, char const*) [13]

[15] 0.0 0.00 0.00 100 createBitmapInfoHeader(int, int) [15]


               0.00    0.00     100/100         createBMP(int*, int, int) [2]

[16] 0.0 0.00 0.00 100 Bitmap::~Bitmap() [16]

               0.00    0.00     100/100         generateBitmapImage(unsigned char*, int, int, char const*) [13]

               0.00    0.00       1/1           __libc_csu_init [25]

[17] 0.0 0.00 0.00 1 _GLOBAL__sub_I_main [17]


Index by function name

 [17] _GLOBAL__sub_I_main (julia.cpp) [3] lerp(float, Pix&, Pix&, Bitmap&) [5] Bitmap::Bitmap(char const*, int, int)
 [13] generateBitmapImage(unsigned char*, int, int, char const*) [1] calcJulia(int*, int, int, float, float) [16] Bitmap::~Bitmap()
 [14] createBitmapFileHeader(int, int, int) [2] createBMP(int*, int, int)
 [15] createBitmapInfoHeader(int, int) [4] Bitmap::addColor(int, int, int)



Generated Image of Julia set at (-0.4, 0.6)

Julia.jpg

Assignment 2

Assignment 3