Numeri grandi

smalldragon
salve a tutti
vorrei sapere se c'è una libreria per windows visual c++ che gestisca i cosidetti bigint.
ho gia provato le seguenti librerie ma chi per un verso e chi per un altro non funzionano.
le librerie che ho provato sono:
miracl http://en.wikipedia.org/wiki/Arbitrary- ... #Libraries non funziona in fase di compilazione
biginteger https://mattmccutchen.net/bigint/ non funziona col la cin >>
grazie anticipatamente a chiunque mi sappia aiutare

Risposte
Rggb1
Hmm questa https://mattmccutchen.net/bigint/ sembra senza manutenzione, ultimo aggiornamento 2010 (magari non vuol dire nulla...)

Ma GMP non ti va bene, oppure non riesci a farla funzionare su visual?

apatriarca
Domande simili sono già uscite diverse volte in passato. Che cosa ci devi fare? Perché vuoi usare il C++ per gestire degli interi di grosse dimensioni (ci sono linguaggi che li supportano nativamente e che fanno un ottimo lavoro). Quali sono i tuoi limiti operativi (in quale intervallo di valori si devono trovare)? Per alcuni utilizzi e limiti potrebbero esistere librerie più specifiche ottimizzate per il tuo scopo.

GMP è una libreria abbastanza diffusa e utilizzata anche in software commerciali come Mathematica. Ci sarebbe anche MPIR che è un fork di GMP per fornire un miglior supporto alla piattaforma della Microsoft (dovrebbe quindi essere più facile da usare e installare in Visual Studio). Non ho idea se ci siano differenze.

claudio862
Io ho usato APFloat in passato, e mi sono trovato bene. Mi sembra anche di averla usata anche con Visual Studio. Non funziona su Windows a 64 bit (la libreria assume che sia usato il modello LP64 mentre Windows x64 usa LLP64). A parte quello dovrebbe funzionare quasi ovunque (io la usavo su un cellulare Symbian).
Rispetto a GMP ha il vantaggio di supportare numeri interi e razionali a precisione infinita, e reali e complessi a precisione arbitraria.
Da una breve ricerca sembra che sia spesso consigliata anche MPIR, però non la conosco.

smalldragon
ho provato a scaricare la libreria mpc ma quando vado a crearla mi dice che non trova i sorgenti
"Rggb":
Hmm questa https://mattmccutchen.net/bigint/ sembra senza manutenzione, ultimo aggiornamento 2010 (magari non vuol dire nulla...)

Ma GMP non ti va bene, oppure non riesci a farla funzionare su visual?

allora ho provato a scaricarla ma siccome mi da indicazioni di essere stata scritta per linux/unix non so proprio come fare per utilizzarla sotto windows visual studio.
"apatriarca":
Domande simili sono già uscite diverse volte in passato. Che cosa ci devi fare? Perché vuoi usare il C++ per gestire degli interi di grosse dimensioni (ci sono linguaggi che li supportano nativamente e che fanno un ottimo lavoro). Quali sono i tuoi limiti operativi (in quale intervallo di valori si devono trovare)? Per alcuni utilizzi e limiti potrebbero esistere librerie più specifiche ottimizzate per il tuo scopo.

GMP è una libreria abbastanza diffusa e utilizzata anche in software commerciali come Mathematica. Ci sarebbe anche MPIR che è un fork di GMP per fornire un miglior supporto alla piattaforma della Microsoft (dovrebbe quindi essere più facile da usare e installare in Visual Studio). Non ho idea se ci siano differenze.

siccome mi hanno trombato le funzioni natie dell' assembler (istruzioni int e operazioni di extra segmentali) quindi non posso più usare a gran livello il linguaggio assembler.
il linguaggio c++ a livello di potenza e molto vicino all'assembler.
ma ha un grandissimo difetto con le librerie natie non si può fare quasi nulla cosi alla fine si perde più tempo ad a cercare e a impararsi librerie che effettivamente a fare le cose.
gli altri linguaggi invece tendono ad essere troppo specifici per campi ben prestabiliti. ma questa e un altra storia!
per quanto riguarda i numeri devo fare operazioni complesse formattazione / compattamento e calcoli scientifici dove serve molta precisione.
"claudio86":
Io ho usato APFloat in passato, e mi sono trovato bene. Mi sembra anche di averla usata anche con Visual Studio. Non funziona su Windows a 64 bit (la libreria assume che sia usato il modello LP64 mentre Windows x64 usa LLP64). A parte quello dovrebbe funzionare quasi ovunque (io la usavo su un cellulare Symbian).
Rispetto a GMP ha il vantaggio di supportare numeri interi e razionali a precisione infinita, e reali e complessi a precisione arbitraria.
Da una breve ricerca sembra che sia spesso consigliata anche MPIR, però non la conosco.

pultroppo ho un sistema 64 bit cosi APFloat non la posso usare mentre MPIR non me la fa costruire

apatriarca
Ma a che cosa ti servono questi numeri molto grandi? Quali sono i requisiti della tuo progetto? Di quali operazioni hai bisogno? Non ho capito il commento sull'assembly. Esistono comunque molti linguaggi che supportano nativamente i big integer e che possono essere usati per progetti di ogni tipo..

smalldragon
al momento sto lavorando su dei dati che per compressione a 255 quindi per poterli implementare devo gestire operazioni (le 4 classiche al massimo l'elevamento a potenza) con numeri del ordine di 255^15 o al massimo 255^20 quindi portate in cifre numeri del ordine tra le 40 e le 60 cifre. sia interi che a virgola mobile.
il problema con l'assembler che adesso non si può più accedere direttamente all'hardwere senza passare per librerie scritte di solito in c++.
se mi lasciavano l'assembler così come era il problema lo avrei gia risolto da un paio di settimane mentre adesso sono 2 mesi che cerco di risolverlo senza riuscirci!

apatriarca
Non vero perché dovrebbe essere diverso. Se lo sai implementare in assembly, perché mai non dovressi essere in grado di farlo in C++? E poi perché non lo scrivi direttamente in assembly a sto punto? MASM esiste ancora che io sappia.

smalldragon
si il masm esiste ancora ma pultroppo nel sistema windows le funzioni a più basso livello tipo quella di accesso diretto all'hardwere sono state spostate di livello,per motivi di protezione, e quindi a livello di programmazione sia dei compilatori masm conpreso sono state inibite e virtualizzate quindi inaccessibili per quasi tutti i programmatori normali cioè non apparteneti a grosse multinazionali quali microsoft,intel etc etc le quali utilizzano dei compilatori speciali che costano milioni di euro se te li vendono e non te li vendono altrimenti si potrebbero scrivere sistemi operativi molto più performanti e loro non rischierebbero di non vendere. e questo il punto per quanto riguarda l'assembler.
per quanto riguarda il c++ il problema stà nel fatto che se non becchi la libreria giusta e te la studi non puoi fare granchè.
di solito la documentazione delle librerie e molto fallace quando riesci a trovarla.
per riscrivere la libreria hai bisogno di altre librerie ,perchè non tutte le funzioni che ti servirebbero stanno in quella base, quindi e un cane che si morde la coda.

apatriarca
[OT] Prima di tutto non mi sembra il caso di fare inutili polemiche sulle scelte della Microsoft. Se non ti piacciono i suoi strumenti di sviluppo puoi sempre usare qualche strumento della concorrenza. Per esempio puoi usare MinGW che è basato su gcc oppure assemblatori come yasm o nasm o fasm o .. [OT]

L'uso del linguaggio assembly x64 non risolve magicamente il problema di fare calcoli con interi di grosse dimensione in modo efficiente. Ha certamente alcune istruzioni che ne semplificano l'implementazione, ma gli algoritmi da usare sono alla fin fine gli stessi per ogni linguaggio di programmazione scelto. Ripeto quindi la mia domanda: che cosa ti impedisce di implementare l'algoritmo che hai in mente in assembly in un altro linguaggio? Perché in assembly saresti in grado di implementarlo e in C/C++ hai bisogno di guardarne l'implementazione di una qualche libreria?

Ritornando al tuo problema più specifico. I tuoi numeri non sono poi tanto grandi. In un simile range di valori l'algoritmo naive è probabilmente abbastanza veloce per la maggior parte degli usi (i metodi più complicati hanno una complessità inferiore ma costanti maggiori per cui in questo caso potrebbero non convenire). Hai esigenze di performance particolari?

Rggb1
"smalldragon":
il problema con l'assembler che adesso non si può più accedere direttamente all'hardwere senza passare per librerie scritte di solito in c++.

Pero' non capisco... a che ti serve 'accedere direttamente all'hardware'?

"apatriarca":
I tuoi numeri non sono poi tanto grandi. In un simile range di valori l'algoritmo naive è probabilmente abbastanza veloce per la maggior parte degli usi

Concordo.

smalldragon
no,per fortuna, non ci sono esigenze particolari di prestazioni basta che faccia come detto in precedenza le 4 operazioni.
ma con la precisione più alta possibile per tipi double e float.
mi sembra strano che in giro per windows visual c++ non ci sia una libreria funzionante
che definisca i tipi bigint, bigdouble, bigfloat da 40-60 cifre
insomma per farla breve la libreria che cerco dovrebbe :
poter accettare i numeri da 40-60 cifre
poterli conservare in variabili,vettori e matrici
poter svolgere le 4 classiche operazioni (+-/*) sia per le variabili che per i puntatori
poter visualizzare i suddetti nemeri.
se poi ci fosse anche una funzione che mi prelevi i numeri previrgola e quelli postvirgola (per i tipi double e float) sarebbe una cosa ottima ma se non ci fosse non sarebbe un problema.
in fondo quello che sto cercando non mi sembra poi cosi particolare.
per quanto riguarda l'assembler ho già provato fasm, yasm e molti altri compilatori simili ma ho riscontrato diversi problemi nell'ottimizzazione del codice il masm, pultroppo, è il migliore.
comunque ho un esperienza in assembler di oltre 25 anni e lo conosco meglio delle mie tasche quindi è meglio terminarla qui la discussione sull'assembler.

Rggb1
"smalldragon":
comunque ho un esperienza in assembler di oltre 25 anni e lo conosco meglio delle mie tasche quindi è meglio terminarla qui la discussione sull'assembler.

Ma che c'entra? Anche io ho esperienza di programmazione di oltre 25 anni (purtroppo! :-D) ma non era questa la domanda - comunque ho capito cosa intendevi.

Però da una rapida ricerca web sembra che MPIR sia la migliore scelta per win_64 (non l'ho mai provata poiché non ho mai avuto necessità). Che cosa intendi con "MPIR non me la fa costruire"? Perché - estraggo dal manuale MPIR 2.5.1, sezione 2.4 "Notes for Particular Systems", pag. 12:
For building with MSVC we provide a number of ways.
In addition, project files for MSVC are provided, allowing MPIR to build on Microsoft’s compiler.
For Visual Studio 2010 see the readme.txt file in the build.vc10 directory. The MSVC projects provides full assembler support and for ‘x86_64’ CPU’s this will produce far superior results. These project files can also be accessed via the command line with the batch files ‘configure.bat’ and ‘make.bat’ which have a ‘unix like’ interface , however they are not very well tested and are due to be replaced.

Della serie: "non siamo molto sicuri che 'sta roba sia correttissima, però funziona". :)

apatriarca
comunque ho un esperienza in assembler di oltre 25 anni e lo conosco meglio delle mie tasche quindi è meglio terminarla qui la discussione sull'assembler.

Mi dispiace essere suonato polemico, ma non era questa la mia intenzione e il significato delle mie domande.

Sto semplicemente cercando di capire perché tu abbia difficoltà ad implementare queste classi in C++ senza ricorrere ad una libreria. Gli algoritmi per calcolare la somma, la differenza, la moltiplicazione o la divisione tra interi di grandi dimensioni sono indipendenti dal particolare linguaggio usato. Alcune istruzioni in assembly possono certamente rendere più facile l'implementazione di alcuni di questi algoritmi, ma non vedo alcuna ragione per cui non sia possibile implementare la stessa logica in un linguaggio di più alto livello, eventualmente rendendola un po' meno efficiente (e ci sono in effetti diverse implementazioni di classi di questo tipo nei più svariati linguaggi). Siccome l'efficienza non sembra al momento essere tra le tue priorità e non riesci a trovare librerie che facciano al caso tuo, credo che questa sia l'idea migliore.

In cosa incontri quindi difficoltà nell'implementare tale classe in C++? Che istruzioni assembly hai bisogno/desiderio di "emulare" in C++?

smalldragon
allora in assembler il problema si sarebbe risolto in questa maniera:
siccome tutti i tipi matematici primari tipo int double float hanno come lunghezza massima un registro -1 bit perchè il bit iniziale rappresenta il segno.
poi il significato dei bit interni a questo registro a seconda del tipo int e double viene trattato in maniera diversa a seconda del tipo.
adesso se si forza questo registro a concatenarlo ad altri registri spostando l'esponente all'ultimo registro che si vuol considerare il numero utilizzato sarà a più cifre.
per farti capire meglio:
un numero e immaganizzato nella seguente maniera n * 10^y ed è giustamente immaganizzato in un unico registro.
e a seconda del registro il numero può essere a 7-15-31-63 bit ho escluso il bit segno
adesso in assembler si concatenano + registri solamente accedendo all'hardware perdendo un ulteriore bit che indicherà se il registro e concatenato oppure no.
alla fine si ottiene n+n+n * 10^y bit - naturalmente i bit di concatenamento (-1 per ogni n) e il bit segno.
poi si fanno delle semplici funzioni per le 4 operazioni e una funzione di conversione tra come veniva trattato prima il registro e dopo e il gioco e fatto
in assembler tutto questo mi sarebbe venuto naturale e semplice da fare ma adesso con tutte le limitazioni che ci hanno imposto ciò non lo si può più fare.
in c++ senza funzioni specifiche per i bit e quindi librerie apposite ciò non si può fare.
per non parlare poi della riprogrammazione di tutti i vari operatori overload et affini un vero manicomio.
in oltre bisognerebbe fare tutto il trattamento per ogni tipo di dato cioè per int, double e float.
quindi come vedi non è cosi semplice e rapido fare il tipo big.
come per esempio sul guazzabuglio delle librerie ti faccio questo esempio
pensa tu che per gestire una semplice stringa in c++ bisogna includere una libreria apposita che è di sistema, per fortuna!, ma è pur sempre una libreria e poi l'enorme confusione tra string e wstring con tutte le varie modalità.
mentre con l'assembler lascio a te dedurre.

hamming_burst
[UOT: UltraOT]
"Rggb":

Della serie: "non siamo molto sicuri che 'sta roba sia correttissima, però funziona". :)

il famoso Lemma dell'Ingegnere :D

[/UOT]

smalldragon
sinceramente non ho capito l'ultima risposta

apatriarca
Hai insomma difficoltà ad allontanarti dall'hardware e ad astrarre un po' l'algoritmo che hai in mente.

Se ho capito bene, vuoi semplicemente memorizzare il tuo numero \( x \in \mathbb N \) (considero per ora solo i numeri naturali) dividendolo in blocchi di \(b\) bits (che suppongo essere tutti della stessa dimensione per comodità). Ogni blocco conterrà un numero compreso tra \(0\) e \(10^y - 1\) (per un opportuno \(y\) tale che \( y < \log_2 (b-1) \). Se \(x_i\) è il valore contenuto nell'\(i\)-esimo blocco allora \(x\) si otterrà con la formula:
\[ x = \sum_{i = 0}^{\lfloor \log_{10^y} x \rfloor} x_i\,10^{i\,y}. \]
Il segno, se ho capito bene, lo distribuiresti su tutti i blocchi. Avendo quindi valori compresi tra \(1 - 10^y\) e \(10^y - 1\).

L'idea della lista di registri in cui un bit determina se c'è una continuazione o meno non la copierei. In C++ un'idea più normale sarebbe quella di usare un semplice array per contenere il numero. Siccome i tuoi numeri sono abbastanza piccoli, allocherei semplicemente un numero fisso di blocchi (diciamo fino ad arrivare a 256bit?). A questo punto somma e sottrazione sono immediati. Il prodotto e la divisione sono un po' più complicati e ci sono probabilmente diversi algoritmi possibili (partirei dal più semplice e immediato di tutti).

Su double o float il discorso mi sembra decisamente più complicato di quello che il tuo post abbia voluto descrivere. E' in questo caso maggiormente importante descrivere nel dettaglio la diversa semantica dei vari operatori e se il numero deve rappresentare numeri decimali correttamente o meno. Il numero 0.1 è infatti ad esempio periodico in base 2... nonostante abbia solo una cifra decimale dopo la virgola.

vict85
Per la concatenazione basta usare un array (eventualmente allocato dinamicamente), se vuoi essere sicuro sulla dimensione di ogni elemento dell'array esiste la libreria standard cstdint (non supportato da vecchi standard in realtà perché viene dal penultimo standard C). Per un array unsigned di 32 bit per esempio devi scrivere uint32_t. Visual Studio usava comunque da anni delle macro per le dimensioni, per esempio un unsigned da 32 bit era segnato come unsigned __int32 (penso che in visual studio non sia necessaria nessuna libreria per usarlo ma non è portabile).

A seconda di quale siano le tue necessità potresti avere gestioni di memoria e tipi diversi. Per esempio potrebbe essere meglio allocare staticamente della memoria e poi "metterci dentro i numeri" oppure potrebbe essere meglio allocare dinamicamente i numeri o addirittura allocarli staticamente come array della dimensione massima sensata (usare semplicemente degli array di 25-26 uint8_t, 6-7 uint32_t o 3-4 uint64_t). Per il segno uno static cast a int8_t nel primo elemento potrebbe fare al caso tuo.
Considerando che li vuoi mettere in array e matrici, e che 20/25 byte sono pochi, ritengo che la dimensione fissa possa essere la soluzione ottimale. Inoltre, negli altri casi, creare un array di elementi di quel tipo non ti garantisce di usare blocchi di memoria consecutiva per elementi contigui (a meno di fare un grosso lavoro di gestione della memoria ogni volta che devi cambiare la dimensione).

smalldragon
va beh visto che non c'è niente di già fatto.
grazie per le informazioni cerchèro di crearla io la classe anche se sarà un lavoraccio.

Rggb1
Ma scusa, dall'impostazione che hai fatto nelle varie richieste non sembra tu abbia bisogno di una classe. Forse più semplicemente puoi usare il C e creare le funzioni che ti servono...

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.