@Test public void testAutomaticConvolution() { int[] actual = SmallNumberTheoreticTransform.circularConvolve( new int[]{4, 1, 4, 2, 1, 3, 5, 6}, new int[]{6, 1, 8, 0, 3, 3, 9, 8}); int[] expect = {123, 120, 106, 92, 139, 144, 140, 124}; assertArrayEquals(expect, actual); }
public static int[] circularConvolve(int[] vec0, int[] vec1) { if (vec0.length == 0 || vec0.length != vec1.length) throw new IllegalArgumentException(); int maxval = Integer.MIN_VALUE; for (int x : vec0) { if (x < 0) throw new IllegalArgumentException(); maxval = Math.max(x, maxval); } for (int x : vec1) { if (x < 0) throw new IllegalArgumentException(); maxval = Math.max(x, maxval); } BigInteger minmod = BigInteger.valueOf(maxval).pow(2) .multiply(BigInteger.valueOf(vec0.length)).add(BigInteger.ONE); if (minmod.bitLength() > 31) throw new ArithmeticException(); int mod = findModulus(vec0.length, minmod.intValue()); int root = findPrimitiveRoot(vec0.length, mod - 1, mod); int[] temp0 = transform(vec0, root, mod); int[] temp1 = transform(vec1, root, mod); int[] temp2 = new int[temp0.length]; for (int i = 0; i < temp0.length; i++) temp2[i] = (int)((long)temp0[i] * temp1[i] % mod); return inverseTransform(temp2, root, mod); }
SmallNumberTheoreticTransform { public static int[] circularConvolve(int[] vec0, int[] vec1) { if (vec0.length == 0 || vec0.length != vec1.length) throw new IllegalArgumentException(); int maxval = Integer.MIN_VALUE; for (int x : vec0) { if (x < 0) throw new IllegalArgumentException(); maxval = Math.max(x, maxval); } for (int x : vec1) { if (x < 0) throw new IllegalArgumentException(); maxval = Math.max(x, maxval); } BigInteger minmod = BigInteger.valueOf(maxval).pow(2) .multiply(BigInteger.valueOf(vec0.length)).add(BigInteger.ONE); if (minmod.bitLength() > 31) throw new ArithmeticException(); int mod = findModulus(vec0.length, minmod.intValue()); int root = findPrimitiveRoot(vec0.length, mod - 1, mod); int[] temp0 = transform(vec0, root, mod); int[] temp1 = transform(vec1, root, mod); int[] temp2 = new int[temp0.length]; for (int i = 0; i < temp0.length; i++) temp2[i] = (int)((long)temp0[i] * temp1[i] % mod); return inverseTransform(temp2, root, mod); } }
SmallNumberTheoreticTransform { public static int[] circularConvolve(int[] vec0, int[] vec1) { if (vec0.length == 0 || vec0.length != vec1.length) throw new IllegalArgumentException(); int maxval = Integer.MIN_VALUE; for (int x : vec0) { if (x < 0) throw new IllegalArgumentException(); maxval = Math.max(x, maxval); } for (int x : vec1) { if (x < 0) throw new IllegalArgumentException(); maxval = Math.max(x, maxval); } BigInteger minmod = BigInteger.valueOf(maxval).pow(2) .multiply(BigInteger.valueOf(vec0.length)).add(BigInteger.ONE); if (minmod.bitLength() > 31) throw new ArithmeticException(); int mod = findModulus(vec0.length, minmod.intValue()); int root = findPrimitiveRoot(vec0.length, mod - 1, mod); int[] temp0 = transform(vec0, root, mod); int[] temp1 = transform(vec1, root, mod); int[] temp2 = new int[temp0.length]; for (int i = 0; i < temp0.length; i++) temp2[i] = (int)((long)temp0[i] * temp1[i] % mod); return inverseTransform(temp2, root, mod); }  }
SmallNumberTheoreticTransform { public static int[] circularConvolve(int[] vec0, int[] vec1) { if (vec0.length == 0 || vec0.length != vec1.length) throw new IllegalArgumentException(); int maxval = Integer.MIN_VALUE; for (int x : vec0) { if (x < 0) throw new IllegalArgumentException(); maxval = Math.max(x, maxval); } for (int x : vec1) { if (x < 0) throw new IllegalArgumentException(); maxval = Math.max(x, maxval); } BigInteger minmod = BigInteger.valueOf(maxval).pow(2) .multiply(BigInteger.valueOf(vec0.length)).add(BigInteger.ONE); if (minmod.bitLength() > 31) throw new ArithmeticException(); int mod = findModulus(vec0.length, minmod.intValue()); int root = findPrimitiveRoot(vec0.length, mod - 1, mod); int[] temp0 = transform(vec0, root, mod); int[] temp1 = transform(vec1, root, mod); int[] temp2 = new int[temp0.length]; for (int i = 0; i < temp0.length; i++) temp2[i] = (int)((long)temp0[i] * temp1[i] % mod); return inverseTransform(temp2, root, mod); }  static int[] transform(int[] invec, int root, int mod); static int[] inverseTransform(int[] invec, int root, int mod); static void transformRadix2(int[] vector, int root, int mod); static int[] circularConvolve(int[] vec0, int[] vec1); static int findModulus(int vecLen, int minimum); static int findGenerator(int totient, int mod); static int findPrimitiveRoot(int degree, int totient, int mod); static boolean isGenerator(int val, int totient, int mod); static boolean isPrimitiveRoot(int val, int degree, int mod); static int reciprocal(int n, int mod); static List<Integer> uniquePrimeFactors(int n); static boolean isPrime(int n); static int pow(int x, int y, int mod); static int sqrt(int x); }
SmallNumberTheoreticTransform { public static int[] circularConvolve(int[] vec0, int[] vec1) { if (vec0.length == 0 || vec0.length != vec1.length) throw new IllegalArgumentException(); int maxval = Integer.MIN_VALUE; for (int x : vec0) { if (x < 0) throw new IllegalArgumentException(); maxval = Math.max(x, maxval); } for (int x : vec1) { if (x < 0) throw new IllegalArgumentException(); maxval = Math.max(x, maxval); } BigInteger minmod = BigInteger.valueOf(maxval).pow(2) .multiply(BigInteger.valueOf(vec0.length)).add(BigInteger.ONE); if (minmod.bitLength() > 31) throw new ArithmeticException(); int mod = findModulus(vec0.length, minmod.intValue()); int root = findPrimitiveRoot(vec0.length, mod - 1, mod); int[] temp0 = transform(vec0, root, mod); int[] temp1 = transform(vec1, root, mod); int[] temp2 = new int[temp0.length]; for (int i = 0; i < temp0.length; i++) temp2[i] = (int)((long)temp0[i] * temp1[i] % mod); return inverseTransform(temp2, root, mod); }  static int[] transform(int[] invec, int root, int mod); static int[] inverseTransform(int[] invec, int root, int mod); static void transformRadix2(int[] vector, int root, int mod); static int[] circularConvolve(int[] vec0, int[] vec1); static int findModulus(int vecLen, int minimum); static int findGenerator(int totient, int mod); static int findPrimitiveRoot(int degree, int totient, int mod); static boolean isGenerator(int val, int totient, int mod); static boolean isPrimitiveRoot(int val, int degree, int mod); static int reciprocal(int n, int mod); static List<Integer> uniquePrimeFactors(int n); static boolean isPrime(int n); static int pow(int x, int y, int mod); static int sqrt(int x);  }