Translate To Preferred Language

Search Obioku's Thoughts

Please Read Today's Featured Post

Things I Would Like To Happen Soon

For all those who believe in speaking ideas into existence and prayer in the universe will return to a person.  I simply want to write a lis...

Template for Finite Mathematics in Java (some bugs may occur)

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package gf2;

//import library packages
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Arrays;
import static java.util.Arrays.copyOf;
import java.util.Scanner;

/**
 *
 * @author obobotette0
 */
public class GF2 {

    /**
     * @param args the command line arguments
     */
    //create method to add polynomials
    static public int[] add(int iDeg1, int nums1[], int iDeg2, int nums2[], int finite) {
        //variable to return result
        int mathResult[] = new int[nums1.length];
        String result[] = new String[mathResult.length];
        int temp[] = new int[1];

        //if polynomial degrees are equal
        if (iDeg1 == iDeg2) {
            int degree = iDeg1;
            //Calculate result
            for (int x = 0; x < nums1.length; x++) {
                //add matching nodes
                mathResult[x] = Integer.valueOf(nums1[x]) + Integer.valueOf(nums2[x]);
                //if greater than zero print with exponenet

                --degree;
            }
        }//else if f(x) degree is greater than g(x)
        else if (iDeg1 > iDeg2) {
            int degree = iDeg1;
            int count = 0;
            for (int x = 0; x < nums1.length; x++) {
                //if one array in longer than the other
                //copy contents till sizes are equal
                if (degree > iDeg2) {
                    mathResult[x] = Integer.valueOf(nums1[x]);

                    --degree;
                    count++;
                } else {
                    //add matching nodes
                    mathResult[x] = Integer.valueOf(nums1[x]) + Integer.valueOf(nums2[x - count]);
                    //if greater than zero print with exponenet

                    --degree;
                }
            }
        }//else f(x) degree is less than g(x)
        else if (iDeg1 < iDeg2) {
            int degree = iDeg2;
            //count difference in arrays
            int count = 0;

            for (int x = 0; x < nums2.length; x++) {
                //if one array in longer than the other
                //copy contents till sizes are equal
                if (degree > iDeg1) {
                    mathResult[x] = Integer.valueOf(nums2[x]);

                    --degree;
                    count++;;

                } else {
                    //add matching nodes
                    mathResult[x] = Integer.valueOf(nums1[x - count]) + Integer.valueOf(nums2[x]);

                    --degree;
                }
            }
        }
        //loop through array to mod coefficient not in finite field
        for (int m = 0; m < mathResult.length; m++) {
            if (Integer.valueOf(mathResult[m]) > finite) {
                mathResult[m] %= finite;
            }
        }

        return mathResult;
    }

    //create method for subtract polynomial
    static public int[] subtract(int iDeg1, int nums1[], int iDeg2, int nums2[], int finite) {
        //variables to return result
        int degree;
        int mathResult[] = new int[nums1.length];
        String result[] = new String[mathResult.length];
        int[] temp = new int[1];

        //if degrees are equal
        if (iDeg1 == iDeg2) {
            degree = iDeg1;
            for (int y = 0; y < nums1.length; y++) {
                //subtract matching nodes
                mathResult[y] = Integer.valueOf(nums1[y]) - Integer.valueOf(nums2[y]);
             
                //keep track of exponent
                --degree;
            }
        }//else if f(x) degree is greater than g(x)
        else if (iDeg1 > iDeg2) {
            degree = iDeg1;
            //count difference in arrays
            int count = 0;

            for (int y = 0; y < nums1.length; y++) {
                //if one array in longer than the other
                //copy contents till sizes are equal
                if (degree > iDeg2) {
                    mathResult[y] = Integer.valueOf(nums1[y]);

                    --degree;
                    count++;
                } else {
                    //subtract matching nodes
                    mathResult[y] = Integer.valueOf(nums1[y]) - Integer.valueOf(nums2[y - count]);
                    //if greater than zero print with eyponenet

                    --degree;
                }
            }
        }//else if f(x) degree is less than g(x)
        else if (iDeg1 < iDeg2) {
            degree = iDeg2;
            //count difference in arrays
            int count = 0;

            for (int y = 0; y < nums2.length; y++) {
                //if one array in longer than the other
                //copy contents till sizes are equal
                if (degree > iDeg1) {
                    mathResult[y] = Integer.valueOf(nums2[y]);

                    --degree;
                    count++;
                } else {
                    //subtract matching nodes
                    mathResult[y] = Integer.valueOf(nums1[y - count]) - Integer.valueOf(nums2[y]);
                    //if greater than zero print with eyponenet

                    --degree;
                }
            }
        }
        for (int m = 0; m < mathResult.length; m++) {
            if (Integer.valueOf(mathResult[m]) < 0) {
                mathResult[m] %= finite;
                mathResult[m] += finite;
            }
        }

        return mathResult;
    }

    static public int[] multiply(int iDeg1, int nums1[], int iDeg2, int nums2[], int mdeg, int mx[], int finite) {
        //create variable to return result
        int degree;
        int degResult[] = new int[nums1.length];
        int mathResult[] = new int[nums1.length];
        int temp[] = new int[nums1.length];
        String result[] = new String[mathResult.length];
        int temp1;

        //if degrees are equal
        if (iDeg1 == iDeg2) {
            degree = iDeg2;

            //int count = 0;
            int i = 0;
            //double for loop
            //multiply element of first polynomial to each element of the second before iteration
            for (int x = 0; x < nums1.length; x++) {
                for (int y = 0; y < nums2.length; y++) {
                    if (nums1[x] != 0 && nums2[y] != 0) {
                        temp[i] = nums1[x] * nums2[y];
                        temp[i] %= finite;
                        degResult[i] = iDeg1 + iDeg2;
                        i++;
                    }
                    iDeg2--;
                }
                iDeg2 = degree;
                iDeg1--;
                //count = i;
            }
        }//else if f(x) degree greater than g(x)
        else if (iDeg1 > iDeg2) {
            degree = iDeg2;
            int i = 0;
            //double for loop
            //multiply element of first polynomial to each element of the second before iteration
            for (int x = 0; x < nums1.length; x++) {
                for (int y = 0; y < nums2.length; y++) {
                    if (nums1[x] != 0 && nums2[y] != 0) {
                        temp[i] = nums1[x] * nums2[y];
                        temp[i] %= finite;
                        degResult[i] = iDeg1 + iDeg2;
                        i++;
                    }
                    iDeg2--;
                }
                iDeg2 = degree;
                iDeg1--;
            }
        }//else f(x) degree is less than g(x)
        else if (iDeg1 < iDeg2) {
            degree = iDeg1;
            int i = 0;
            //double for loop
            //multiply element of first polynomial to each element of the second before iteration
            for (int x = 0; x < nums2.length; x++) {
                for (int y = 0; y < nums1.length; y++) {
                    if (nums1[x] != 0 && nums2[y] != 0) {
                        temp[i] = nums1[x] * nums2[y];
                        temp[i] %= finite;
                        degResult[i] = iDeg1 + iDeg2;
                        i++;
                    }
                    iDeg1--;
                }
                iDeg1 = degree;
                iDeg2--;
            }
        }
        //for loop to add element with the same degree
        //Begins at second node
        for (int x = 1; x < mathResult.length; x++) {
            //System.out.println("res " + Arrays.toString(mathResult));
            //before search array return first element
            if (x == 1) {
                mathResult[x - 1] = temp[x - 1];
            }
            //if degree of current element is equal to that of previous element
            //add together and mod result
            if (degResult[x] == degResult[x - 1]) {
                mathResult[x - 1] = temp[x] + temp[x - 1];
                mathResult[x - 1] %= finite;
            }//else return result as is
            else {
                mathResult[x] = temp[x];
            }
        }
        //search through array to remove zero coefficient results
        for (int x = 0; x < mathResult.length - 1; x++) {
            if (mathResult[x] == 0 && mathResult[x + 1] != 0) {
                mathResult[x] = mathResult[x + 1];
                mathResult[x + 1] = 0;
            }
        }

        //check for irreducible polynomial
        if (degResult[0] >= mdeg) {
            mathResult = modulus(mdeg, mx, degResult[0], mathResult, finite);
        }

        //remove leading zero if necessary
        if (mathResult[0] == 0) {
            for (int b = 1; b < mathResult.length; b++) {
                temp1 = mathResult[b];
                mathResult[b - 1] = temp1;
            }
        }

        return mathResult;
    }

    static public int[] divide(int iDeg1, int divisor[], int iDeg2, int dividend[], int finite) {
         <- n="" nbsp="" p="" x=""><- n="" nbsp="" p="" x="">/*PLDA(n(x), d(x))
          * perform mod p to every coefficient of n(x)
          * perform mod p to every coefficient of d(x)
          * (q(x), r(x))          while r(x) != 0 and deg(r(x)) >= deg(d(x)) do
          * t(x) 
         /* 
         * lead() returns the leading term of a polynomial,
         * it needs GF1 to compute the division lead(r(x))/lead(d(x)).
         * For example, if r(x) = 2x^2 + x + 1, d(x) = 3x + 2, and p = 7, 
         * then lead(r(x)) = 2x^2, lead(d(x)) = 3x,
         * t(x) = 2x^2/3x = (2/3)(x^2/x) = 3x,
         * it needs GF1 to compute 2/3 = 3 in Z_7.
<- n="" nbsp="" p="" x="">         * (q(x), r(x)) 
         * perform mod p to every coefficient of q(x)
         * perform mod p to every coefficient of r(x)
         * return (q(x), r(x))*/
        //create variables to return result
        int degree = 0;
        int i = 0;
        int q1;
        int r1;
        int inv[] = new int[2];
        String q = new String();
        int quot[] = new int[dividend.length];
        int r[] = new int[dividend.length];
        int degResult[] = new int[dividend.length];
        int mathResult[] = new int[dividend.length];
        int temp[] = new int[dividend.length];
        int temp1;

        //Create multiple inverse for division result  
        inv = EEA(divisor[0], finite);
        //get first coefficient of quotient
        q1 = dividend[0] * inv[0];

        //If case to return to finite field
        if (q1 < 0) {
            q1 %= finite;
            q1 += finite;
        }

        //Multiple quotient by each element of divisor
        for (int a = 0; a < divisor.length; a++) {
            temp[a] = divisor[a] * q1;
            temp[a] %= finite;
        }
        if (q1 != 0) {

            degResult[i] = q1;
            i++;

        }
        //perform subtraction for remainder
        //mathResult = subtract(iDeg2, dividend, iDeg2, temp, finite);

        //remove leading zero if necessary
        if (mathResult[0] == 0) {
            for (int b = 1; b < mathResult.length; b++) {
                temp1 = mathResult[b];
                mathResult[b - 1] = temp1;
            }
        }

        //recalculate degree of math result
        for (int a = 0; a < mathResult.length - 1; a++) {
            if (mathResult[a] != 0 && mathResult[a + 1] != 0) {
                degree = a + 1;
            }
        }

        //if degree of remainder greater than divisor
        //call divide again
        if (iDeg2 > iDeg1) {
            return mathResult = divide(iDeg1, divisor, degree, mathResult, finite);
        }

        return mathResult;
    }

        static public int[] finite_divide(int iDeg1, int divisor[], int iDeg2, int dividend[], int iDeg3, int ireduce[], int finite) {
        /*PLDA(n(x), d(x))
          * perform mod p to every coefficient of n(x)
          * perform mod p to every coefficient of d(x)
          * (q(x), r(x))          while r(x) != 0 and deg(r(x)) >= deg(d(x)) do
          * t(x)
         /*
         * lead() returns the leading term of a polynomial,
         * it needs GF1 to compute the division lead(r(x))/lead(d(x)).
         * For example, if r(x) = 2x^2 + x + 1, d(x) = 3x + 2, and p = 7,
         * then lead(r(x)) = 2x^2, lead(d(x)) = 3x,
         * t(x) = 2x^2/3x = (2/3)(x^2/x) = 3x,
         * it needs GF1 to compute 2/3 = 3 in Z_7.
<- n="" nbsp="" p="" x="">         * (q(x), r(x))
         * perform mod p to every coefficient of q(x)
         * perform mod p to every coefficient of r(x)
         * return (q(x), r(x))*/
        //create variables to return result
        int degree = 0;
        int i = 0;
        int q1;
        int r1;
        int inv[] = new int[2];
        String q = new String();
        int poly_inv[] = new int[dividend.length];
        int r[] = new int[dividend.length];
        int degResult[] = new int[dividend.length];
        int mathResult[] = new int[dividend.length];
        int temp[] = new int[dividend.length];
        int temp1;

        //Create multiple inverse for division result  
        inv = EEA(divisor[0], finite);
        poly_inv = EEAP(iDeg1, divisor, iDeg3, ireduce, finite);
        degree = iDeg3 - iDeg1;
     
        //Multiple quotient by each element of divisor
        for (int a = 0; a < poly_inv.length; a++) {
            if(poly_inv[a] < 0){
                poly_inv[a] %= finite;
                poly_inv[a] += finite;
            }else{
                poly_inv[a] %= finite;
            }
        }
     
        //perform multiplication
        mathResult = multiply(iDeg2, dividend, degree, poly_inv, iDeg3, ireduce, finite);

        //remove leading zero if necessary
        if (mathResult[0] == 0) {
            for (int b = 1; b < mathResult.length; b++) {
                temp1 = mathResult[b];
                mathResult[b - 1] = temp1;
            }
        }

        //recalculate degree of math result
        for (int a = 0; a < mathResult.length - 1; a++) {
            if (mathResult[a] != 0 && mathResult[a + 1] != 0) {
                degree = a + 1;
            }
        }

        return mathResult;
    }
     
    static public int[] modulus(int iDeg1, int divisor[], int iDeg2, int dividend[], int finite) {
        //create variables to return result
        int degree;
        int i = 0;
        int inv[] = new int[2];
        int q[] = new int[dividend.length];
        int r[] = new int[dividend.length];
        int degResult[] = new int[dividend.length];
        int mathResult[] = new int[dividend.length];
        int temp[] = new int[dividend.length];

        if (iDeg1 > iDeg2) {
            mathResult = dividend;
            return mathResult;
        } else {

            //perform EEA on leading cofficient of divisor and finite number
            inv = EEA(divisor[0], finite);
            //if inverse is less than zero
            if (inv[0] < 0) {
                //mod result than add to return to field
                inv[0] %= finite;
                inv[0] += finite;
            } else {
                inv[0] %= finite;
            }

            //multiple inverse and first element of dividend for first cofficient of the quotient
            q[i] = dividend[0] * inv[0];
            q[i] %= finite;
            //subtract degree of divisor from degree of dividend
            degree = iDeg2 - iDeg1;
            //multiple quotient with each element of the divisor
            for (int x = 0; x < divisor.length; x++) {
                temp[x] = divisor[x] * q[i];
                temp[x] %= finite;
                //System.out.println("temp d q " + temp[x] + divisor[x] + q[i]);
            }
            //move to next quotient location
            i++;
            //add degree of quotient with degree of divisor
            degResult[0] = degree + iDeg1;
            //subtract to find remainder
            mathResult = subtract(iDeg2, dividend, degResult[0], temp, finite);

            //if remainer degree is greater than divisor repeat
            if (degResult[0] > iDeg1) {
                //System.out.println("degree " + degResult[0] + iDeg1);
                mathResult = modulus(iDeg1, divisor, degResult[0], mathResult, finite);
            }

            return mathResult;
        }
    }

    static public int[] EEA(int a, int b) {
        if (b == 0) {
            return new int[]{1, 0};
        } else {
            int q = a / b;
            int r = a % b;
            int[] R = EEA(b, r);
            return new int[]{R[1], R[0] - q * R[1]};
        }
    }

    static public int[] EEAP(int deg1, int a[], int deg2, int b[], int c) {
        int deg;
        int ideg;
        //Create test variables for irreducible polynomial
        int mdeg = 10;
        int[] mx = {1};
        //temp
        int[] temp = new int[b.length];
        int[] R = new int[b.length];
        int[] q = new int[b.length];
        int[] r = new int[b.length];

        if (b[0] == 0) {
            try{
            R = EEA(a[0], c);
            }catch (StackOverflowError e){
                    return new int[]{R[0], b[0]};
                    }      
            return new int[]{R[0], b[0]};
         
         
        } else {
            q = divide(deg1, a, deg2, b, c);
            deg = deg2 - deg1;
            r = modulus(deg1, a, deg2, b, c);

            for (int loop = 0; loop < q.length; loop++) {
                q[loop] %= c;
            }
            for (int loop = 0; loop < r.length; loop++) {
                r[loop] %= c;
            }
            R = EEAP(deg2, b, deg, r, c);

            temp = multiply(deg, q, deg - 1, R, mdeg, mx, c);
            ideg = deg + deg - 1;
            temp = subtract(deg, R, deg, temp, c);
            return new int[]{R[0], temp[0]};
        }
    }

    public static void main(String[] args) throws FileNotFoundException, IOException {
        // TODO code application logic here

        //Variables
        int answer[] = new int[5];
        int answer_deg[] = new int[5];
        int prime;
        int m_deg;
        int m_x[] = new int[5];
        int f_deg;
        int f_x[] = new int[5];
        int g_deg;
        int g_x[] = new int[5];
        int iterator = 0;
        //int count;
        String read = new String();
        String str_convert[] = new String[7];
        String save[] = new String[7];

        //String inputString = "..\\GF2\\src\\gf2\\input (another sample)(13).txt";
        String inputString = "..\\GF2\\src\\gf2\\input.txt";
        //String inputString = "..\\GF2\\src\\gf2\\input(13).txt";
        String outputString = "..\\GF2\\src\\gf2\\output.txt";

        //variable for input file
        File inputFile = new File(inputString);
        BufferedReader readFile = new BufferedReader(new FileReader(inputFile));

        //loop to read file line by line
        read = readFile.readLine();
        while (read != null) {
            save[iterator] = read;
            read = readFile.readLine();
            iterator++;
        }

        //close input file
        readFile.close();

        //Begin to parse strings
        prime = Integer.valueOf(save[0]);
        m_deg = Integer.valueOf(save[1]);
        f_deg = Integer.valueOf(save[3]);
        g_deg = Integer.valueOf(save[5]);
        str_convert = save[2].split(" ");
        for (int i = 0; i < str_convert.length; i++) {
            m_x[i] = Integer.valueOf(str_convert[i]);
        }
        str_convert = save[4].split(" ");
        for (int i = 0; i < str_convert.length; i++) {
            f_x[i] = Integer.valueOf(str_convert[i]);
        }
        str_convert = save[6].split(" ");
        for (int i = 0; i < str_convert.length; i++) {
            g_x[i] = Integer.valueOf(str_convert[i]);
        }

        //Variables for output file
        FileWriter outputFile = new FileWriter(outputString);
        PrintWriter writeFile = new PrintWriter(outputFile);
        String print = new String();

        //static public int[] add(int iDeg1, int nums1[], int iDeg2, int nums2[], int finite)
        answer = add(f_deg, f_x, g_deg, g_x, prime);
        //print result
        print = Arrays.toString(f_x) + " + " + Arrays.toString(g_x) + " = " + Arrays.toString(answer) + " in finite field of " + prime;
        writeFile.append(print);
        writeFile.println("");
        System.out.println("Add " + Arrays.toString(answer));
        answer = subtract(f_deg, f_x, g_deg, g_x, prime);
        //print result
        print = Arrays.toString(f_x) + " - " + Arrays.toString(g_x) + " = " + Arrays.toString(answer) + " in finite field of " + prime;
        writeFile.append(print);
        writeFile.println("");
        System.out.println("Sub " + Arrays.toString(answer));
        //answer = Arrays.copyOf(answer, answer.length + 1);
        answer = multiply(f_deg, f_x, g_deg, g_x, m_deg, m_x, prime);
        //print result
        print = Arrays.toString(f_x) + " * " + Arrays.toString(g_x) + " = " + Arrays.toString(answer) + " in finite field of " + prime;
        writeFile.append(print);
        writeFile.println("");
        System.out.println("Mul " + Arrays.toString(answer));
        /*answer = finite_divide(g_deg, g_x, f_deg, f_x, m_deg, m_x, prime);
        print = Arrays.toString(f_x) + " / " + Arrays.toString(g_x) + " = " + Arrays.toString(answer) + " in finite field of " + prime;
        writeFile.append(print);
        writeFile.println("");
        System.out.println("Div " + Arrays.toString(answer));*/
        answer = divide(f_deg, f_x, g_deg, g_x, prime);
        print = Arrays.toString(f_x) + " / " + Arrays.toString(g_x) + " = " + Arrays.toString(answer) + " in finite field of " + prime;
        writeFile.append(print);
        writeFile.println("");
        System.out.println("Div " + Arrays.toString(answer));
        writeFile.flush();
    }

}

No comments:

Post a Comment

Thank you very much for viewing this entry and I hope you are able to return soon to continue to enjoy more of the site.
Please share your thoughts in the comment section.
Be blessed and enjoy life!