Вопрос для интервью - внедрить Biginteger Multiply

Question

Реализация Biginteger Multiply

1. использовать массив целых чисел для хранения большого целого например, 297897654 будет храниться как {2,9,7,8,9,7,6,5,4}
2. реализовать функцию умножения для больших целых
   Примеры: {2, 9, 8, 8, 9, 8} * {3,6,3,4,5,8,9,1,2} = {1,0,8,6,3,7,1 , 4,1,8,7,8,9,7,6}

Мне не удалось реализовать этот класс, и я думал об этом в течение нескольких недель, но не смог получить ответ.

Кто-нибудь может помочь мне реализовать это с помощью C # / Java? Большое спасибо.

Answer 1

Знаете ли вы, как сделать умножение на бумаге?

  123
x 456
-----
  738
 615
492
-----
56088

Я бы просто реализовал этот алгоритм в коде.

Answer 2

C ++ Реализация:

Исходный код:

#include <iostream>

using namespace std;

int main()
{
    int a[10] = {8,9,8,8,9,2};
    int b[10] = {2,1,9,8,5,4,3,6,3};

    // INPUT DISPLAY
    for(int i=9;i>=0;i--) cout << a[i];
    cout << " x ";
    for(int i=9;i>=0;i--) cout << b[i];
    cout << " = ";

    int c[20] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};

    for(int i=0;i<10;i++)
    {
            int carry = 0;
            for(int j=0;j<10;j++)
            {
                    int t = (a[j] * b[i]) + c[i+j] + carry;
                    carry = t/10;
                    c[i+j] = t%10;
            }
    }

    // RESULT DISPLAY
    for(int i=19;i>=0;i--) cout << c[i];
    cout << endl;
}

Выход:

0000298898 x 0363458912 = 00000108637141878976

Answer 3

Существует превосходный алгоритм, называемый алгоритмом Карацубы. Здесь
Который использует стратегию «разделяй и властвуй» .. Где вы можете умножать большие числа ..
Я реализовал это в Java .. Используя некоторые манипуляции ..

 package aoa;
    import java.io.*;
    public class LargeMult {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException
    {
        // TODO code application logic here
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        System.out.println("Enter 1st number");
        String a=br.readLine();
        System.out.println("Enter 2nd number");
        String b=br.readLine();
        System.out.println("Result:"+multiply(a,b));

    }
    static String multiply(String t1,String t2)
    {

        if(t1.length()>1&&t2.length()>1)
        {
            int mid1=t1.length()/2;
            int mid2=t2.length()/2;
            String a=t1.substring(0, mid1);//Al
            String b=t1.substring(mid1, t1.length());//Ar
            String c=t2.substring(0, mid2);//Bl
            String d=t2.substring(mid2, t2.length());//Br
            String s1=multiply(a, c);
            String s2=multiply(a, d);
            String s3=multiply(b, c);
            String s4=multiply(b, d);


            long ans;
            ans=Long.parseLong(s1)*(long)Math.pow(10, 
            b.length()+d.length())+Long.parseLong(s3)*(long)Math.pow(10,d.length())+
            Long.parseLong(s2)*(long)Math.pow(10, b.length())+Long.parseLong(s4);
            return ans+"";
        }
        else

        {
            return (Integer.parseInt(t1)*Integer.parseInt(t2))+"";
        }   
    }
}    

Надеюсь, это поможет !! Наслаждайтесь ..

Answer 4

Дайте число, которое вы хотите умножить в массиве целочисленных типов, например int [] one & int [] two.

public class VeryLongMultiplication {
public static void main(String args[]){
    int[] one={9,9,9,9,9,9};
    String[] temp=new String[100];
    int c=0;
    String[] temp1=new String[100];
    int c1=0;
    int[] two={9,9,9,9,9,9};
    int car=0,mul=1; int rem=0; int sum=0;
    String str="";

    ////////////////////////////////////////////
    for(int i=one.length-1;i>=0;i--)
    {
        for(int j=two.length-1;j>=0;j--)
        {
            mul=one[i]*two[j]+car;
            rem=mul%10;
            car=mul/10;
            if(j>0)
                str=rem+str;
            else
                str=mul+str;
        }
        temp[c]=str;
        c++;
        str="";
        car=0;
    }

    ////////////////////////////////////////
    for(int jk=0;jk<c;jk++)
    {
        for(int l=c-jk;l>0;l--)
            str="0"+str;
        str=str+temp[jk];
        for(int l=0;l<=jk-1;l++)
            str=str+"0";
        System.out.println(str);
        temp1[c1]=str;
        c1++;
        str="";
    }

    ///////////////////////////////////

        String ag="";int carry=0;
        System.out.println("========================================================");
        for(int jw=temp1[0].length()-1;jw>=0;jw--)
        {

            for(int iw=0;iw<c1;iw++)
            { 
                int x=temp1[iw].charAt(jw)-'0';
                sum+=x;

            }
            sum+=carry;
            int n=sum;

            sum=n%10;carry=n/10;
                ag=sum+ag;
                sum=0;
            }
    System.out.println(ag);
}
}

Выход:

0000008999991 
0000089999910 
0000899999100 
0008999991000 
0089999910000 
0899999100000
______________
0999998000001

Answer 5

Python один вкладыш просто для удовольствия:

def mul(one,two):
    return map(int,str(int("".join(map(str,one))) * int("".join(map(str,two)))))

Попробуйте:

>>> mul([2,7,6],[1,0,5])
[2, 8, 9, 8, 0]

Answer 6

Я публикую код Java, который я написал.Надеюсь, это поможет

import org.junit.Test;
import static org.junit.Assert.*;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
* Created by ${YogenRai} on 11/27/2015.
*
* method multiply BigInteger stored as digits in integer array and returns results
*/
public class BigIntegerMultiply {
   public static List<Integer> multiply(int[] num1,int[] num2){
    BigInteger first=new BigInteger(toString(num1));
    BigInteger result=new BigInteger("0");
    for (int i = num2.length-1,k=1; i >=0; i--,k=k*10) {
        result =  (first.multiply(BigInteger.valueOf(num2[i]))).multiply(BigInteger.valueOf(k)).add(result);
    }
    return convertToArray(result);
}

private static List<Integer> convertToArray(BigInteger result) {
    List<Integer> rs=new ArrayList<>();
    while (result.intValue()!=0){
        int digit=result.mod(BigInteger.TEN).intValue();
        rs.add(digit);
        result = result.divide(BigInteger.TEN);
    }
    Collections.reverse(rs);
    return rs;
}

public static String toString(int[] array){
    StringBuilder sb=new StringBuilder();
    for (int element:array){
        sb.append(element);
    }
    return sb.toString();
}

@Test
public void testArray(){
    int[] num1={2, 9, 8, 8, 9, 8};
    int[] num2 = {3,6,3,4,5,8,9,1,2};
    System.out.println(multiply(num1, num2));
}

}

Answer 7

Подсказка: используйте функцию «разделяй и властвуй», чтобы разбить int на половинки, это может эффективно уменьшить временную сложность с O (n ^ 2) до O (n ^ (log3)).Суть заключается в сокращении операций умножения.

Answer 8

Если вы сделаете это длинным способом, вам также придется реализовать метод Add (), чтобы сложить все части в конце. Я начал там только для того, чтобы сдвинуться с мертвой точки. Когда у вас отключен метод Add (), метод Multipy () будет реализован в том же духе.

public static int[] Add(int[] a, int[] b) {
   var maxLen = (a.Length > b.Length ? a.Length : b.Length);
   var carryOver = 0;
   var result = new List<int>();
   for (int i = 0; i < maxLen; i++) {
      var idx1 = a.Length - i - 1;
      var idx2 = b.Length - i - 1;
      var val1 = (idx1 < 0 ? 0 : a[idx1]);
      var val2 = (idx2 < 0 ? 0 : b[idx2]);

      var addResult = (val1 + val2) + carryOver;
      var strAddResult = String.Format("{0:00}", addResult);
      carryOver = Convert.ToInt32(strAddResult.Substring(0, 1));
      var partialAddResult = Convert.ToInt32(strAddResult.Substring(1));
      result.Insert(0, partialAddResult);
   }
   if (carryOver > 0) result.Insert(0, carryOver);
   return result.ToArray();
}