Programma Numeri Primi su commissione

di il
50 risposte

50 Risposte - Pagina 2

  • Re: Programma Numeri Primi su commissione

    Quindi secondo te io scrivo :

    long int A = 200000000…unmilione di zeri / 2 e mi produce l'output come se niente fosse ?

    Qual'è la differenza tra int e long int ? boh ?
  • Re: Programma Numeri Primi su commissione

    aleasia ha scritto:


    Quindi secondo te io scrivo :

    long int A = 200000000…unmilione di zeri / 2 e mi produce l'output come se niente fosse ?

    Qual'è la differenza tra int e long int ? boh ?
    No, perche non usa i tipi del C.
    La differenza tra int e long int dipende dall'ambiente, può anche non esistere.
    Tipicamente (o meglio "una volta") un int era da 16 bit, e un long int sinonimo di long, cioè 32.
    Oggi possono essere di tutte le lunghezze, 32 o anche 64 bit (ci sono le opportune macro e funzioncelle)

    Però, per tornare alla libreria, ti suggerisco di darci un'occhiata e magari scaricare qualche programma di esempio per vederla all'opera.
    Come detto ce ne sono tante altre, magari anche più facili da usare (tipicamente quelle native C++)
  • Re: Programma Numeri Primi su commissione

    Ti ripeto , sembra facile ma non lo è affatto . Di solito questi programmi sono fatti in Assembly.
  • Re: Programma Numeri Primi su commissione

    aleasia ha scritto:


    Ti ripeto , sembra facile ma non lo è affatto . Di solito questi programmi sono fatti in Assembly.
    Cosa non è facile?
  • Re: Programma Numeri Primi su commissione

    Io non sono in grado altrimenti non avrei chiesto niente a nessuno .
  • Re: Programma Numeri Primi su commissione

    Ho trovato solo questa libreria tratto da wikipedia :
    La GNU multipla di precisione aritmetica Library (GMP) è un libero libreria per l'aritmetica precisione arbitraria , che operano su firmati interi , razionali , e in virgola mobile numeri. [3] Non ci sono limiti pratici per la precisione, tranne quelli implicati dalla disposizione la memoria nella macchina GMP gira su (limite di dimensione operando è 2^32 -1 bit su macchine a 32-bit e 2^37 bit su macchine a 64-bit).

    Quindi come puoi ben vedere non è facile , costruire questo tipo di programma .
  • Re: Programma Numeri Primi su commissione

    Correggo ho trovato in un sito questo articolo , forse avevi ragione +m+ , dal sito non si può scaricare , l'ho scaricata da un altra parte comunque , grazie a tutti.

    Riporto l'articolo :

    Si tratta di una libreria molto potente per gestire operazioni aritmetiche a precisione arbitraria, ossia illimitata. La lunghezza delle cifre presenti nei numeri è limitata solamente dalla quantità di memoria presente sul PC che ospita il programma. Tale libreria ha lo scopo di, oltre che a trattare numeri enormi, essere il più veloce possibile. Per questo essa è, senza dubbio, una delle più performanti e potenti del settore. Tale risultato è raggiunto grazie a particolari ed efficienti algoritmi matematici, a volte un po' astrusi e complicati ma sicuramente molto veloci. E' distribuita gratuitamente sotto le licenze GPL e LGPL e, al momento della scrittura dell'articolo è presente la fresca versione 6.1.0. E' disponibile per Linux ma con qualche accorgimento particolare si può effettuare il "porting" su Windows. Essa non è distribuita già pronta e utilizzabile ma deve essere compilata sul proprio PC. In questo modo il processo di creazione tiene conto delle caratteristiche dell'hardware in modo da sfruttare in pieno, e al meglio, tutte le informazioni del computer ospitante, ai fini del raggiungimento della massima velocità operativa possibile. [...]
  • Re: Programma Numeri Primi su commissione

    aleasia ha scritto:


    Ho trovato solo questa libreria tratto da wikipedia :
    La GNU multipla di precisione aritmetica Library (GMP) è un libero libreria per l'aritmetica precisione arbitraria , che operano su firmati interi , razionali , e in virgola mobile numeri. [3] Non ci sono limiti pratici per la precisione, tranne quelli implicati dalla disposizione la memoria nella macchina GMP gira su (limite di dimensione operando è 2^32 -1 bit su macchine a 32-bit e 2^37 bit su macchine a 64-bit).

    Quindi come puoi ben vedere non è facile , costruire questo tipo di programma .
    E' quella che ti ho già segnalato precedentente.
    In realtà non devi "costruirla" (difficile), bensì "usarla" (relativamente facile).

    Se vuoi vedere come funziona puoi scaricare i sorgenti e studiarteli.
  • Re: Programma Numeri Primi su commissione

    Hai modificato il messaggio ed era sulla pagina precedente l'ho visto solo adesso , infatti non capivo quando l'avevi scritto.
  • Re: Programma Numeri Primi su commissione

    @alesia, c'e' stato un gran cianciare su un argomento decisamente interessante e complesso.

    Allora, riassumiamo: librerie per la gestione di numeri di dimensione arbitraria ce ne sono diverse. La piu' famosa e' GMP (GNU MultiPrecision Library), ed immagino sia esattamente quella che hai trovato.

    https://gmplib.org

    Piu' interessanti sono i CAS (Computer Algebra System) che permettono di poter lavorare direttamente con tali numeri, ed implementano gia' gli algoritmi di fattorizzazione, test di primalita', ed ovviamente le operazioni matematiche.

    Il piu' bello, a mio avviso, e' Mathematica, ma e' a pagamento (non costa molto). Ci sono molte alternative gratuite, ma forse il migliore e' Maxima.

    http://maxima.sourceforge.net

    Le operazioni di somma, sottrazione si implementano esattamente come si farebbe a mano.
    Per la moltiplicazione e la divisione ci sono diversi metodi, i piu' banali dei quali e' esattamente quello che si usa quando si fanno le operazioni con carta e matita.

    Gli algoritmi li trovi anche su Wikipedia.
    Come libri: Handbook of Applied Cryptography (trovi i PDF gratuiti) e The Art of Computer Programming Volume 2 (per palati fini )
    Ovviamente ce ne sono altri, basta cercare con Google.

    https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic
    http://cacr.uwaterloo.ca/hac

    Il test di primalita' e' un problema DIFFICILE: infatti sono stati trovati algoritmi STATISTICI che permettono di supporre che un numero sia primo a meno di una probabilita' imposta come parametro (1/100, 1/000, 1/100000000, ecc). NON ESISTE UN ALGORITMO sicuro al 100%, se non facendo tutti i test possibili (il che potrebbe richiedere tempi dell'ordine dei miliardi di anni anche mettendo in parallelo TUTTI i computer del mondo )

    La fattorizzazione e' un problema DIFFICILE: non esistono algoritmi in grado di fattorizzare numeri , se non per tentativi. Comunque, numeri di 200 cifre (decimali, circa 650 cifre binarie) sono ancora trattabili.

    Ben piu' complicato e' analizzare numeri di 1024/2048 bit: infatti i vari HTTPS, FTPS, SSH, SSL, ecc si basano su numeri di 2048 bit.

    NON ESISTE un algoritmo per generare numeri primi: i primi SI CERCANO.

    Il sistema e' banale: si inizia con un numero dispari, si usa un test di primalita', se non lo passa, si aggiunge 2 e si ricomincia. Ci sono sistemi piu' efficienti, ma non si va molto piu' lontano da questo banale sistema. Quello che fanno e' sfruttare tutta una serie di regole per usare passi piu' ampi di 2.

    OVVIAMENTE i due problemi sono strettamente correlati: se si dovesse trovare un test di primalita' sicuro al 100% ed efficiente, si potrebbe anche trovare un algoritmo efficiente per la fattorizzazione.

    https://en.wikipedia.org/wiki/Primality_tes

    https://it.wikipedia.org/wiki/Fattorizzazion

    https://en.wikipedia.org/wiki/Mersenne_prim
  • Re: Programma Numeri Primi su commissione

    aleasia ha scritto:


    Ho trovato solo questa libreria tratto da wikipedia :
    Dovresti imparare a cercare meglio, ad esprimerti in modo più chiaro, ed a leggere con maggiore attenzione quello che ti viene scritto. Non si può parlare di numeri primi in precisione arbitraria e pensare che un "test di primalità" come AKS o Rabin-Miller sia un concorso a premi.

    All'inizio di sono elencate praticamente tutte le più note librerie in multiprecisione disponibili gratuitamente e di un certo interesse. Anche gli storici snippets di Bob Stout (RIP) contengono una implementazione didattica elementare, senza troppe pretese ma di facile lettura, contribuita da tale Cliff Rhodes.

    Vi sono poi in giro altre dozzine di librerie analoghe, tra balocchi accademici, come parti degli arcinoti package opensource per il calcolo numerico e simbolico (da SAGE a PARI-GP a tutto il carrozzone della Knoppix Math), verticalizzazioni special purpose e ovviamente prodotti commerciali. Come giustamente scriveva il grande , "The easiest machine applications are the technical/scientific computations.", e di sicuro sono anche quelle più a buon mercato, soprattutto finché si parla di piattaforme banali, sistemi mainstream, applicazioni accademiche e poco oltre.
  • Re: Programma Numeri Primi su commissione

    Si hai ragione , ma credo che capiti a tutti di fare un po' di confusione , credimi se ti dico che ho scoperto queste cose solo oggi e di anni non ne ho pochi , quindi ero rimasto con l'idea che fosse più difficile di quello che era leggendo sui vari forum risposte negative e inconcludenti , poi figurati quando mi sono sentito dire che era una cosa banale ho fatto ancora più confusione.
  • Re: Programma Numeri Primi su commissione

    @ aleasia

    Sei sempre interessato ad avere sorgenti da studiare, come da te richiesto nel primo post, oppure sei abbastanza soddisfatto da come l'argomento è evoluto ?
    Fammi sapere, se vuoi anche in mp.
  • Re: Programma Numeri Primi su commissione

    migliorabile ha scritto:


    @alesia, c'e' stato un gran cianciare su un argomento decisamente interessante e complesso...
    Il test di primalita' e' un problema DIFFICILE: infatti sono stati trovati algoritmi STATISTICI che permettono di supporre che un numero sia primo a meno di una probabilita' imposta come parametro (1/100, 1/000, 1/100000000, ecc). NON ESISTE UN ALGORITMO sicuro al 100%
    ... proprio sicuro?
  • Re: Programma Numeri Primi su commissione

    aleasia ha scritto:


    ...quindi ero rimasto con l'idea che fosse più difficile di quello che era leggendo sui vari forum risposte negative e inconcludenti ...
    cambia forum
    Ma niente di che, la stragrande maggioranza dei forummisti generalisti sono bimbiminkia o assimilabili (con le dovute eccezioni).
    Argomenti come quelli che hai sollevato sono da un lato ignoti (a bimbiminkia e simili), dall'altro well known (per chi si occupa invece seriamente).

    In sostanza è come chiedere "ma un trapianto di fegato come si fa?" in un forum non-medico.

    Se trovi un chirurgo ti dirà "è facile", per tutti gli altri "pressochè impossibile".
Devi accedere o registrarti per scrivere nel forum
50 risposte