Calcul de produits de grands nombres en utilisant des tableaux?

Question

J'ai un projet (pour l'école) et je ne peux absolument pas utiliser les bibliothèques externes, donc je ne peux pas utiliser une grande bibliothèque de nombres et j'ai besoin d'obtenir le produit de 2 (très) grands nombres. J'ai donc pensé que j'écrirais mon propre code, mais je n'arrive pas à obtenir des multiplications à un chiffre.

Comment je l'ai fait jusqu'à présent, c'est que j'ai un tableau de caractères 'a'. Et Ill multiplie chacun de ses chiffres avec l'autre nombre (puisque aucune multiplication ne peut aller au-delà de 81 soit 9 * 9). Mais je n'arrive pas à comprendre comment Ill multiplier deux tableaux les uns avec les autres.

Comme dans

int a[] = {1,2,3}; 
int b[] = {4,5,6}; 

int r[200]; // To store result of 123x456. After processing should have value 56088 

Heres mon code jusqu'à présent ...

#include <iostream> 
using namespace std; 

void reverseArray(int array[], int n) 
{ 
    int t; 
    for(int i=0;i<n/2;i++) 
    { 
     t = array[i]; 
     array[i] = array[n-i-1]; 
     array[n-i-1] = t; 
    } 
} 

int main() 
{ 
    int A[] = {1,2,6,6,7,7,8,8,8,8,8,8,8,8,8,8}; 
    int s = sizeof(A)/sizeof(int); 
    int n = s-1; 

    int R[50]; 


    int x = 2; 

    int rem = 0; 

    for(int i=0; i<s; i++) 
    { 
     R[i] = (A[n-i] * x) % 10; 
     R[i] += (rem != 0) ? rem:0; 
     rem = (A[n-i] * x)/10; 
    } 

    reverseArray(R, s); 

    for(int i=0; i<s; i++) cout<<R[i]; // Gives 2533557777777776 

} 

J'ai aussi trouvé un programme similaire here qui calcule factorielles de très grands nombres. Mais je ne peux pas sembler comprendre le code assez pour le changer à mes besoins. Désolé, la question est un peu incomplète.

Merci.

Answer 1

Il suffit de faire la même chose que vous faites maintenant, mais pour chaque chiffre dans le second tableau - en d'autres termes, au lieu de x utilisation B[j], où j est une boucle sur tous les chiffres du tableau B.

Answer 2

Je ne suis pas sûr de ce que l'algorithme que vous avez appris à l'école primaire pour multiplier deux nombres arbitraires, mais visuellement il va quelque chose comme ceci:

43241 
    621 
    ----- * 
    43241 <-- 1 * 43241 
    864820 <-- 20 * 43241, basically do 2 * 43241 and append a zero 
25944600 <-- 600 * 43241, basically do 6 * 43241 and append two zeroes 
-------- + 
26852661 <-- Add up results, remember to carry 

Ainsi, dans cet exemple particulier, les tableaux seraient A[] = {1,4,2,3,4} et B[] = {1,2,6} . Vous pouvez alors juste faire une boucle, comme

int tempArray[50]; // something big enough 
for (int n = 0; n < max; n++) 
{ 
    multiplyArrayWithNumber(A, B[i], tempArray, i); 
    addArraysAndStore(resultArray, tempArray, resultArray); 
} 

où les fonctions multiplyArrayWithNumber et addArraysAndStore pourraient avoir la signature

void multiplyArrayWithNumber(const int* array, const int number, int* resultArray, const int zeroesAppended); 

void addArraysAndStore(const int* lefthandside, const int* righthandside, int* result); 

Answer 3

Je l'ai fait en java, Ici, je prends des numéros N1 et N2, Et j'ai créé un tableau de taille 1000. Prenons un exemple Comment résoudre ce problème, N1 = 12, N2 = 1234. Pour N1 = 12, temp = N1% 10 = 2, maintenant Multipliez ce chiffre par le chiffre N2 de droite à gauche et stockez le résultat dans le tableau en commençant par i = 0, de même pour le chiffre de repos de N1. Le tableau stockera le résultat mais dans l'ordre inverse. Jetez un coup d'oeil sur ce lien. http://ideone.com/UbG9dW#view_edit_box

//Product of two very large number 
import java.io.*; 
import java.util.*; 
import java.text.*; 
import java.math.*; 
import java.util.regex.*; 

class Solution { 
    public static void main(String[] args) { 
     Scanner scan=new Scanner(System.in); 
     int N1=scan.nextInt(); 
     int N2=scan.nextInt(); 
     //int N=scan.nextInt(); 
     int [] array=new int[1000]; 
     Arrays.fill(array,0); 
     int size=multiply(N1,N2,array); 
     for(int i=size-1;i>=0;i--){ 
      System.out.print(array[i]); 
     } 
    } 
    public static int multiply(int N1, int N2, int [] result){ 
     int a=N1; 
     int b=N2;    
     int count=0, carry=0; 
     int i=0; 
     int max=0; 
     if(a==0||b==0) 
      return 1; 
     while(a>0){ 
      int temp1=a%10; 
      a=a/10; 
      i=0; 
      while(b>0){ 
       int temp2=b%10; 
       b=b/10; 
       int product=result[count+i]+temp1*temp2+carry; 
       result[count+i]=product%10; 
       carry=product/10; 
       i++; 
       //System.out.println("ii="+i); 
      } 
      while(carry>0){ 
       result[count+i]=carry%10; 
       carry=carry/10; 
       i++; 
       //System.out.println("iiii="+i); 
      } 
      count++; 
      b=N2; 
     } 
     //System.out.println("i="+i); 

     return i+count-1; 
    } 
}