// Von http://www.java-forum.org/java-basics-anfaenger-themen/83464-array-multiplikations-problem-2.html#post520557
// Erweitert um mult2 + test + benchmark
import java.util.*;
import java.math.*;
class ArrayMulTest2
{
private static Random random = new Random(0);
public static void main(String[] args)
{
test();
//benchmark();
}
private static void test()
{
for (int a=2; a<5; a++)
{
for (int b=2; b<5; b++)
{
int input[] = generateRandomNumber(a,10);
int factor[] = generateRandomNumber(b,10);
int resultMult[] = mult(input, factor);
int resultMult2[] = mult2(input, factor, 10);
BigInteger i = bigIntegerBase10(input);
BigInteger f = bigIntegerBase10(factor);
BigInteger r = i.multiply(f);
BigInteger m = bigIntegerBase10(mult(input, factor, 10));
BigInteger m2 = bigIntegerBase10(mult2(input, factor, 10));
System.out.println("input "+i);
System.out.println("factor "+f);
System.out.println("mult "+m);
System.out.println("mult2 "+m2);
System.out.println("BigDecimal "+r);
if (!m.equals(r)) System.out.println("--- mult failed ---");
if (!m2.equals(r)) System.out.println("--- mult2 failed ---");
}
}
}
private static void benchmark()
{
int runs = 10;
for (int digits = 1000; digits <= 5000; digits+=1000)
{
int input[] = generateRandomNumber(digits,10);
int factor[] = generateRandomNumber(digits,10);
long s, before, after;
s = 0;
before = System.nanoTime();
for (int i=0; i<runs; i++)
{
int result[] = mult(input, factor);
s += result.length;
}
after = System.nanoTime();
System.out.println(s+" mult "+((after-before)/1000000));
s = 0;
before = System.nanoTime();
for (int i=0; i<runs; i++)
{
int result[] = mult2(input, factor, 10);
s += result.length;
}
after = System.nanoTime();
System.out.println(s+" mult2 "+((after-before)/1000000));
}
}
private static BigInteger bigIntegerBase10(int array[])
{
String s = "";
for (int i=0; i<array.length; i++)
{
s += array[i];
}
return new BigInteger(s);
}
private static int[] generateRandomNumber(int digits, int base)
{
int a[] = new int[digits];
for (int i=0; i<digits; i++)
{
a[i] = 1+random.nextInt(base-1);
}
return a;
}
private static int[] mult2(int input[], int factor[], int base)
{
int result[] = new int[input.length+factor.length];
int ii = 0;
for (int i = factor.length - 1; i >= 0; i--, ii++)
{
int overflow = 0;
int ij = 0;
for (int j=input.length-1; j >= 0; j--, ij++)
{
int k = result.length - 1 - ii - ij;
int r = factor[i] * input[j] + overflow;
//System.out.println("mul "+input[j]+" with "+factor[i]+" add "+overflow+" result at "+k+" is "+r);
result[k] += r;
overflow = result[k] / base;
result[k] -= ((overflow << 3) + (overflow << 1));
//System.out.println("result now ");
//print(result);
}
int index = 1;
while (overflow > 0)
{
int k = result.length - 1 - ii - (input.length - 1) - index;
result[k] += overflow;
overflow = result[k] / base;
result[k] -= ((overflow << 3) + (overflow << 1));
index++;
//System.out.println("result now after overflow ");
//print(result);
}
}
return result;
}
public static void print(int[] array)
{
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]);
}
System.out.println();
}
public static int[] mult(int[] inp, int[] mult) {
return mult(inp, mult, 10);
}
public static int[] mult(int[] inp, int[] mult, int base) {
int array[] = new int[inp.length];
System.arraycopy(inp, 0, array, 0, inp.length);
int[] overflow = { 0 };
for (int i = array.length - 1; i >= 0; i--) {
int[] sum = add(mult(array[i], mult, base), overflow, base);
array[i] = sum[sum.length - 1];
overflow = new int[sum.length - 1];
System.arraycopy(sum, 0, overflow, 0, sum.length - 1);
}
while (overflow.length > 0 && overflow[overflow.length - 1] > 0) {
int[] tmp = new int[array.length + 1];
System.arraycopy(array, 0, tmp, 1, array.length);
array = tmp;
array[0] = overflow[overflow.length - 1];
tmp = new int[overflow.length - 1];
System.arraycopy(overflow, 0, tmp, 0, tmp.length);
overflow = tmp;
}
return array;
}
public static int[] mult(int inp, int[] mult, int base) {
int array[] = new int[mult.length];
System.arraycopy(mult, 0, array, 0, mult.length);
int overflow = 0;
for (int i = mult.length - 1; i >= 0; i--) {
int sum = inp * mult[i] + overflow;
array[i] = sum % base;
overflow = sum / base;
}
while (overflow > 0) {
int[] tmp = new int[array.length + 1];
System.arraycopy(array, 0, tmp, 1, array.length);
array = tmp;
array[0] = overflow % base;
overflow /= base;
}
return array;
}
public static int[] add(int[] a, int[] b, int base) {
int length = a.length > b.length ? a.length : b.length;
int[] array = new int[length];
System.arraycopy(a.length == length ? a : b, 0, array, 0, length);
int shortArr[] = a.length == length ? b : a;
int overflow = 0;
for (int i = array.length - 1; i >= 0; i--) {
int index = i + shortArr.length - length;
int val = index >= 0 ? shortArr[index] : 0;
int sum = array[i] + val + overflow;
array[i] = sum % base;
overflow = sum / base;
}
while (overflow > 0) {
int[] tmp = new int[array.length + 1];
System.arraycopy(array, 0, tmp, 1, array.length);
array = tmp;
array[0] = overflow % base;
overflow /= base;
}
return array;
}
}