Домашнее задание: как написать собственное умножение больших чисел?

Question

В моем проекте я имею дело с умножением больших чисел (больше, чем java.long) в моем собственном классе BigNumber на int[]. В основном мне нужно реализовать что-то вроде этого:

    157 x
    121 y
   ----
    157 result1
   314  + result2
  157   + result3
 ------
 18997  finalResult

Но как мне это реализовать?

Я думал о расширении результата 2,3 с нулями (3140, 15700) и их добавлении. Но сначала мне нужно как-то перемещаться между каждой цифрой y и умножать ее на каждую цифру x.

Answer 1

Используйте диагональный подход. Создайте массив, умножьте каждую цифру на другую и заполните числа в каждой ячейке.

36 x 92

       3     6
    +-----+-----+
    | 2 / | 5 / |
9   |  /  |  /  |
    | / 7 | / 4 |
    +-----+-----+
    | 0 / | 1 / |
2   |  /  |  /  |
    | / 6 | / 2 |
    +-----+-----+

Добавьте числа на каждой диагонали. Переход от наименее значимой цифры (внизу справа) к самой (вверху слева).

2                                                                    2 (least-significant)
(6 + 1 + 4) = 11 (make this 1, and carry the 1 to the next digit)    1
(5 + 7 + 0 + 1(carried)) = 13 (make this 3, and carry the 1)         3
2 + 1(carried) = 3                                                   3 (most-significant)

Ответ 3312.

Создайте двумерный массив из ваших цифр. Заполните массив с умножением единственных цифр вместе.

Напишите некоторую логику, чтобы очистить диагонали, как я делал выше.

Это должно работать для произвольно больших чисел (если у вас еще есть память).

Answer 2

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

public String multiply(String num1, String num2){
        int product, carry=0, sum=0;
        String result = new String("");
        String partial = new String("");
        ArrayList<String> partialList = new ArrayList<String>();

        /* computing partial products using this loop. */
        for(int j=num2.length()-1 ; j>=0 ; j--) {
            for(int i=num1.length()-1 ; i>=0 ; i--) {       

                product = Integer.parseInt((new Character(num1.charAt(i))).toString()) * 
                                Integer.parseInt((new Character(num2.charAt(j))).toString()) + carry;               
                carry = product/10;
                partial = Integer.toString(product%10) + partial;               
            }       

            if(carry != 0)
                partial = Integer.toString(carry) + partial;

            partialList.add(partial);
            partial = "";
            carry = 0;
        }                           

        /* appending zeroes incrementally */
        for(int i=0 ; i<partialList.size() ; i++)
            partialList.set(i, partialList.get(i) + (Long.toString( (long)java.lang.Math.pow(10.0,(double)i))).substring(1)   );        

        /* getting the size of the largest partial product(last) */
        int largestPartial = partialList.get(partialList.size()-1).length();

        /* prefixing zeroes */
        int zeroes;
        for(int i=0 ; i<partialList.size() ; i++) {
            zeroes =  largestPartial - partialList.get(i).length();

            if(zeroes >= 1)
            partialList.set(i, (Long.toString( (long)java.lang.Math.pow(10.0,(double)zeroes))).substring(1) + partialList.get(i)   );
        }

        /* to compute the result */
        carry = 0;
        for(int i=largestPartial-1 ; i>=0 ; i--) {

            sum = 0;
            for(int j=0 ; j<partialList.size() ; j++)
                sum = sum + Integer.parseInt(new Character(partialList.get(j).charAt(i)).toString());

            sum = sum + carry;
            carry = sum/10;         
            result = Integer.toString(sum%10) + result;     
        }

        if(carry != 0)
            result = Integer.toString(carry) + result;

        return result;
    }

Answer 3

Я бы избежал головной боли при написании собственного и просто использовал класс java.math.BigInteger . В нем должно быть все необходимое.

Answer 4

Разделение переноса и умножения цифр:

def carries(digitlist):
    digitlist.reverse()
    for idx,digit in enumerate(digitlist):
        if digit>9:
            newdigit = digit%10
            carry = (digit-newdigit)/10
            digitlist[idx] = newdigit
            if idx+1 > len(digitlist)-1:
                digitlist.append(carry)
            else:
                digitlist[idx+1] += carry
    digitlist.reverse()
    return True

def multiply(first,second):
    digits = [0 for place in range(len(first)+len(second))]
    for fid,fdig in enumerate(reversed(first)):
        for sid,sdig in enumerate(reversed(second)):
            offset = fid+sid
            mult = fdig*sdig
            digits[offset] += mult
    digits.reverse()
    carries(digits)
    return digits

def prettify(digitlist):
    return ''.join(list(`i` for i in digitlist))

Тогда мы можем назвать это:

a = [1,2,3,4,7,6,2]
b = [9,8,7,9]
mult = multiply(a,b)
print prettify(a)+"*"+prettify(b)
print "calc:",prettify(mult)
print "real:",int(prettify(a))*int(prettify(b))

Урожайность:

1234762*9879
calc: 12198213798
real: 12198213798

Конечно, 10 секунд в функции carries и неявное десятичное представление в prettify - единственное, что требует, чтобы это было основанием 10. Добавление аргумента может сделать эту базу n, так что вы можете переключиться на базу 1000 в чтобы уменьшить количество блоков и ускорить расчет.

Answer 5

Я думаю, это поможет вам

import java.util.ArrayList;
import java.util.List;

public class Multiply {


static int len;
public static void main(String[] args) {
      System.out.println(multiply("123456789012345678901","123456789012345678901");
}

private static ArrayList<Integer> addTheList(List<ArrayList<Integer>> myList) {
    ArrayList<Integer> result=new ArrayList<>();

    for(int i=0;i<len;i++)
    {
        result.add(0);

    }
    int index=0;
    for(int i=0;i<myList.size();i++)
    {
        ArrayList<Integer> a=new ArrayList<>(myList.get(index));
        ArrayList<Integer> b=new ArrayList<>(myList.get(index+1));
        for (int j = 0; j < a.size()||j < b.size(); i++) {
            result.add(a.get(i) + b.get(i));
    }

    }

    return result;
}

private static ArrayList<Integer> multiply(ArrayList<Integer> list1, Integer integer) {
    ArrayList<Integer> result=new ArrayList<>();
    int prvs=0;
    for(int i=0;i<list1.size();i++)
    {
        int sum=(list1.get(i)*integer)+prvs;
        System.out.println(sum);
        int r=sum/10;
        int m=sum%10;

        if(!(r>0))
        {

            result.add(sum);                
        }
        else
        {
            result.add(m);
            prvs=r;
        }
        if(!(i==(list1.size()-1)))
        {
            prvs=0;
        }

    }
    if(!(prvs==0))
    {
        result.add(prvs);
    }
    return result;
}

private static ArrayList<Integer> changeToNumber(String str1) {
    ArrayList<Integer> list1=new ArrayList<>();
    for(int i=0;i<str1.length();i++)
    {

        list1.add(Character.getNumericValue(str1.charAt(i)));
    }
    return list1;

}
public static String multiply(String num1, String num2) {
    String n1 = new StringBuilder(num1).reverse().toString();
    String n2 = new StringBuilder(num2).reverse().toString();

    int[] d = new int[num1.length()+num2.length()];

    //multiply each digit and sum at the corresponding positions
    for(int i=0; i<n1.length(); i++){
        for(int j=0; j<n2.length(); j++){
            d[i+j] += (n1.charAt(i)-'0') * (n2.charAt(j)-'0');
        }
    }

    StringBuilder sb = new StringBuilder();

    //calculate each digit
    for(int i=0; i<d.length; i++){
        int mod = d[i]%10;
        int carry = d[i]/10;
        if(i+1<d.length){
            d[i+1] += carry;
        }
        sb.insert(0, mod);
    }

    //remove front 0's
    while(sb.charAt(0) == '0' && sb.length()> 1){
        sb.deleteCharAt(0);
    }

    return sb.toString();
}
}

Answer 6

Вы можете проверить следующее решение, которое учит нас как умножению, так и сложению больших чисел. Пожалуйста, прокомментируйте, если это можно улучшить.

public static void main(String args[]) {

    String s1 = "123666666666666666666666666666666666666666666666669999999999999999999999999666666666666666666666666666666666666666666666666666666666666666666";
    String s2 = "45688888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888";
    System.out.println(multiply(s1, s2));
}

private static String multiply(String s1, String s2) {

    int[] firstArray = convert(s1);
    int[] secondArray = convert(s2);
    //System.out.println(Arrays.toString(firstArray));
    //System.out.println(Arrays.toString(secondArray));
    // pass the arrays and get the array which is holding the individual
    // rows while we multiply using pen and paper
    String[] result = doMultiply(firstArray, secondArray);
    //System.out.println(Arrays.toString(result));

    // Now we are almost done lets format them as we like

    result = format(result);
    //System.out.println(Arrays.toString(result));

    //Add elements now and we are done
    String sum="0";
    for(String s:result){
        sum=add(sum,s);
    }

    return sum;
}

private static String[] doMultiply(int[] firstArray, int[] secondArray) {

    String[] temp = new String[secondArray.length];

    for (int i = secondArray.length - 1; i >= 0; i--) {

        int result = 0;
        int carry = 0;
        int rem = 0;
        temp[secondArray.length - 1 - i] = "";
        for (int j = firstArray.length - 1; j >= 0; j--) {
            result = (secondArray[i] * firstArray[j]) + carry;
            carry = result / 10;
            rem = result % 10;
            temp[secondArray.length - 1 - i] = rem
                    + temp[secondArray.length - 1 - i];
        }
        // if the last carry remains in the last digit
        if (carry > 0)
            temp[secondArray.length - 1 - i] = carry
                    + temp[secondArray.length - 1 - i];
    }

    return temp;
}

public static int[] convert(String str) {

    int[] arr = new int[str.length()];
    for (int i = 0; i < str.length(); i++) {
        arr[i] = Character.digit(str.charAt(i), 10);
    }

    return arr;
}

private static String[] format(String[] result) {

    for (int i = 0; i < result.length; i++) {
        int j = 0;
        while (j < i) {
            result[i] += "0";
            j++;
        }
    }

    return result;
}

public static String add(String num1, String num2) {

    //System.out.println("First Number :" + num1);
    //System.out.println("Second Number :" + num2);

    int max = num1.length() > num2.length() ? num1.length() : num2.length();

    int[] numArr1 = new int[max];
    int[] numArr2 = new int[max];

    for (int i = 0; i < num1.length(); i++) {
        numArr1[i] = Integer.parseInt(""
                + num1.charAt(num1.length() - 1 - i));
    }
    for (int i = 0; i < num2.length(); i++) {
        numArr2[i] = Integer.parseInt(""
                + num2.charAt(num2.length() - 1 - i));
    }

    int carry = 0;
    int[] sumArr = new int[max + 1];

    for (int k = 0; k < max; k++) {
        int tempsum = numArr1[k] + numArr2[k] + carry;
        sumArr[k] = tempsum % 10;
        carry = 0;
        if (tempsum >= 10) {
            carry = 1;
        }
    }
    sumArr[max] = carry;

/*  System.out.println("Sum :"
            + new StringBuffer(Arrays.toString(sumArr)).reverse()
            .toString().replaceAll(",", "").replace("[", "")
            .replace("]", "").replace(" ", ""));*/
    return new StringBuffer(Arrays.toString(sumArr)).reverse().toString()
            .replaceAll(",", "").replace("[", "").replace("]", "")
            .replace(" ", "");
}

Answer 7

Я реализовал это в C ++. обратитесь к этому для логики ...

#include <iostream>
#include <deque>

using namespace std;

void print_num(deque<int> &num) {
  for(int i=0;i < num.size();i++) {
    cout<<num[i];
  }
  cout<<endl;
}

deque<int> sum(deque<int> &oppA, deque<int> &oppB) {
  if (oppA.size() == 0) return oppB;
  if (oppB.size() == 0) return oppA;

  deque<int> result;
  unsigned int carry = 0;

  deque<int>::reverse_iterator r_oppA = oppA.rbegin();
  deque<int>::reverse_iterator r_oppB = oppB.rbegin();
  while ((r_oppA != oppA.rend()) && (r_oppB != oppB.rend())) {

    int tmp = *r_oppA + *r_oppB + carry;
    result.push_front(tmp % 10);
    carry = tmp / 10;

    r_oppB++;
    r_oppA++;

  }
  while (r_oppA != oppA.rend()) {
    int tmp = *r_oppA + carry;
    result.push_front(tmp % 10);
    carry = tmp / 10;
    r_oppA++;
  }

  while (r_oppB != oppB.rend()) {
    int tmp = *r_oppB + carry;
    result.push_front(tmp % 10);
    carry = tmp / 10;
    r_oppB++;
  }

  return result;
}

deque<int> multiply(deque<int>& multiplicand, deque<int>& multiplier) {

  unsigned int carry = 0;
  deque<int> result;
  int deci_cnt = 0;

  deque<int>::reverse_iterator r_multiplier = multiplier.rbegin();
  deque<int> tmp_result;

  while (r_multiplier != multiplier.rend()) {

    for (int i=0; i<deci_cnt ;i++) {
      tmp_result.push_front(0);
    }

    deque<int>::reverse_iterator r_multiplicand = multiplicand.rbegin();
    while (r_multiplicand != multiplicand.rend()) {
      int tmp = (*r_multiplicand) * (*r_multiplier) + carry;
      tmp_result.push_front(tmp % 10);
      carry = tmp / 10;
      r_multiplicand++;
    }

    if (carry != 0) {
      tmp_result.push_front(carry);
      carry = 0;
    }

    result = sum(result, tmp_result);

    deci_cnt++;
    tmp_result.clear();
    r_multiplier++;
  }

  return result;
}

deque<int> int_to_deque(unsigned long num) {
  deque<int> result;

  if (num == 0) {
    result.push_front(0);
  }

  while (num > 0) {
    result.push_front(num % 10);
    num = num / 10;
  }

  return result;
}

int main() {

  deque<int> num1 = int_to_deque(18446744073709551615ULL);
  deque<int> num2 = int_to_deque(18446744073709551615ULL);

  deque<int> result = multiply(num1, num2);
  print_num(result);

  return 0;
}

Выход: 340282366920928463426481119284349108225

Answer 8

сделал это по-своему:

    int bigger = t1.length;
    int smaller = t2.length;
    int resultLength = bigger + smaller;
    int []resultTemp = new int[resultLength];
    int []result = new int[bigger + smaller];
    int []temporary = new int[resultLength+1];

    int z = resultLength-1;
    int zet = z;
    int step = 0;
    int carry = 0;
    int modulo = 0;

    for(int i=smaller-1; i>=0; i--){
        for(int k = bigger-1; k>= -1; k--){
            if(k == -1 && carry != 0 ){
                resultTemp[z] = carry;
                carry = 0;
                break;
            }
            else if(k == -1 && carry == 0){
                resultTemp[z] = 0;
                break;
            }
            resultTemp[z] = carry + t1[k]*t2[i];
            carry = 0;
            if( resultTemp[z] > 9 ){
               modulo = resultTemp[z] % 10;
               carry = resultTemp[z]/10;
               resultTemp[z] = modulo;
            }
            else{
                resultTemp[z] = resultTemp[z];
            }
            z--;
        }
        temporary = add(resultTemp, result);
        result = copyArray(temporary);
        resultTemp = clear(resultTemp);

        z = zet;
        step++;
        z = z - step;
    }

тогда я проверяю знак.

Answer 9

Так как это домашнее задание ... Вы уверены, что использование массива int - ваш лучший способ?
Я пытался внедрить нечто подобное год назад для повышения производительности в исследовательском проекте
, и мы закончили с сцепленные примитивы ..

Используя это, вы можете воспользоваться преимуществами того, что уже есть, и "only" придется беспокоиться о переполнениях на концах. Это может оказатьсябыть довольно простым, когда вы реализуете свое умножение с << (сдвигом влево) и сложениями .. </p>

Теперь, если вы хотите по-настоящему бросить вызов , попробуйте реализовать по модулю ...;)

Answer 10

Поскольку это домашнее задание, я дам несколько советов.

Вы можете подойти к нему так же, как и в своем примере, используя строки для хранения чисел любой длины и реализуя:

• добавить одно число к другому
• умножьте в качестве примера, добавив нули и вызвав метод сложения за шаг (поэтому для умножения на 20 добавьте "0" и добавьте это число дважды

Метод сложения, который вы можете создать путем извлечения char [] из строк, выделения результата char [], который на 1 длиннее самого длинного и добавления, как вы делали бы на бумаге с конца до начала обоих массивов .

Конечный результат не будет наилучшим решением, но легко показать, что он верен и будет обрабатывать числа любой длины (если они будут соответствовать строке Java).

Обновление

Хорошо, если вы решили добавить два числа, вы можете:

• реализовать умножение на 10
• реализовать умножение путем повторного сложения, как в вашем примере

или

• реализовать умножение на 2 (сдвиг влево)
• реализовать двоичное умножение по той же концепции, только на этот раз x 2 и добавить один раз

, чтобы проиллюстрировать последнее,

  13
   5 x
----
  13 x 1
  26 x 0
  52 x 1
---- +
  65

обратите внимание, что 1 0 1 - это биты в числе (5), на которое вы умножаетесь, и 26 = 13 x 2, 52 = 26 x 2. Вы поняли: -)