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

Question

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

Answer 1

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

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

Answer 2

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

#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");
}

Answer 3

Проверьте это Библиотека BigInteger и очень простой пример кода из мира семи.

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

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

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

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

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

Answer 4

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

Answer 5

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

Answer 6

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