Реализация BigInt.add()?

Question

Я пытаюсь реализовать свою собственную версию метода add() из класса BigInteger. До сих пор он отлично работает при задании двух чисел одинаковой длины, но он не может скомпилировать (индексировать за пределы) при задании двух чисел разной длины. Какой был бы лучший способ решить эту проблему?

Если это поможет, то выход, когда два значения, вставленные в 10 и 1 составляет 20.

public BigInt add(BigInt b) { 
     int[] ans = new int[value.length]; 
     int carry=0; 

     if(this.lessThan(b)) 
       for(int i=b.value.length-1;i>=0;i--){ 
         int result=this.value[i]+b.value[i]+carry; 
         carry=result/10; 
         result%=10; 
         ans[i]=result; 
       } 
     else 
       for(int i=this.value.length-1;i>=0;i--){ 
         int result=this.value[i]+b.value[i]+carry; 
         carry=result/10; 
         result%=10; 
         ans[i]=result; 
       } 

     String ANSsz=convertArrayToString(ans); 
     BigInt Sum = new BigInt(ANSsz); 
     return Sum; 
    } 

Answer 1

Если я понимаю ваш код правильно, ans длина должна быть один больше, чем больше из двух BigInt длина. Ваш ans только велик, как объект, на который вызывается метод.

Answer 2

Я хотел бы попробовать что-то вроде этого:

public BigInt add2(BigInt b) 
    { 
     int answerLength = Math.max(b.value.length, this.value.length) + 1; 
     int[] answer = new int[ answerLength ]; 

     BigInt bigger = this; 
     BigInt smaller = b; 
     if(this.lessThan(b)) 
     { 
      bigger = b; 
      smaller = this; 
     } 

     // copy the bigger value into answer 
     for(int i = bigger.value.length - 1; i >= 0; i--) 
     { 
      answer[ i + 1 ] = bigger.value[ i ]; 
     } 

     // add the smaller into the answer 
     int carry = 0; 
     int lengthOffset = answerLength - smaller.value.length; 
     for(int i = smaller.value.length - 1; i >= 0; i--) 
     { 
      int result = answer[ i + lengthOffset ] + smaller.value[ i ] + carry; 
      carry = result/10; 
      result %= 10; 
      answer[ i ] = result; 
     } 
     answer[ 0 ] = carry; 

     String ANSsz = convertArrayToString(answer); 
     BigInt Sum = new BigInt(ANSsz); 
     return Sum; 
     } 

Answer 3

Это чрезвычайно странное решение на самом деле. Прежде всего, это имеет очевидную проблему переполнения (результат двух добавленных ints может не вписываться в int int), и я понятия не имею, почему именно мы хотели бы разделить на 10 для простого добавления 2 чисел - это действительно необходимо только для преобразования числа в десятичную строку.

В любом случае просто подумайте о том, сколько цифр может иметь продукт двух чисел. Для простоты мы попробуем это в base10, но обобщение очевидно:

A k разрядное длинное число не более 10^k - 1 большое. Следовательно, если мы имеем число с n цифрами и одно с m, результат не более: 10^n - 1 + 10^m - 1 = 10^n + 10^m - 2. Наибольшее значение мы можем получить, если n == m, что эквивалентно 10^n * 2 - 2, что, очевидно, меньше 10^(n + 1). Это означает, что число имеет не более одной цифры больше, чем у большего из двух (что также справедливо для базы 2).