Сначала кусочки кода.
Функция сложения двух BigInt
| Код |
public static BigInt add(BigInt A, BigInt B) {
int n; // number of digits in the longest BigInt
int tmpN1 = A.length();
int tmpN2 = B.length();
if (tmpN1 > tmpN2) {
n = tmpN1;
} else {
n = tmpN2;
}
String number = "";
Unsigned carry = new Unsigned(0);
for (int i=0; i < n + 1; i++) {
DigitCarry digitsSum = Arithmetic.addDigits(A.getDigit(i),B.getDigit(i),carry);
number = " " + digitsSum.digit().intValue() + number;
carry = digitsSum.carry();
if (i == n) {
number = digitsSum.carry().intValue() + number;
}
}
return new BigInt(number);
}
|
Функция вычитания:
| Код |
public static BigInt sub(BigInt A, BigInt B) {
int n = A.length(); // because in this application we assume that we subtract smaller number from larger
String number = "";
Unsigned carry = new Unsigned(0);
for (int i=0; i < n; i++) {
if (A.getDigit(i).intValue() < B.getDigit(i).intValue()) {
DigitCarry digitsDiff = Arithmetic.subDigits(new Unsigned(A.getDigit(i).intValue() + A.base()), B.getDigit(i), carry); // here I assume, that A is always bigger than B (as mentioned on page 6)
carry = new Unsigned(1);
number = " " + digitsDiff.digit().intValue() + number;
}
if (A.getDigit(i).intValue() > B.getDigit(i).intValue()) {
DigitCarry digitsDiff = Arithmetic.subDigits(A.getDigit(i), B.getDigit(i), carry);
carry = new Unsigned(0);
number = " " + digitsDiff.digit().intValue() + number;
}
}
return new BigInt(number);
}
|
http://en.wikipedia.org/wiki/Karatsuba_algorithm:
| Код |
public static BigInt koMul(BigInt A, BigInt B) {
int n; // number of digits in the longest BigInt
int nLower;
int nUpper;
int tmpN1 = A.length();
int tmpN2 = B.length();
if (tmpN1 > tmpN2) {
n = tmpN1;
} else {
n = tmpN2;
}
if (n == 1) {
return Arithmetic.schoolMul(A, B);
}
nLower = n / 2;
nUpper = (n / 2) + (n % 2);
// A = a0 + (A.base()) ^ n * a1 and B = b0 + (B.base()) ^ n * b1
BigInt a0 = A.split(0,nLower-1);
BigInt a1 = A.split(nUpper, n-1);
BigInt b0 = B.split(0, nLower-1);
BigInt b1 = B.split(nUpper, n-1);
// sub-expressions as denoted on page 4 of the assignment
BigInt l = koMul(a0,b0);
BigInt h = koMul(a1,b1);
BigInt mPart = koMul(add(a0,a1), add(b0,b1));
BigInt m = sub(sub(mPart,l),h); // change add for sub
m.rshift(nLower);
h.rshift(2*nLower);
return add(add(l, m), h);
}
|
Проблема в следующем, что вроде все работает, но например если
A = 46907104279396844685534662588027 (base = 10^4)
B = 27814373078049346316783187585969
Result = 1304691698438108879726626703151282372117941977066919804092593163
Все ок, а если
A = 23868885311265469252694810491357
B = 17831413929796672871197506987660
То выдает следующее
| Код |
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1 > 0
at imult.StudentCode.koMul(StudentCode.java:84) [return Arithmetic.schoolMul(A, B);]
at imult.StudentCode.koMul(StudentCode.java:100) [BigInt h = koMul(a1,b1);]
at imult.StudentCode.koMul(StudentCode.java:101) [BigInt mPart = koMul(add(a0,a1), add(b0,b1));]
at imult.StudentCode.koMul(StudentCode.java:99) [BigInt l = koMul(a0,b0);]
at imult.StudentCode.koMul(StudentCode.java:100) [BigInt h = koMul(a1,b1);]
at imult.StudentCode.main(StudentCode.java:138) [koMul(a, b).print();]
|
Не могу никак понять, где тупняк : (((
Помогите!
|