Násobení polynomů v C

[JayCube]

Zdravim, potřeboval bych poradit. Potřebuji napsat program v C, který vynásobí dva zadané polynomy. Vstupem jsou koeficienty a nejvyšší mocnina (např. mocnina 3 a koeficienty 2, 3, 5, 2 znamená 2x^3+3x^2+5x+2). Normálně polynomy násobit umím, ale nejde mi to naprogramovat. Něco už jsem sice dal dohromady,ale není to dost efektivní (Musí to zvládnout vynásobit přes 90000 členů za méně než dvě vteřiny). Našel by se tu nějaký dobrák, který by mi poradil?

[Reklama]

[faraon]

Záleží na čem to budeš počítat, jestli na osmibitovém Commodore 64 s frekvencí necelého 1MHz, tak za ty dvě sekundy vynásobíš možná 9000 členů, ale kdybys měl k dispozici Cray Titan (aktuální vítěz TOP500), tak jich za stejnou dobu zvládneš určitě 90000000000000. Ale žere přes 20 megawattů

K věci. Zkus tohle, nic rychlejšího mě nenapadlo (doufám že to není blbost, už jsem to ze školy trochu pozapomněl):

max1 - nejvyšší mocnina prvního polynomu
max2 - nejvyšší mocnina druhého polynomu
maxv - nejvyšší mocnina výsledku

pol1[1000] - koeficienty prvního polynomu
pol2[1000] - koeficienty druhého polynomu
vysl[2000] - výsledek, před výpočtem vynulovat!

Je to alokované staticky s limitem do x^999, to by pro běžné výpočty mohlo stačit

Koeficienty jsou v polích uloženy tak, že index buňky odpovídá mocnině, takže ten tvůj příklad 3: 2, 3, 5, 2 bude v paměti takhle:
max1=3;
pol1={2,5,3,2,0,0,0,0,0,...};
Rozepsané by to bylo 2*x^0 + 5*x^1 + 3*x^2 + 2*x^3 + 0x^4 atd.
Můžou tam samozřejmě být i záporná čísla.

A roznásobí se to dvěma vnořenými cykly:

Kód: Vybrat vše

maxv=max1+max2;
for (i=0;i<=max1;++i)
    for (j=0;j<=max2;++j)
        vysl[i+j]+=pol1[i]*pol2[j];

Výsledek je v poli uspořádaný stejně jako vstupy, tedy také o obráceném pořadí.

---

P.S. Tak jsem se na to vyspal a přepočítal si ručně, blbost to fakt není:

Kód: Vybrat vše

index|  0  |  1  |  2  |  3  |  4  |  5  |  6  |  7  |
     | x^0 | x^1 | x^2 | x^3 | x^4 | x^5 | x^6 | x^7 |
-----+-----+-----+-----+-----+-----+-----+-----+-----+
pol1 |   2 |   5 |   3 |   2 |   0 |   0 |   0 |   0 | = 2x^3 + 3x^2 + 5x + 2
-----+-----+-----+-----+-----+-----+-----+-----+-----+
pol2 |   3 |   1 |   0 |   4 |   0 |   0 |   0 |   0 | = 4x^3 (+ 0x^2) + x + 3
-----+-----+-----+-----+-----+-----+-----+-----+-----+
     |   6 |   2 |   0 |   8 |     |     |     |     |
     |     |  15 |   5 |   0 |  20 |     |     |     | mezivýsledky postupně
     |     |     |   9 |   3 |   0 |  12 |     |     | přičítané k výsledku
     |     |     |     |   6 |   2 |   0 |   8 |     |
-----+-----+-----+-----+-----+-----+-----+-----+-----+
vysl |   9 |  17 |  14 |  17 |  22 |  12 |   8 |   0 | = 8x^6 + 12x^5 + 22x^4 + 17x^3 + 14x^2 + 17x + 9
-----+-----+-----+-----+-----+-----+-----+-----+-----+

Zkusil jsem těch tvých 90000 členů, vygeneroval jsem si dva náhodné polynomy do mocniny 300 (takhle jsi to myslel?) s koeficienty do 1000, a na mém vraku s 1,2GHz to vynásobení trvalo 0,003 sekundy se čtyřiašedesátibitovými čísly. Dvaatřicetibitový int by na to ale bohatě stačil.

[JayCube]

Tak to je paráda. Já se s tim dělal několik dní, měl jsem ten výpočet skoro na 60 řádků a stejně to pořádně nefungovalo . Ty použiješ dva cykly a jede to. Akorát ty pole jsem si alokoval dynamicky, ve škole to tak po nás chtěli (ale to je detail, to umím).

Standartním testem to prošlo bez problémů, takže mám splněno, ale máme tam ještě "bonusový test" a při něm to nahlásilo "Pád programu (segmentation fault)". Tuším, že to znamená, že sahám do paměti někam kam bych neměl. Prvni ze zadaných polynomů měl nejvyšší mocninu 80194 , druhý nevím, takže to asi spadlo už při načítání vstupu. Přikládám zdroják, kdyby jsi měl náhodou chvilku čas :

Kód: Vybrat vše

#include <stdio.h>
#include <stdlib.h>


int main( void )
{
    int i, j, tmp, A, B;
    int *koef_A, *koef_B, *vys;


    printf("Zadejte stupen polynomu A:\n");
    if( scanf("%d", &A)!=1 || A<0 )
    {
        printf("Nespravny vstup.\n");
        return 1;
    }

    printf("Zadejte koeficienty polynomu A:\n");
    koef_A = (int *) malloc( (A+1) * sizeof(int) );
    for( i=0; i<(A+1); i++ )
    {
        if( scanf("%d", &tmp)!=1 )
        {
            printf("Nespravny vstup.\n");
            return 1;
        }

        koef_A[i] = tmp;
    }


    printf("Zadejte stupen polynomu B:\n");
    if( scanf("%d", &B)!=1 || B<0 )
    {
        printf("Nespravny vstup.\n");
        return 1;
    }

    printf("Zadejte koeficienty polynomu B:\n");
    koef_B = (int *) malloc( (B+1) * sizeof(int) );
    for( i=0; i<(B+1); i++ )
    {
        if( scanf("%d", &tmp)!=1 )
        {
            printf("Nespravny vstup.\n");
            return 1;
        }

        koef_B[i] = tmp;
    }


/* Když jsou oba stupně nula */
    if( A==0 && B==0 )
    {
        printf("%d\n", koef_A[0]*koef_B[0]);
        return 0;
    }


/* Výpočet */
    vys = (int *) malloc( (A+1)*(B+1) * sizeof(int) );

    for( i=0; i<(A+1)*(B+1); i++ )
    {
        vys[i] = 0;
    }

    for ( i=0; i<A+1; i++ )
    {
        for ( j=0; j<B+1; j++ )
        {
            vys[i+j] += koef_A[i] * koef_B[j];
        }
    }


/* Uvolnění paměti */
    free( koef_A );
    free( koef_B );


/* Výpis výsledku */
    if( (A+1)*(B+1)==2 )
    {
        if( vys[0]==-1 )printf("-x");
        else if( vys[0]==1 ) printf("x");
        else if( vys[0]!=0 ) printf("%dx", vys[0]);

        if( vys[1]<0 ) printf("%d", vys[1]);
        else if( vys[1]>0 ) printf("+%d", vys[1]);
    }
    else
    {
        j=0;
        for( i=0; i<(A+B); i++ )
        {
            if( vys[i]!=0 )
            {
                if( vys[i]>0 && j!=0 ) printf("+");
                else if( vys[i]==-1 ) printf("-");
                if( vys[i]!=1 && vys[i]!=-1 )printf("%d", vys[i]);
                printf("x");
                if( (A+B)-i>1 ) printf("<sup>%d</sup>", (A+B)-i);
            }
            j++;
        }

        if( vys[i]<0 ) printf("%d", vys[i]);
        else if( vys[i]>0 ) printf("+%d", vys[i]);
    }

    printf("\n");

    return 0;
}



Děkuji za pomoc.

[faraon]

Není tam náhodou nějaké omezení ohledně paměti? Ty totiž netestuješ návratové hodnoty malloc(), takže se nedozvíš, jestli se paměť podařilo naalokovat, nebo ne. Buď od té funkce dostaneš ukazatel, nebo NULL, a na adresu 0 se zaručeně zapisovat nedá (tedy dá, je tam tabulka vektorů přerušení, ale určitě jí nedostaneš přidělenou jako pracovní).

Mě to při 100000:100000 také hodí SIGSEGV. Samotné vstupy se do toho prostoru sice vejdou, ale už není místo pro pole výsledků! Takže ošetři ty návratové hodnoty, a přemýšlej co s tím, jestli v takovém případě nahlásit chybu a skončit, nebo zkusit vymyslet něco jiného:

Kód: Vybrat vše

    printf("Zadejte koeficienty polynomu A:\n");
    if ((koef_A = (int *) malloc( (A+1) * sizeof(int) )))
       for( i=0; i<(A+1); i++ )
       {
           if( scanf("%d", &tmp)!=1 )
           {
               printf("Nespravny vstup.\n");
               return 1;
           }

           koef_A[i] = tmp;
       }
    else
       {
       printf("Malo pameti pro polynom A.\n");
       return 1;
       }

To provede tohle, místo pádu programu:

Kód: Vybrat vše

Zadejte stupen polynomu A:
Zadejte koeficienty polynomu A:
Zadejte stupen polynomu B:
Zadejte koeficienty polynomu B:
Malo pameti pro vysledek.

A také neuvolňuješ paměť pole výsledků, ono se to sice obvykle udělá automaticky při ukončení programu, ale nejde na to spoléhat. Takže buď otestuj jestli v těch ukazatelích není NULL (pokud je, tak ti to také spadne) a pak je teprve uvolni (a rovnou si do nich zapiš svůj NULL), nebo to uspořádej takhle, aby program vůbec neprováděl části, které jsou v takovém případě zbytečné:

Kód: Vybrat vše

if (1. malloc)
   {
   načtení 1;
   if (2. malloc)
      {
      načtení 2;
      if (3. malloc)
         {
         výpočet;
         zobrazení;
         free 3;
         }
      else
         chyba 3;
      free 2;
      }
   else
      chyba 2;
   free 1;
   }
else
   chyba 1;

To se mi osvědčilo hlavně při otevírání víc souborů

V Céčku se prostě musí hlídat úplně všechno, tenhle jazyk za tebe neudělá vůbec nic, správně bys měl kontrolovat i to co ti hlásí printf() a nějak na to reagovat

---

Ale blbost! Asi mi teprve začíná po ránu zapínat IQ, tak jsem si ty alokované velikosti spočítal ručně.

Takže první alokace zabere 400004 bajtů.
Druhá alokace zabere také 400004 bajtů.
A alokace pro výsledek by měla zabrat 800008 bajtů, ale zabere 40000800000 bajtů!
40 giga RAM teda fakt nevlastním

Takže takhle:
if ((vys = (int *) malloc( (A+B+2) * sizeof(int) )))
a při nulování pole:
for( i=0; i<((A+B+2)); i++ )

To mi připomnělo toho astronauta, co si na let k Měsíci vzal sebou pro jistotu logaritmické pravítko, protože tomu řídícímu počítači prostě nevěřil, a všechno co do něj zadal si přepočítával osobně

No, tomu mému vraku to trvalo 11:34 minuty

Jen takový fór, uhodneš co udělá tohle?

Kód: Vybrat vše

int main(void)
    {
    int p[10],a,b,c;

    p[10]=12345;

    return 0;
    }

[JayCube]

Omlouvám se za zpoždění, poslední dobou toho mám nějak moc a k programování jsem se vůbec nedostal.

S tou alokací paměti jsi měl pravdu. Teď už to nehlásí chybu, ale je to moc pomalé (limit máme 6 sekund). Asi to bude chtít nějaký lepší algoritmus. Ale jak jsem říkal, je to jenom bonusový test. Zatím to tu nechám odemčené, ještě se k tomu vrátím.

Samozřejmě děkuji za pomoc.

[faraon]

Vyzkoušej jak rychlé by to bylo s tou statickou alokací, možná je problém i tam.

Zkus se podívat na tohle:
http://ppershing-bsc-thesis.googlecode. ... moenck.pdf
http://en.wikipedia.org/wiki/Sch%C3%B6n ... _algorithm