Solving a linear system of equations
public class App {
public static void main(String[] args) throws Exception {
// First, define the tolerance
double epsilon = 5E-6;
// Define maximum number of iterations
int maxIters = 500;
// Define the initial values/seed (x0^0)
double[] x0 = {0,0,0,0,0,0};
// Define the matrix of coefficients
double[][] M = {
{4, -1, 0, -2, 0, 0}, // coefficients for first equation
{-1, 4, -1, 0, -2, 0}, // second equation
{0, -1, 4, 0, 0, -2}, // third
{-1, 0, 0, 4, -1, 0}, // fourth
{0, -1, 0, -1, 4, -1}, // ...
{0, 0, -1, 0, -1, 4} // last equation
};
// Define vector b (equalities)
double[] b = {-1, 0, 1, -2, 1, 2};
// Call method
Jacobi(M, b, x0, epsilon, maxIters);
System.out.println("");
GaussSeidel(M, b, x0, epsilon, maxIters);
}
public static void Jacobi(double[][] M, double[] b, double[] x0, double epsilon, int maxIters)
{
System.out.println(" *** JACOBI METHOD *** ");
System.out.println("Solving the following system:");
System.out.println("Number of variables: " + b.length);
System.out.println("Toleance: " + epsilon);
System.out.println("Max. number of iterations: " + maxIters);
System.out.println("The system is:\n");
// Define initial error
double err = 1E+10; // a rally big number
// Define number of equations/variables
int N = b.length;
// Print equations so user can see them
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
System.out.print(M[i][j]+"*x" + (j+1) + " ");
}
System.out.print("= " + b[i] + "\n");
}
System.out.println("");
System.out.println("Starting iterations... ");
// Start iterations
double[] xold = x0; // varray to store old values (from previous iteration)
double[] xnew = xold.clone(); // array to store the result of the new iteration
int iterCounter = 0; // variable to count the iterations
double xi, erri; // helper variables to be used in the method
while(err > epsilon)
{
iterCounter++;
// Jacobi Method
for(int i = 0; i < N ;i++)
{
xi = b[i];
for(int j = 0; j < N; j++)
{
if(i != j)
xi -= M[i][j] * xold[j];
}
xi = xi/M[i][i];
xnew[i] = xi;
}
// Calculate errors and pick maximum
/*
For this method the error is calculated as the difference between the old solution and
the new one.
*/
double maxErr = -1;
for(int i = 0; i < N; i++)
{
erri = Math.abs((xnew[i]-xold[i]));
if(erri > maxErr)
maxErr = erri;
}
xold = xnew.clone(); // For the next iteration, the old_values are the new_values in this one
err = maxErr;
System.out.println("Iteration " + iterCounter + ", Err: " + err);
if(iterCounter == maxIters) // reached maximum number of iterations
{
System.out.println("Maximum number of iterations reached. Last error: " + err);
break;
}
}
// Display results only if the system converged
if(iterCounter < maxIters && err <= epsilon)
{
System.out.println("");
System.out.println("Convergence achieved in " + iterCounter + " iterations. Min error was: " + err);
System.out.println("The solution is:");
for(int i = 0; i < N; i++)
{
System.out.println("x[" + (i+1) + "] = " + xnew[i]);
}
}
}
public static void GaussSeidel(double[][] M, double[] b, double[] x0, double epsilon, int maxIters)
{
System.out.println(" *** GAUSS-SEIDEL METHOD *** ");
System.out.println("Solving the following system:");
System.out.println("Number of variables: " + b.length);
System.out.println("Toleance: " + epsilon);
System.out.println("Max. number of iterations: " + maxIters);
System.out.println("The system is:\n");
// Define initial error
double err = 1E+10; // a rally big number
// Define number of equations/variables
int N = b.length;
// Display equations
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
{
System.out.print(M[i][j]+"*x" + (j+1) + " ");
}
System.out.print("= " + b[i] + "\n");
}
System.out.println("");
System.out.println("Starting iterations... ");
// Start iterations
double[] x = x0; // vector of solutions is setted to the initial values
int iterCounter = 0; // variable to count interations
double xi, erri; // helper variables
double sigma; // helper variable for gauss-Seidel method
// Start iterations
while(err > epsilon)
{
iterCounter++;
// Gauss-Seidel method
for(int i = 0; i < N ;i++)
{
sigma = 0;
for(int j = 0; j < N; j++)
{
if(i != j)
sigma += M[i][j]*x[j];
}
xi = (b[i]-sigma)/M[i][i];
x[i] = xi;
}
// Calculate errors and pick maximum
/*
For this method the error is calculated as the value of the functions for the current solution.
The method converges when the value of the function f(xi)-bi = 0 is less than epsilon
*/
double maxErr = -1;
for(int i = 0; i < N; i++)
{
erri = 0;
for(int j = 0; j < N; j++)
{
erri += M[i][j]*x[j];
}
erri -= b[i];
erri = Math.abs(erri);
if(erri > maxErr)
maxErr = erri;
}
//xold = xnew.clone(); // the results of this iterations are the old for the next iteration
err = maxErr;
System.out.println("Iteration " + iterCounter + ", Err: " + err);
if(iterCounter == maxIters) // reached max number of iters
{
System.out.println("Maximum number of iterations reached. Last error: " + err);
break;
}
}
if(iterCounter < maxIters && err <= epsilon) // display results only if system converged
{
System.out.println("");
System.out.println("Convergence achieved in " + iterCounter + " iterations. Min error was: " + err);
System.out.println("The solution is:");
for(int i = 0; i < N; i++)
{
System.out.println("x[" + (i+1) + "] = " + x[i]);
}
}
}
}
Data encryption and decryption
#include
#include
#include
// get_keys(char *, unsigned *, unsigned *)
// - Extracts two 8-bit keys from 8 bytes
void get_keys(char *twokeys, unsigned *key1, unsigned *key2)
{
int i;
char *key;
if (strlen(twokeys) != 8)
{
printf("Password must be exactly 8 characters long.\n");
exit(1);
}
key = twokeys;
key1[0] = 0;
for (i = 0; i< 4; i++)
// move 7 bits at a time, add character reduced to 7 bits
key1[0] = (key1[0] << 7) | (*(key++) & 0x7F);
key2[0] = 0;
for (i = 0; i< 4; i++)
// move 7 bits at a time, add character reduced to 7 bits
key2[0] = (key2[0] << 7) | (*(key++) & 0x7F);
}
// get_n_bits(unsigned, int, int)
// - Returns the integer value of a specified subsequence of 32 bits
// - width is the number of bits to be extracted
// - index*width is the index of the rightmost bit to extract
unsigned get_n_bits(unsigned bits, int width, int index)
{
bits >>= (index*width); // move required bits down
return bits & ((1 << width) - 1); // return only width bits
}
// shuffle_nibbles(unsigned *)
// - shuffles the nibbles in the argument according to the pattern
void shuffle_nibbles(unsigned *bits)
{
int i;
int shuffle[] = {6,5,4,0,2,1,3}; // shuffle sequence
int nibbles[7];
for (i = 0; i< 7; i++)
// get nibble and shuffle it
nibbles[shuffle[i]] = get_n_bits(bits[0], 4, i);
bits[0] = 0;
// build resulting number using the nibbles
for (i = 6; i>= 0; i--)
bits[0] = (bits[0] << 4) | nibbles[i];
}
// rotate_left(unsigned)
// - Given a sequence of 7 bits, rotates 3 bits to the left
unsigned rotate_left(unsigned bits)
{
int i;
unsigned bit;
for (i = 0; i< 3; i++)
{
bit = (bits & 0x40) != 0; // get 7th bit value
bits = ((bits << 1) & 0x7F) | bit; // shift left and add rotated bit
}
return bits;
}
// rotate_septets(unsigned *)
// - Rotates every 7 bits of the argument 3 times to the left
// - returns the resulting rotation
unsigned rotate_septets(unsigned bits)
{
int i;
unsigned rotated = 0;
for (i = 3; i>= 0; i--)
{
// get septet and rotate it, save in rotated number
rotated = (rotated << 7) | rotate_left(get_n_bits(bits, 7, i));
}
return rotated;
}
// septets_to_chars(unsigned, char *)
// - Converts every 7 bits in the bits argument to a character and saves it
// - in the plain argument, adds an ending zero to end the string
void septets_to_chars(unsigned bits, char *plain)
{
int i, j;
for (i = 3, j = 0; i>= 0; i--, j++)
{
// get septet and use it as char
plain[j] = get_n_bits(bits, 7, i);
}
plain[j] = 0;
}
// decode_28bits(unsigned, char *, unsigned, unsigned)
// - Decodes the 28bit block given in the first argument to a plain
// - text saved in the second argument, uses the key pair given
// - in the third and fourth arguments
void decode_28bits(unsigned cipher, char *plain, unsigned key1, unsigned key2)
{
cipher ^= key2; // xor with key2
shuffle_nibbles(&cipher); // shuffle the nibbles
cipher ^= key1; // xor with key1
cipher = rotate_septets(cipher); // rotate septets
septets_to_chars(cipher, plain); // convert septets to characters
}
// ishex(char)
// - Returns 1 if the given char is a hexadecimal digit,
// - and 0 otherwise
int ishex(char c)
{
return (c >= '0' && c <= '9')
|| (c >= 'a' && c <= 'f')
|| (c >= 'A' && c <= 'F');
}
// hextodec(char)
// - converts the given hexadecimal digit to a decimal number
int hextodec(char c)
{
if (c >= '0' && c <= '9')
return c - '0';
else if (c >= 'a' && c <= 'f')
return c - 'a' + 10;
else if (c >= 'A' && c <= 'F')
return c - 'A' + 10;
return -1; // for invalid hex digits
}
// decrypt(int, int)
// - Decrypts the input read from the standard input with the two
// - 28bit keys given as arguments
// - prints the result on the standard output
void decrypt(int key1, int key2)
{
int c;
unsigned int bits;
unsigned int digit;
int n;
char plain[5];
bits = 0;
n = 0;
while (1)
{
if (n >= 7) // if we have completed 7 hex digits
{
decode_28bits(bits, plain, key1, key2); // decode the 28bit cipher
printf("%s", plain); // print the output
bits = 0;
n = 0;
}
c = fgetc(stdin); // read new char from input
if (feof(stdin)) // if end of input, terminate loop
break;
else if (ishex(c))
{
digit = hextodec(c); // convert hex digit
bits = (bits << 4) | digit; // add 4 bits to number
n++; // increment number of hex digits
}
}
printf("\n");
}
int main(int argc, char **argv)
{
char *password;
unsigned key1, key2;
if (argc< 2)
{
fprintf(stderr, "Password missing\n");
exit(1);
}
password = argv[1];
get_keys(password, &key1, &key2); // get the 28bit keys
decrypt(key1, key2); // start decrypting using the password
return (0);
}
