Translate To Preferred Language

Search ObiokusThoughts

Please Read Today's Featured Post

Alliteration Ere Zeitgeist

Actually ask archaic adult Broadband boy baked bad batch Cold case cant consistently catch Dawn developed dusk do-over Enact emerge...

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) {
        /*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)) <- n="" nbsp="" p="" x="">         while r(x) != 0 and deg(r(x)) >= deg(d(x)) do
         t(x) <- class="Apple-tab-span" d="" lead="" r="" span="" style="white-space: pre;" 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.

         (q(x), r(x)) <- -="" class="Apple-tab-span" d="" q="" r="" span="" style="white-space: pre;" t="" 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)) <- n="" nbsp="" p="" x="">         while r(x) != 0 and deg(r(x)) >= deg(d(x)) do
         t(x) <- class="Apple-tab-span" d="" lead="" r="" span="" style="white-space: pre;" 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.

         (q(x), r(x)) <- -="" class="Apple-tab-span" d="" q="" r="" span="" style="white-space: pre;" t="" 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 for reading.
Please share your thoughts.
Be blessed and enjoy life!