Умножение двух длинных длинных int C

Question

Я работаю над программой в C как часть Homework, в которой я должен получить произведение двух длинных чисел, которые берутся как символьная строка. например: 123456789021 и 132456789098. Поскольку он берется как строка, я преобразовал их в long long int для умножения. Но полученный продукт будет очень большим (я думаю, больше, чем длинный длинный int). Может ли кто-нибудь предложить мне метод выполнения этого умножения?

Answer 1

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

• как разбить целое (представленное в виде строки) в цифры
• как преобразовать каждую цифру обратно в целое число 0 <= d < 10
• как управлять массивами цифр (то есть., насколько велики вы должны сделать массивы?)
• как написать цикл (ы), возможно, потребуется реализовать умножение
• как управлять выполнение изделий из одной цифры к следующему
• как преобразовать эти цифры обратно в символы для вывода

Answer 2

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

Answer 3

обычно большие целые числа, представленные в виде массивов байтов. Вы можете взглянуть на реализацию Microsoft BigInteger в DLR. Я думаю, что они использовали алгоритмы, разработанные Кнутом

Answer 4

Другим подходом было бы умножение чисел как float/double и отключение десятичного числа при отображении результатов.

Answer 5

Проверьте это BigInteger library и very basic sample code от World of Seven.

Если вы заинтересованы в некоторых из моих домашних вареных кодов в C (только умножение):

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

Code removed after I checked the home-work tag ;) 

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

Это работает в некоторых из предыдущих олимпиад по программированию я участвовал;) Но если вы ищете даже более быстрый алгоритм умножения вы можете реализовать Karatsuba algorithm, я лично использую это сейчас в режиме реального времени.

Answer 6

Эй человек, проверить это, я только что закончил его вчерашний день, как часть моей домашней работы:

#include<stdio.h> 
#include<string.h> 

int main() 
{ 
    char one[195]; 
    char two[195]; 
    char temp[195]; 
    int a[195],c[195],b[195]; 
    int x,i,j,k,l,p,add; 

    for(;;)/*determining the larger number...*/ 
    { 
     printf("Input A:"); 
      gets(one); 
     printf("Input B:"); 
      gets(two); 

     k=strlen(one); 
     l=strlen(two); 
     if(l>k) 
     { 
      strcpy(temp,one); 
      strcpy(one,two); 
      strcpy(two,temp); 
      break; 
     } 
     else 
     { 
      break; 
     } 
    } 
     k=strlen(one); 
     l=strlen(two); 
    for(p=0;p<195;p++)/*assigning all initial values to 0*/ 
    { 
     a[p]=0; 
     b[p]=0; 
     c[p]=0; 
    } 

    for(i=0;one[i];i++)/*converting char to integer(note:1,as a character assigned as 49.)*/ 
    { 
     a[i]=((one[--k])-48); 
    } 

    for(i=0;i<two[i];i++) 
    { 
     b[i]=((two[--l])-48); 
    } 


    for(i=0;i<=strlen(two);i++)/*main algorithm*/ 
    { 
     add=0; 
     p=0; 
     for(j=i;j<=(2*strlen(one)-1);j++) 
     { 
      x=c[j]+b[i]*a[p]+add; 
      c[j]=x%10; 
      add=x/10; 
      p++; 
     } 
    } 

    printf("\nMultiplication:"); 
    for(p=(2*strlen(one)-1);p>=0;p--) 
    { 
     if(p>strlen(one)&&c[p]==0) 
     { 
      continue; 
     } 
     printf("%d",c[p]); 
    } 
    printf("\n"); 
}