Perché i decimali a precisione arbitraria sono usati in pratica su numeri razionali?

3

L'aritmetica di base di un chip di computer può funzionare solo su numeri (interi o in virgola mobile) di una dimensione fissa.

Ci sono molti algoritmi che potrebbero essere estesi per lavorare su numeri di dimensioni arbitrarie (e alcuni li richiedono). Pertanto, è utile avere un modo per archiviare ed eseguire operazioni aritmetiche con numeri di dimensione arbitraria.

Per numeri interi arbitrari, l'approccio di solito è di prendere una lista di byte (che ognuno può memorizzare un valore nell'intervallo 0-255) e avere il "numero grande" finale (spesso abbreviato come bignum ), quindi sii base-256, utilizzando ognuno di questi byte come "cifre" (ducentiquinquagintiquinquesexa-its?).

Per ogni numero reale non numerato non intero, esistono due diversi modi di rappresentazione:

  • decimali , che consistono in una mantissa ed esponente di "numero grande" di dimensioni arbitrarie. Il numero è rappresentato da sign(+1 or -1) * mantissa * pow(base, exponent) (dove base è in genere 2 o talvolta 10 )
  • rationals , che hanno un numeratore e un denominatore di una dimensione numerica arbitraria. Il numero è rappresentato da numerator / denominator

In pratica, ho trovato molte più lingue e librerie da utilizzare / supportare tipi di dati decimali rispetto ai tipi di dati razionali. Un esempio di questo sono gli archivi di dati (SQL), che hanno un tipo di dati DECIMAL nativo ma non razionale.

Perché è così? Perché i tipi di dati decimali sono preferiti rispetto a quelli razionali?

    
posta Qqwy 25.08.2016 - 12:58
fonte

4 risposte

1

Un cavillo

I decimali arbitrari di precisione sono in realtà abbastanza rari. Per esempio. anche se si cita SQL nella domanda, lo standard SQL non richiede implementazioni per supportare precisione arbitraria. Per esempio. MS SQL Server supporta solo fino a 38 cifre di precisione. Altre librerie potrebbero essere descritte più accuratamente come a supporto della precisione variabile piuttosto che della precisione arbitraria: ad es. La BigDecimal di Java opera all'interno di un MathContext che definisce la precisione dei risultati di un'operazione. Una vera implementazione di precisione arbitraria non richiede di impegnarsi in prima linea per la precisione di cui avrete bisogno in futuro. (Sì, questo significa che deve necessariamente essere pigro).

Rilevanza

Perché sto facendo questa distinzione? Perché quando si lavora con precisione fissa (limitata, come in SQL Server o variabile, come in Java), una serie di operazioni utilizza una quantità di memoria prevedibile. Quando si lavora con i razionali, d'altra parte, l'utilizzo della memoria può crescere senza limiti.

Questa è una differenza importante che, a mio parere, spiega in gran parte perché storicamente i progettisti di linguaggi e biblioteche hanno favorito i decimali rispetto ai razionali. Specialmente quando si guarda ad es. SQL, che è un prodotto di un'epoca in cui la memoria era molto più limitata di oggi, ha senso scegliere una rappresentazione che ti consenta di limitare in anticipo l'utilizzo della memoria.

Altri fattori plausibili

Non dico che i limiti di memoria sono l'unico fattore che ha influenzato le decisioni di progettazione. Ci sono altri due fattori plausibili che vengono in mente prontamente:

  • La familiarità delle prime generazioni di informatici con tabelle decimali di logaritmi ecc.
  • Supporto hardware. Nel corso della giornata, alcuni set di istruzioni includevano istruzioni per operare su decimale con codice binario.
risposta data 26.08.2016 - 12:19
fonte
5

Un motivo potrebbe essere semplicemente che i programmatori sono più abituati alle rappresentazioni dei numeri decimali o che la loro libreria arbitraria di precisione non supporta i razionali.

Un altro motivo potrebbe essere una penalità aggiuntiva per le prestazioni:

Una operazione centrale che devi certamente fare su numeri razionali è ridurre numeratore e denominatore. Se si continua a calcolare (aggiunta, moltiplicazione, ecc.) Su numeri razionali, il numeratore e il denominatore di solito crescono rapidamente (ad esempio quando si aggiungono due numeri senza fattori comuni).

La riduzione dei numeri razionali richiede la determinazione del massimo comun divisore, operazione costosa rispetto a una semplice aggiunta di numeri razionali.

In generale, a/b + c/d può essere calcolato da (a*d + c*b) / (b*d) , vale a dire tre moltiplicazioni intere e una addizione. Tuttavia, questo rende numeratore e denominatore grandi. Ad esempio, 1/3 + 1/6 = 9/18 anziché 1/2 . (Naturalmente, questi possono essere resi un po 'più efficienti, ma la complessità del caso peggiore è la stessa.)

Quindi, è necessario calcolare il gcd. Questo è un ulteriore passaggio di calcolo. (Anche se, da un punto di vista teorico, la complessità del caso peggiore è probabilmente la stessa delle operazioni decimali.)

Modifica

Altre spiegazioni perché suppongo che l'aritmetica razionale potrebbe essere più lenta nella pratica dell'aritmetica decimale. (Anche se questo dovrebbe essere testato, ad esempio utilizzando gmp .)

Le operazioni di base (aggiungi, moltiplica) su interi e decimali di precisione arbitrari hanno una complessità teorica di O(log n) , che è lineare nel numero di bit. Quindi per aggiungere due decimali n , hai bisogno di O(log n) di tempo.

I numeri razionali sono rappresentati da due numeri interi di precisione arbitrari. Una prima osservazione che si può fare è che sia il numeratore che il denominatore possono avere lo stesso numero di cifre (decimali) rispetto alla sua controparte decimale. (Anche se questo non è vero per tutti i numeri, ad esempio 1/3 , e la rappresentazione binaria è anche una storia diversa. Ma in molti casi, questo è il caso.)

Considera, ad es. 0.000000000000000994030870125414 (30 cifre). In razionale vale 5040335316639481 / 5070602400912917605986812821504 (16 + 31 cifre). Pertanto, per una semplice aggiunta, entrambe le rappresentazioni richiedono operazioni su ca. 30 cifre: l'operazione di aggiunta decimale è in realtà solo un'aggiunta basata sulla cifra, mentre l'aggiunta nei razionali sono tre moltiplicazioni e una aggiunta, senza contare il gcd.

Nota : sono non a favore di numeri razionali. Dipende veramente dall'applicazione quale sia la rappresentazione più utile.

    
risposta data 25.08.2016 - 13:15
fonte
1

Come rappresenti un numero irrazionale come e come numero razionale?

Puoi chiudere arbitrariamente, ma ciò richiederebbe numeratori e denominatori estremamente grandi.

Per evitare di sovraccaricare la memoria per un solo numero, dovrai limitare la precisione o il numero di posizioni dietro il punto decimale che ti piacerà.

Questo è ciò che fai usando i decimali.

    
risposta data 25.08.2016 - 13:55
fonte
0

Per la maggior parte delle applicazioni, i decimali sono solo efficienti e abbastanza buoni; e le alternative specializzate esistono, se necessario.

I numeri razionali non sono molto utili nella vita reale. Non appena si lascia l'intervallo + - * /, ci si trova in numeri irrazionali, che per definizione non possono essere scritti come 'a / b'.

I numeri interi ti danno la matematica esatta per + - *; razionale ti fornisce la matematica esatta solo per /, e tutto il resto (sqrt, log, sin, ecc.) deve supportare i numeri irrazionali .

Se trovi un modo esatto di memorizzare i numeri irrazionali esatti (incluso trascendente irrazionale ), sarebbe qualcosa che probabilmente sarebbe molto utile. Ma questo non è possibile.

    
risposta data 25.08.2016 - 13:55
fonte

Leggi altre domande sui tag