Я работаю над программой на C как часть домашней работы, в которой мне нужно получить произведение двух длинных чисел, которые принимаются как символьная строка. например: 123456789021 и 132456789098. Поскольку это строка, я преобразовал их в long long int для умножения. Но результирующий продукт будет очень большим (я думаю, больше, чем long long int). Может ли кто-нибудь предложить мне метод для выполнения этого умножения?
Умножение двух длинных длинных целых чисел C
Ответы (6)
Вот один из подходов: подумайте, как бы вы перемножили эти числа вручную на бумаге. Реализуйте этот метод на C. Вам нужно будет обнаружить:
- как разбить целое число (представленное в виде строки) на цифры
- как преобразовать каждую цифру обратно в целое число
0 <= d < 10
- как управлять массивами цифр (т.е. насколько большими должны быть массивы?)
- как написать цикл(ы), которые вам могут понадобиться для реализации умножения
- как управлять переносом продуктов с одной цифры на другую
- как преобразовать эти цифры обратно в символы для вывода
обычно большие целые числа, представленные в виде массивов байтов. Вы можете посмотреть на реализацию Microsoft BigInteger в DLR. Я думаю, что они использовали алгоритмы, разработанные Кнутом.
Проверьте эту библиотеку BigInteger и очень простой пример кода из World of Seven.
Если вас интересуют некоторые из моих домашних кодов на C (только умножение):
////////////////////////////////////////////////////////////////////////////////
Code removed after I checked the home-work tag ;)
///////////////////////////////////////////////////////////////////////////////////////
Это работает в некоторых из более ранних соревнований по программированию, в которых я участвовал;) Но если вы ищете еще более быстрый алгоритм умножения, вы можете реализовать алгоритм Карацубы, я лично использую его сейчас в соревнованиях в реальном времени.
Эй, чувак, зацени это, я только что закончил это вчера как часть моей домашней работы:
#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");
}
Вы можете использовать библиотеку для арифметики больших целых чисел, в Википедии есть список здесь.
Другим подходом было бы умножение чисел как float/double и удаление десятичной дроби при отображении результатов.