Умножение путем повторного добавления

Question

Я пытаюсь умножить два массива цифр за счет повторного добавления. Таким образом, число 324 = [4,2,3] раз 24 = [4,2]. То, что я застрял, повторяет добавление 324 и 324, сохраняя это в массиве как [8,4,6], затем повторяя процесс добавления, чтобы получить [8,4,6] + [4,2,3] и т. Д. и т. д. Это то, что у меня есть до сих пор:

BigInt result = new BigInt(); 
BigInt temp = new BigInt(); 
int sum = 0; 
int carry = 0; 
int size = digitList.size(); 
int k = 0; //k is our multiplier 
for (int i = otherBigInt.digitList.size()-1; i >=0; i--) { 
    k = 10 * k + otherBigInt.digitList.get(i); 
} 

Здесь я выполняю длинное добавление, по цифре.

for (int i =0; i<size;i++) { 
    sum = digitList.get(i) + digitList.get(i) + carry; 
    if (sum > 9) { 
     temp.digitList.add(sum%10); 
     carry=1; 
    } else { 
     temp.digitList.add(sum); 
     carry=0; 
    } 
    if (sum > 9 && i == size-1) { 
     temp.digitList.add(sum/10); 
    } 
} 

Здесь я застреваю. То, что я пытаюсь сделать здесь, состоит в том, чтобы добавить 324 во временный массив, где он отвечает, а затем назначается массиву результатов. Отсюда я назначаю результат массиву temp, чтобы добавить к сохраненному результату. например: digitlist = 324, temp = 324. Результат = 648 -> digitList = 324, temp = 648. result = 972.

Я очищаю массив результатов, поэтому я могу сохранить более свежий результат на каждой итерации. В этот момент я получаю nullpointerExeption, где index = 0 и size = 0.

for(int i=0;i<25;i++) { 
    result.digitList.clear(); 
    for (int j=0; j<digitList.size();j++) { 
     sum = digitList.get(j) + temp.digitList.get(j) + carry; 
     if (sum > 9) { 
      result.digitList.add(sum%10); 
      carry=1; 
     } else { 
      result.digitList.add(sum); 
      carry=0; 
     } 
     if (sum > 9 && j == size-1) { 
      result.digitList.add(sum/10); 
     } 
    } 
    temp.digitList = result.digitList; 
    } 
    return result; 
} 

Это вопрос, связанный с домашним заданием, однако я некоторое время застрял на нем. Решение, к которому я прихожу, кажется слишком сложным для такой простой задачи, может ли кто-то направить меня в правильном направлении?

Answer 1

Это может быть проще, если вы используете другие имена переменных, чтобы помочь вам вместе:

BigInt input1 = new BigInt(); 
BigInt multiplier = new BigInt(); 

BigInt nextResult = new BigInt(); 
BigInt lastResult = null; 

while (... notdone ...) { 
    nextResult.digitList.clear(); 
    if (lastResult==null) { 
     lastResult = input1; 
    } else { 
     ... the addition logic: nextResult = lastResult + input1 ... 
    } 
    ... the logic to remember that one addition step was done ... 

    lastResult = nextResult; 
    nextResult = new BigInt(); 
} 

lastResult всегда ваш результат от предыдущей итерации. Вы должны быть осторожны, чтобы вы никогда не меняли цифры в lastResult. Единственное изменение в lastResult должно быть, если вы назначили его с input1 или nextResult.

Когда вы начинаете с добавления, ваш lastResult не имеет данных, потому что не было «последней итерации». В этом случае вы можете просто инициализировать lastResult с input1.

nextResult Здесь вы работаете в дополнение к итерации и сохраняете новые цифры. Когда эта итерация будет выполнена, сделайте это lastResult и подготовьте новый nextResult, на котором будет работать. (В вашем коде вы иногда используете temp, а иногда result, что добавляет вам путаницу.)

Интересная часть, помня, как далеко вы уже рассчитали. Например, с «5 x 3» после первой итерации вы получаете результат, а «3» становится «2», так как осталось две итерации. Или с «123 x 15» «15» уменьшается с каждой итерацией сначала до «14», затем «13», ... «10», «9», ... a.s.o.

Это относится к части состояния «... не сделано ...».

Здесь возможно несколько оптимизаций, о которых я бы не хотел много говорить, потому что это, безусловно, часть вашей домашней работы. Вероятно, вам стоит просто продолжить разработку кода, пока он не сработает. По пути вы, возможно, уже имеете идеи, как сделать вещи проще. Это также может помочь, если вы попытаетесь выполнить дополнительные шаги на бумаге. Вы можете заметить, какие части можно сделать более легко. (Если вы не найдете оптимизаций, не беспокойтесь - это требует практики, а иногда мозг находится в таком настроении, а иногда нет. Также ваши результаты должны быть правильными, они не должны быть «искусно оптимизированы», а затем иногда ошибаться.)

UPDATE: на переменные и экземпляры объектов

Вы должны сделать разницу между переменными и объектами, к которым они относятся.

nextResult = new BigInt(); 

Это утверждение означает две вещи: 1) Вы создаете экземпляр BigInt() и 2) Вы ссылаетесь, что BigInt с lastResult.

Теперь это утверждение:

lastResult = nextResult; 

Eсть все тот же BigInt, но теперь оба lastResult и nextResult относятся к той же самой BigInt. Если вы измените цифру в lastResult, вы фактически измените цифру в примере BigInt. А так как nextResult и lastResult относятся к тем же BigInt, оба будут выдавать одинаковые значения при наборе цифр.

Это также означает, что вам не нужно копировать цифры. Они уже есть.

Теперь это утверждение создает новый экземпляр BigInt:

nextResult = new BigInt(); 

Теперь после этих трех утверждений, nextResult относится к новому BigInt экземпляра, который теперь отличается от BigInt, который находится в lastResult.