Perché Haskell può gestire facilmente numeri molto grandi?

Question

Hugs> 94535^445 
1376320882321377050696053887661515621104890164005282153069726424773999801846841903244827702943487982707454966009456016735041878000604143500908532887464920380605164932112687039059526672109818924234920844448231612532570718657160234177285377733830104834041049076609912488237219608445995072867798430614935403219495883835042862802917980856774134757390782052200512932375660858045003581611863121089979673784484701791210379500218604466721285456487387736825167702127154268533859979529612671925052419513844416493584817268143587955662039327860394141299238613042312035808541735213479394437496215520277526351425482512084759462579494878772787079101513841720202004639843443083454387175700954018825292148776647553122504118229978165851660083576570848983047255050145168802863168613110619584686348869690774233051669081248424584219383477237544209892290799448207462345346336076966775224683516220960618177284844330167142846351091001423033864986042919757795382577032341453971393897073354841924116635150129850119992031076354249371062307034564093077675129303383786693131843907104175619570678630497198824622804914508555467550904967368926176118094672479099827962889569753303773699017596074205893197641101210911874606040804983166177455705972192827752532495287749766682029353154226049380290040508900715169403153139668217790502306177709467234413947747673881158973344492079455405942662489751581189327200960698310350121179918845099840977270519116578719881752429190273998774113278822810866144521416958558406602325070095207349450759264393913367193083149679216066539911941983836313340998945139132421885688290888674594474605510238217590823316979504437667252929278291853368754482552573193289277120902144178425726693671235675042499401282016643202758246845332593475338220708351934511933096882598943512036679145593929114103343255708217768511665236173107020739195152050863630870948954052925049746246549772984384435109578859863612603574306739909728739428192798727373799081111333186135697868385292787575475482883660605162944306327057220313320376280182432763977906971557137715710757099478269250731209785404487629107297262798803645379809868663503452656912571816192881412782623078761411808958183665272686617730596943579533808499348879195167683064937591552734375 

Perché Haskell può calcolare un numero così elevato e altre lingue, ad esempio Java, non possono (così facilmente)?

Answer 1

Java ha la classe BigInteger.

Potrebbe aver costruito questa funzione nel linguaggio, ma (come in molte lingue) tende a far sì che le caratteristiche primitive siano mappate strettamente su cose che sono supportate dalla CPU.

Haskell enfatizza invece l'espressività nello stile della notazione matematica, dove le considerazioni di "prestazioni" sono in gran parte irrilevanti.

Answer 2

La risposta breve e di base è che implementano valori di default diversi. In Java, un int standard è di 32 bit. Firmato, che offre un intervallo di −2,147,483,648 a +2,147,483,647.

Detto questo, Java ha anche classi bignum. Se li usi, avrai anche la possibilità di usare numeri arbitrariamente grandi.

Answer 3

Si tratta di come codificare i numeri. Il modo tradizionale per farlo è quello di codificare i numeri con un determinato numero di bit, in cui non è possibile avere una precisione infinita. Apparentemente Haskell fa questo con un numero variabile di bit per un numero che va bene, ma di solito significa che tutto il lavoro matematico è fatto nel software, poiché l'accelerazione hardware è generalmente disponibile solo per una precisione finita.

Answer 4

È possibile utilizzare BigInteger per fare la stessa cosa. Haskell è un linguaggio funzionale che è più conciso di Java.

Uno dei motivi per cui abbiamo così tante lingue è che le lingue diverse sono migliori in diversi compiti poiché sono state progettate con diversi presupposti. La maggior parte dei linguaggi funzionali è più semplice con funzioni matematiche ma tende a lottare con altri casi d'uso, ad es. haskell è improbabile che sia una buona scelta per scrivere una GUI.

Answer 5

Java ha la nozione di "Tipi di dati primitivi" (che sono i tipi supportati dal processore) e quelli sono diversi da tutte le altre classi.

In Haskell, Int è un tipo come tutti gli altri tipi, e quindi era facilmente fatto un membro dei Num e Integral typeclasses utilizzati in (^) ("(^) :: (Num a, Integral b) => a -> b -> a"). Un altro membro di quei typeclass è Integer, che supporta numeri interi di tutte le dimensioni (purché abbia memoria sufficiente per le loro cifre).

In Java, è possibile utilizzare molte librerie "Big Numbers", ma le operazioni per esse non utilizzano gli operatori di infissi a cui si è abituati, perché sono solo per "Tipi primitivi" in Java.

Answer 6

Come già detto, se si dispone di 32 parole bit e di utilizzare l'intera gamma si ottiene -2^31 a 2^31-1 usando complemento a due.

riservando alcuni bit della parola, questi bit possono essere utilizzati per trasportare informazioni sul tipo per il valore. Cioè, i valori "conoscono" il proprio tipo in fase di esecuzione. I bit rimanenti vengono utilizzati per trasportare i dati del valore.

I valori interi che si adattano a questi bit rimanenti possono essere memorizzati direttamente nella parola. Tali numeri interi sono in genere chiamati "fixnums". Se non si adattano, i bit di tipo della parola indicano che è un "bigint" e i bit rimanenti vengono utilizzati per memorizzare un puntatore di memoria nell'heap in cui è memorizzato il valore bigint.

Il compilatore deve tradurre le espressioni aritmetiche in più percorsi di codice che coprono le combinazioni di tipi consentite per gli operandi. Esempio per l'aggiunta:

• Fixnum + Fixnum
• bigint + Fixnum
• Fixnum + bigint
• bigint + bigint

Un sacco di ottimizzazioni in compilatori per queste lingue si concentrano su come evitare in testa per i controlli di tipo runtime necessari per farlo funzionare. Ci sono spesso anche modi per dire esplicitamente al compilatore che la retrocessione automatica da fixnum a bignum è indesiderata, e invece si desidera il comportamento di overflow degli interi a 32 bit. Questo può essere molto importante per implementare gli algoritmi di crittografia in modo efficiente.

Answer 7

letterali numeriche a Haskell sono sovraccarichi in modo che possano rappresentare più tipi concreti (come Int, Integer, Float o addirittura MyOwnNumber).

È possibile scegliere manualmente un tipo specifico fornendo informazioni sul tipo, in questo modo:

x = 4 :: Int 
y = 4 :: Integer 
z = 4 :: Float 

Questi tre valori hanno diversi tipi e le operazioni eseguite su questi si comporteranno in modo diverso.

La dimensione esatta di un Int dipende dall'implementazione ma può essere qualcosa come 28 bit, questo tipo si comporta come una primitiva Java int, ad es. traboccherà.

Un Integer è un tipo che può contenere interi precisione arbitraria, come il Java BigInteger.

E un Float è come un Java float, utilizzando l'aritmetica in virgola mobile.

Proprio come i valori letterali numerici, molti operatori sono sovraccaricati (utilizzando type classes) e possono quindi essere utilizzati con tipi diversi. Quindi l'operatore + può lavorare con entrambi gli Int se Float s.

Nel tuo caso, dal momento che non hai fornito alcuna informazione sul tipo, l'interprete utilizzerà automaticamente il tipo Integer. Ciò significa che per l'operatore ^, sceglierà anche l'istanza Integer. Consentendo calcoli integer di precisione arbitraria.

Answer 8

È una differenza nella filosofia di design:

• I progettisti di Haskell volevano essere sicuri che gli utenti non sarebbe sorpreso dal fallimento apparentemente arbitraria di un calcolo integer che necessitano di più di 32 bit.

• I progettisti di Java volevano essere sicuri che gli utenti non sarebbero sorpresi dal degrado delle prestazioni apparentemente arbitrario causato da molti calcoli su numeri interi che richiedono più di 32 bit.

In ogni lingua, devi fare qualcosa di speciale per ottenere l'altro tipo di numero intero.

C'è una lunga e onorevole storia di linguaggi che supportano numeri interi arbitrariamente grandi per impostazione predefinita. Due dei miei preferiti sono Icon e Smalltalk, che hanno entrambi più di 25 anni.