Libreria per gestione numeri interi(dimensione "infinita").

di
Nanni16
il
6 risposte
N
Nanni16
Utente Attivo
Iscritto da
mar, 2015
Messaggi:
69

Libreria per gestione numeri interi(dimensione "infinita").

Ciao a tutti ragazzi non sapendo cosa fare ho voluto creare una libreria C per le gestione di numeri interi senza segno(NISS) di grosse dimensioni.
Non avendo un esperienza esagerata nella programmazione non ho più idee di come poterla migliorare.
Se avete voglia e vi intriga tutto ciò vi allego quello che ho già fatto cosi che voi possiate darci un'occhiata, e suggerirmi algoritmi migliori (i miei sono un po lenti) o qualsiasi miglioramento voi riteniate corretto. Ve ne sarei molto grato.
Ogni funzione è spiegata e nel file .c ci sono anche delle piccole analisi in termini di tempo sul mio pc.
Più avanti sicuramente aggiungerò una funzione DIV per la divisione intera magari restituendo anche il resto.
Math.h 
#ifndef MATH_H
#define MATH_H
#include <stdlib.h>
#include <stdio.h>
/* NISS: Struttura dati per gestire numeri interi senza segno di grosse dimensioni(potenzialmente infinite).
         Nota: Se bisogna fare molte operazioni conviene passare alla massima base rappresentabile: UINT_MAX
               per por ripassare in base decimale.
*/
typedef struct NISS_ *NISS;

/* Init: Inizializza una struttura dati NISS che conterrà il valore <numero> considerato in base 10
         e trasformato in base <base>.*/
NISS Init(unsigned int numero,unsigned int base);
/* Free: Si occupa di deallocare la struttura NISS */
void Free(NISS a);
/* Print: Si occupa di stampare su f, il numero contenuto in a*/
void Print(FILE *f,NISS a);
/* Atoi: Ritorna un valore long long int che rappresenta in base dieci il numero contenuto in a
         se si dovesse verificare overflow ritorna valore -1*/
long long int Atoi(NISS a);
/* Cfr: Ritorna numero di cifre del numero contenuto in a*/
unsigned int Cfr(NISS a);
/* Base: Ritorna il valore della base di rappresentazione del numero a*/
unsigned int Base(NISS a);
/* CMP: Funzione che confronta due srutture NISS a e b.
        Ritorna 0 se a=b, -1 se a<b, 1 se a>b, 5 in caso di errore.
        Nota: l'operazione ha senso solo se a e b sono rappresentati con la stessa base.*/
int CMP(NISS a,NISS b);
/* INC: Funzione che incrementa il valore di a di un unità
        Ritorna 1 in caso di fallimento altrimenti 0*/
int INC(NISS a);
/* DEC: Funzione che incrementa il valore di a di un unità
        Ritorna 1 in caso di fallimento altrimenti 0*/
int DEC(NISS a);
/* ADD: Funzione che somma due numeri precisamente equivale a: a=a+b.
        I numeri a e b devono essere rappresentati con la stessa base.
        Ritorna 1 in caso di fallimenro altrimenti 0*/
int ADD(NISS a,NISS b);
/* SUB: Funzione equivalente a: a=a-b. Notare che NISS rappresenta numeri senza segno perciò ha senso solo se a>=b.
        I numeri a e b devono essere rappresentati con la stessa base.
        Ritorna 1 in caso di fallimento altrimenti 0*/
int SUB(NISS a,NISS b);
/* MUL: Funzione equivalente a: a=a*b. Il prametro a deve essere passato per riferimento.
        I numeri a e b devono essere rappresentati con la stessa base.
        Ritorna 1 in caso di fallimento altrimenti 0*/
int MUL(NISS *a,NISS b);
/* CHGBase: Funzione che cambia la base di rappresentazione del parametro a.
            La base finale è determinata dal valore del paramtro <base>(massimo: UINT_MAX).
            Ritorna valore 1 in caso di fallimento altrimenti 0*/
int CHGBase(NISS *a,unsigned int base);

#endif // MATH_H
Math.c 
#include "Math.h"
#define CAR 16
char legenda[CAR+1]="0123456789ABCDEF";
/* NISS: Struttura dati per gestire numeri interi senza segno di grosse dimensioni.
   -    vect: vettore di interi, ogni sua locazione rappresenta una cifra.
   -    base: indentifica la base di rappresentazione del numero contenuto in vect.(dimensione massima UINT_MAX)
   -    size: identifica il numero di cifre 'locazioni' di vect.(dimensione massima UINT_MAX)
*/
struct NISS_{
    unsigned int *vect;
    unsigned int base;
    unsigned int size;
};

NISS Init(unsigned int numero,unsigned int base){///100.000.000(cicli con anche Free): 28.8 Secondi numero=rand()*rand(),base=rand()+2
    NISS a=NULL;
    unsigned int v[sizeof(unsigned int)*8]={0};
    int i;
    if(base<=1)
        return NULL;
    a=(NISS)malloc(sizeof(struct NISS_));
    if(a==NULL)
        return NULL;
    if(numero==0){
        a->vect=(unsigned int*)malloc(sizeof(unsigned int));
        if(a->vect==NULL){
            free(a);
            return NULL;
        }
        a->base=base;
        a->size=1;
        a->vect[0]=0;
        return a;
    }
    for(i=0;i<sizeof(unsigned int)*8;i++){
        if(v[i]==0&&numero==0)
            break;
        v[i]=numero%base;
        numero=numero/base;
    }
    while(i>=0&&v[i]==0)
        i--;
    a->vect=(unsigned int*)malloc(sizeof(unsigned int)*(i+1));
    if(a->vect==NULL){
        free(a);
        return NULL;
    }
    a->base=base;
    a->size=i+1;
    for(i=0;i<a->size;i++)
        a->vect[i]=v[a->size-i-1];
    return a;
}
void Free(NISS a){
    if(a==NULL)
        return;
    if(a->vect==NULL){
        free(a);
        return;
    }
    free(a->vect);
    free(a);
    a=NULL;
}
void Print(FILE *f,NISS a){
    if(f==NULL||a->vect==NULL)
        return;
    int i;
    if(a->base<=16){
        for(i=0;i<a->size;i++)
            fprintf(f,"%c",legenda[a->vect[i]]);
        fprintf(f,"\n");
        return;
    }
    for(i=0;i<a->size;i++)
        fprintf(f,"%u ",a->vect[i]);
    fprintf(f,"\n");
}
long long int Atoi(NISS a){
    long long int temp=0;
    int i;
    if(a==NULL||a->vect==NULL)
        return -1;
    for(i=0;i<a->size;i++){
        temp=temp*a->base;
        if(temp<0)
            return -1;
        temp=temp+a->vect[i];
        if(temp<0)
            return -1;
    }
    return temp;
}
unsigned int Cfr(NISS a){
    if(a==NULL)
        return -1;
    return a->size;
}
unsigned int Base(NISS a){
    if(a==NULL)
        return -1;
    return a->base;
}
int CMP(NISS a,NISS b){
    if(a==NULL||a->vect==NULL||b==NULL||b->vect==NULL||a->base!=b->base)
        return 5;
    int i;
    if(a->size>b->size)
        return 1;
    else if(a->size<b->size)
        return -1;
    for(i=0;i<a->size;i++)
        if(a->vect[i]<b->vect[i])
            return -1;
        else if(a->vect[i]>b->vect[i])
            return 1;
    return 0;
}
int INC(NISS a){///1.000.000.000(cicli): 8.21 Secondi     a=(0,10)
    if(a==NULL||a->vect==NULL)
        return EXIT_FAILURE;
    int i=a->size-1;
    while(i>=0&&a->vect[i]==a->base-1){
        a->vect[i]=0;
        i--;
    }
    if(i<0){
        a->size++;
        a->vect=(unsigned int*)realloc(a->vect,sizeof(unsigned int)*a->size);
        if(a->vect==NULL){
            free(a);
            a=NULL;
            return EXIT_FAILURE;
        }
        for(i=a->size-1;i>0;i--)
            a->vect[i]=a->vect[i-1];
        a->vect[i]=0;
    }
    a->vect[i]++;
    return EXIT_SUCCESS;
}
int DEC(NISS a){///1.000.000.000(cicli): 8.35 Secondi     a=(1.000.000.000,10)
    if(a==NULL||a->vect==NULL||(a->size==1&&a->vect[0]==0))
        return EXIT_FAILURE;
    if(a->size==1&&a->vect[0]==1){
        a->vect[0]=0;
        return EXIT_SUCCESS;
    }
    int i=a->size-1;
    while(i>=0&&a->vect[i]==0){
        a->vect[i]=a->base-1;
        i--;
    }
///Siccome cosideriamo il dato di input corretto non cè bisogno di controllare i<0 significherrebe
///che il vettore ha come primo elemento uno 0, cosa non possibile.
    if(i==0&&a->vect[i]==1){
        a->size--;
        for(i=0;i<a->size;i++)
            a->vect[i]=a->vect[i+1];
        a->vect=(unsigned int*)realloc(a->vect,sizeof(unsigned int)*a->size);
        return EXIT_SUCCESS;
    }
    a->vect[i]--;
    return EXIT_SUCCESS;
}
int ADD(NISS a,NISS b){///1.000.000.000(cicli): 29.54 Secondi   ADD(a,b) a=(0,10) b=(4,10)
    if(a==NULL||a->vect==NULL||b==NULL||b->vect==NULL||a->base!=b->base)
        return EXIT_FAILURE;
    int i,j,carry;
    long long int temp;
    if(a->size<b->size){
        a->vect=(unsigned int*)realloc(a->vect,sizeof(unsigned int)*b->size);
        if(a->vect==NULL){
            free(a);
            a=NULL;
            return EXIT_FAILURE;
        }
        for(i=b->size-1;i>=b->size-a->size;i--)
            a->vect[i]=a->vect[i-b->size+a->size];
        while(i>=0)
            a->vect[i--]=0;
        a->size=b->size;
    }
    for(i=a->size-1,j=b->size-1,carry=0;i>=0&&j>=0;i--,j--){
        temp=(long long int)a->vect[i]+b->vect[j]+carry;
        if(temp/a->base>0){
            carry=1;
            a->vect[i]=temp%a->base;
        }
        else{
            carry=0;
            a->vect[i]=temp;
        }
    }
    if(carry){
        while(i>=0&&a->vect[i]==a->base-1){
            a->vect[i]=0;
            i--;
        }
        if(i==-1){
            a->size++;
            a->vect=(unsigned int*)realloc(a->vect,sizeof(unsigned int)*a->size);
            if(a->vect==NULL){
                free(a);
                a=NULL;
                return EXIT_FAILURE;
            }
            for(i=a->size-1;i>0;i--)
                a->vect[i]=a->vect[i-1];
            a->vect[i]=0;
        }
        a->vect[i]++;
    }
    return EXIT_SUCCESS;
}
int SUB(NISS a,NISS b){///1.000.000.000(cicli): 22.91 Secondi   SUB(a,b) a=(UINT_MAX,10),b=(4,10)
    if(a==NULL||a->vect==NULL||b==NULL||b->vect==NULL||a->base!=b->base||CMP(a,b)==-1)
        return EXIT_FAILURE;
    int i,j,carry,temp;
    for(i=a->size-1,j=b->size-1,carry=0;i>=0&&j>=0;i--,j--){
        temp=a->vect[i]-b->vect[j]+carry;
        if(temp<0){
            a->vect[i]=a->vect[i]+a->base+carry-b->vect[j];
            carry=-1;
        }
        else{
            carry=0;
            a->vect[i]=temp;
        }
    }
    if(carry){
        while(a->vect[i]==0){
            a->vect[i]=a->base-1;
            i--;
        }
        a->vect[i]--;
    }
    for(i=0;i<a->size&&a->vect[i]==0;i++);
    if(i!=0){
        if(i==a->size){
            a->size=1;
            a->vect=(unsigned int*)realloc(a->vect,sizeof(unsigned int));
            if(a->vect==NULL){
                free(a);
                a=NULL;
                return EXIT_FAILURE;
            }
            return EXIT_SUCCESS;
        }
        for(j=0;j<a->size-i;j++)
            a->vect[j]=a->vect[j+i];
        a->size=a->size-i;
        a->vect=(unsigned int*)realloc(a->vect,sizeof(unsigned int)*a->size);
        if(a->vect==NULL){
            free(a);
            a=NULL;
            return EXIT_FAILURE;
        }
    }
    return EXIT_SUCCESS;
}
int MUL(NISS *a,NISS b){/// 100.000(cicli): 76.69 Secondi   MUL(&a,b) a=(1,10),b=(2,10)
    if((*a)==NULL||(*a)->vect==NULL||b==NULL||b->vect==NULL||(*a)->base!=b->base)
        return EXIT_FAILURE;
    int i,j,z,x,t,carry;
    long long int temp,temp1;
    NISS c=NULL;
    c=(NISS)malloc(sizeof(struct NISS_));
    if(c==NULL)
        return EXIT_FAILURE;
    c->size=(*a)->size+b->size;
    c->base=(*a)->base;
    c->vect=(unsigned int*)calloc(c->size,sizeof(unsigned int));
    if(c->vect==NULL){
        free(c);
        return EXIT_FAILURE;
    }
    //Considero aSize>bSize
    for(i=b->size-1,z=c->size-1;i>=0;i--,z--){
        for(j=(*a)->size-1,x=z,carry=0;j>=0;j--,x--){
            temp=(long long int)(*a)->vect[j]*b->vect[i]+carry;
            carry=temp/c->base;
            if(carry>0){
                temp1=(long long int)c->vect[x]+(long long int)temp%c->base;
                if(temp1/c->base>0){
                    c->vect[x]=temp1%c->base;
                    t=x-1;
                    while(c->vect[t]==c->base-1){
                        c->vect[t]=0;
                        t--;
                    }
                    c->vect[t]++;
                }
                else
                    c->vect[x]=temp1;
            }
            else{
                temp1=(long long int)c->vect[x]+(long long int)temp%c->base;
                if(temp1/c->base>0){
                    t=x-1;
                    c->vect[x]=temp1%c->base;
                    while(c->vect[t]==c->base-1){
                        c->vect[t]=0;
                        t--;
                    }
                    c->vect[t]++;
                }
                else
                    c->vect[x]=temp1;
            }
        }
        if(carry){
            temp1=(long long int)c->vect[x]+carry;
            if(temp1/c->base>0){
                c->vect[x]=temp1%c->base;
                x--;
                while(c->vect[x]==c->base-1){
                    c->vect[x]=0;
                    x--;
                }
                c->vect[x]++;
            }
            else
                c->vect[x]=temp1;
        }
    }
    i=0;
    while(i<c->size-1&&c->vect[i]==0)
        i++;
    if(i!=0){
        for(j=0;j<c->size-i;j++)
            c->vect[j]=c->vect[j+i];
        c->size=c->size-i;
    }
    Free((*a));
    (*a)=c;
    return EXIT_SUCCESS;
}
int CHGBase(NISS *a,unsigned int base){/// 2^(100.000)in base UINT_MAX -> 2^(100.000) in base 10 Tempo: 26.30 Secondi
    if((*a)==NULL||(*a)->vect==NULL)
        return EXIT_FAILURE;
    NISS temp=NULL,basei=NULL,cifra;
    int i;
    temp=Init(0,base);
    if(temp==NULL)
        return EXIT_FAILURE;
    basei=Init((*a)->base,base);
    if(basei==NULL){
        Free(temp);
        return EXIT_FAILURE;
    }
    for(i=0;i<(*a)->size;i++){
        if(MUL(&temp,basei)){
            Free(temp);
            Free(basei);
            return EXIT_FAILURE;
        }
        cifra=Init((*a)->vect[i],base);
        if(cifra==NULL){
            Free(temp);
            Free(basei);
            return EXIT_FAILURE;
        }
        if(ADD(temp,cifra)){
            Free(temp);
            Free(cifra);
            Free(basei);
            return EXIT_FAILURE;
        }
        Free(cifra);
    }
    Free(basei);
    Free((*a));
    (*a)=temp;
    return EXIT_SUCCESS;
}

6 Risposte

  • O
    oregon
    Super Famoso
    Iscritto da
    nov, 2011
    Messaggi:
    21639

    Re: Libreria per gestione numeri interi(dimensione "infinita").

    Ma già ne esistono tante, affidabili e stabili....
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6049

    Re: Libreria per gestione numeri interi(dimensione "infinita").

    Lasciando perdere il fatto che librerie del genere esistono gia' (ad esempio la super-classica GMP https://gmplib.org), se vuoi approfondire l'argomento c'e' un ottimo libro da studiare:

    The Art of Computer Programming, Volume 2, di Donald E. Knuth.

    E li trovi anche come si implementa la DIVISIONE, che ovviamente e' la pecora nera delle 4 operazioni.
    Oltre a trovare metodi decisamente efficienti per l'implementazione della MOLTIPLICAZIONE (mooolto piu' efficienti ).

    Consiglio: passa tutto in C++ (cosi' puoi usare la normale sintassi nelle espressioni) e se vuoi fare il vero salto di qualita', implementa gli algoritmi elementari in assembler.

    NON SERVE scrivere tutto in assembler, ma ci sono dei sistemi per integrare l'assembler con il C: in pratica il tuo sorgente e' un sorgente C con inserito dei pezzi di codice in assembler

    In questo modo puoi sfruttare TUTTI i 32/64 bit che hai a disposizione e non solo 31 o 63

    Tieni sempre presente che:

    1) imparare ad usare una libreria lo puo' fare chiunque
    2) chi saprebbe realizzare la libreria (e magari non lo fa semplicemente perche' ne esiste gia' una) si puo' contare sulle dita della mano di un monco E fa la differenza, perche' puo' dare delle idee per fare altre cose
  • N
    Nanni16
    Utente Attivo
    Iscritto da
    mar, 2015
    Messaggi:
    69

    Re: Libreria per gestione numeri interi(dimensione "infinita").

    Grazie migliorabile, per la risposta esauriente.
    Bhè che dire mi avete distrutto le mie fantasie in men che non si dica

    L'efficienza della moltiplicazione intendi per esempio tramite la ricorsione ?(es.Karatsuba) non volevo complicarmi troppo la vita era giusto per giocare un pò eheheh.

    Per quanto riguarda al C++, bhe io sto facendo ingegneria informatica e programmazione ad oggetti la iniziamo il prossimo anno... quindi preferisco aspettare ad affrontarla da solo

    Invece sarei molto interessato a come si potrebbe integrare del codice assembler al C. Se hai voglia di spiegarmelo un pò meglio o passarmi qualche link in cui viene spiegato in maniera dettagliata te ne sarei molto grato.
    PS: l'assembly abbiamo appena iniziato a studiarlo a luglio avrò l'esame ehehe.

    pps: il punto due non ho capito se era un complimento o un modo per dire che perdo solo tempo a provare a costruire librerie che non sono degne di tale nome
  • M
    migliorabile
    Super Famoso
    Iscritto da
    apr, 2013
    Messaggi:
    6049

    Re: Libreria per gestione numeri interi(dimensione "infinita").

    Per quanto riguarda l'integrazione del C con l'assembler, non e' possibile insegnatelo in qualche post!
    Devi conoscere l'assembler e dipende dal compilatore!
    Ma trovi esempi in abbondanza.

    Inoltre, non ti derve conoscere l'INTERO Assembler, ma solo le operazioni legate alle operazioni aritmetiche tra interi, piu' qualche altra direttiva, e l'uso dei registri. Cose che si imparano in qualche serata davanti al PC

    Per il punto 2): non si perde mai tempo quando si dedica del tempo ad imparare come funzionano le cose che tutti gli altri usano senza avere la minima idea di come funzionano

    Se uno vuole inventare qualcosa di nuovo, di sicuro sa come funziona il vecchio!
  • N
    Nanni16
    Utente Attivo
    Iscritto da
    mar, 2015
    Messaggi:
    69

    Re: Libreria per gestione numeri interi(dimensione "infinita").

    Forse mi sono espresso male, ma intendevo dire che i rudimenti di assemblee che dici tu già li conosco, devo ancora capire bene il discorso che hanno fatto sugli interrupt e procedure... La mi curiosità era come fare nel senso pratico a integrare parti scritte in assembly al c.
  • M.A.W. 1968
    M.A.W. 1968
    Utente Attivo
    Iscritto da
    ott, 2011
    Messaggi:
    321

    Re: Libreria per gestione numeri interi(dimensione "infinita").

    wrugg25 ha scritto:

    credo converrebbe prendere il K&R e studiare gli ultimi due capitoli, che spiegano bene l'ìmplementazione di una parte della libreria standard, e soprattutto l'appendice A, che spiega esattamente come si "legge" il C (di fatto, è una sintesi del draft document dello standard).
    A tale assolutamente obbligatoria lettura si aggiunga, per lo studente più motivato ed ambizioso, lo studio integrale di almeno "The Standard C Library", P. J. Plauger, Prentice Hall PTR e "C Interfaces and Implementations", David Hanson, Addison-Wesley. Il primo contiene la completa anatomia della standard library, perfettamente valida ai fini didattici nonostante il tempo trascorso dalla pubblicazione; il secondo guida il lettore alla progettazione razionale e alla realizzazione di una completa e funzionale libreria C didattica. Ambedue doverosamente presenti in questa arcinota bibliografia sintetica che ormai circola da tempo immemorabile su FIDOnet, ML e forum assortiti (spesso dimenticando distrattamente di citarne la fonte e ringraziare l'autore, in questo come in altri assai meno banali casi, ma tant'è).

    Sarebbe inoltre auspicabile affiancare lo studio con l'analisi di uno degli esempi probabilmente più semplici e di maggior valore didattico, come il seminale lavoro di Cliff Rhodes "package of unsigned integer math for arbitrarily large numbers" contenuto nella storica raccolta degli Snippets C (RIP Bob Stout e Auke Reitsma).


    Per l'integrazione di Assembly inline e l'uso di moduli Assembly con un compilatore C, fa testo unicamente il manuale del compilatore stesso.
Devi accedere o registrarti per scrivere nel forum
6 risposte