ضرب اثنين طويلة الدولية

Question

أنا أعمل على برنامج في C كجزء من الواجب المنزلي الذي يجب أن أحصل عليه من نتاج رقمين طويلين تؤخذ كسلسلة شخصية. على سبيل المثال: 123456789021 و 132456789098. نظرا لأنها تؤخذ كسلسلة، قمت بتحويلها إلى فترة طويلة طويلة للتكاثر. ولكن المنتج الناتج سيكون كبيرا جدا (أكبر من طويلة طويلة الدولية أعتقد). يمكن لأي شخص يرجى اقتراح لي طريقة لأداء هذا الضرب؟

Answer 1

هنا نهج واحد: النظر في كيفية ضرب هذه الأرقام باليد، على الورق. تنفيذ هذه الطريقة في C. سيتعين عليك اكتشاف:

• كيفية تفكيك عدد صحيح (تمثل كسلسلة) في أرقام
• كيفية تحويل كل رقم مرة أخرى إلى عدد صحيح 0 <= d < 10
• كيفية إدارة صفائف الأرقام (أي. كيف يجب أن تجعل المصفوفات؟)
• كيفية كتابة حلقة (ق) قد تحتاج إلى تنفيذ الضرب
• كيفية إدارة حمل المنتجات من رقم واحد إلى التالي
• كيفية تحويل تلك الأرقام العودة إلى الشخصيات للإخراج

Answer 2

عادة ما يتم تمثيل الأعداد الصحيحة الكبيرة كصفيفات بايت. يمكنك إلقاء نظرة على تطبيق Microsoft Biginteger في DLR. أعتقد أنهم استخدموا الخوارزميات التي طورها Knuth

Answer 3

افحص هذا مكتبة biginteger. و نموذج عينة أساسي جدا من العالم من سبعة.

إذا كنت مهتما ببعض الرموز المنزلية المطبوخة في C (الضرب فقط):

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

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

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

يعمل هذا في بعض مسابقات البرمجة السابقة التي شاركت فيها؛) ولكن إذا كنت تبحث عن خوارزمية مضاعفة أسرع يمكنك تنفيذها خوارزمية Karatsuba.أنا شخصيا استخدم هذا الآن في مسابقة الوقت الحقيقي.

Answer 4

يا رجل، تحقق من ذلك، لقد أكملت للتو يوم YUSTER كجزء من واجبي المنزلي:

#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

يمكنك استخدام مكتبة للأرتيهي الكبير Arithmetik، Wikipedia لديه قائمة هنا.

Answer 6

سيكون نهج آخر مضاعفة الأرقام كما تعويم / مزدوج وتقطيع العشري عند عرض النتائج.