두 개의 long long int C 곱하기

Question

나는 숙제의 일부로 문자열로 사용되는 두 개의 긴 숫자의 곱을 얻어야 하는 C 프로그램을 작업하고 있습니다.예:123456789021 및 132456789098.문자열로 취하기 때문에 곱셈을 위해 long long int로 변환했습니다.그러나 결과 제품은 매우 클 것입니다(내 생각에 long long int보다 더 클 것입니다).누구든지 이 곱셈을 수행하는 방법을 제안해 주실 수 있나요?

Answer 1

다음은 다음과 같습니다.이 숫자를 종이에 어떻게 곱할 것인지 고려하십시오. 이 방법을 C에서 구현하십시오. 다음을 발견해야합니다.

• 정수 (문자열로 표시)를 숫자로 나누는 방법
• 각 숫자를 정수로 다시 변환하는 방법 0 <= d < 10
• 숫자 배열을 관리하는 방법 (즉, 배열을 얼마나 커야합니까?)
• 루프 작성 방법 곱셈을 구현해야 할 수도 있습니다.
• 한 자리에서 다음 자리로 운반 제품을 관리하는 방법
• 출력을 위해 해당 자릿수를 문자로 다시 변환하는 방법

Answer 2

일반적으로 큰 정수는 바이트 어레이로 표시됩니다. DLR에서 Microsoft의 Biginteger 구현을 볼 수 있습니다. Knuth가 개발 한 알고리즘을 사용했다고 생각합니다

Answer 3

이것을 확인하십시오 Biginteger 도서관 그리고 a 매우 기본적인 샘플 코드 7 세의 세계에서.

C에서 내 집 요리 코드 중 일부에 관심이 있다면 (곱셈 만) :

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

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

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

이것은 내가 참여한 이전 프로그래밍 콘테스트 중 일부에서 작동합니다.) 그러나 더 빠른 곱셈 알고리즘을 찾고 있다면 구현할 수 있습니다. Karatsuba 알고리즘, 나는 지금 이것을 실시간 콘테스트에서 개인적으로 사용합니다.

Answer 4

이봐, 이걸 확인해, 난 방금 숙제의 일부로 어제 완료했다.

#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 5

큰 정수 산술을 위해 라이브러리를 사용할 수 있습니다. Wikipedia에는 ​​목록이 있습니다. 여기.

Answer 6

또 다른 접근법은 숫자를 플로트/더블로 곱하고 결과를 표시 할 때 소수점을 깎아내는 것입니다.