VPF::Karatsuba Algorithm - Форум программистов

Dzo

Дата 5.3.2009, 17:46 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 88
Регистрация: 22.4.2008

Репутация: 1
Всего: 1

Сначала кусочки кода.

Функция сложения двух 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);
    }

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();]

Не могу никак понять, где тупняк : (((

Помогите!

Dzo

Дата 5.3.2009, 18:38 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 88
Регистрация: 22.4.2008

Репутация: 1
Всего: 1

Так, я нашел источник ошибки...

Если происходит так, что A.length() < B.length() то дальше по рекурсии число делится на составляющие части и получается ошибка при получение доступа к индексу, которого в числе то нет : )

Пофиксил так:

Код


          if (tmpN1 > tmpN2) {
              n = tmpN1; 
          } else {
              BigInt temporary = B;
              BigInt temporary2 = A;
              A = temporary;
              B = temporary2;
              n = A.length();
          }

Возник совсем простой вопрос - мой метод смены значений переменных друг с другом совсем быдлокодерский?

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »