Codifica banalmente ordinabile per decimali arbitrari di precisione

Question

Codifica banalmente ordinabile per decimali arbitrari di precisione

#1 da (2 voti)
#2 da (2 voti)

4

Sto cercando un modo ragionevolmente (*) efficiente in termini di spazio per codificare decimali di precisione arbitraria (ad esempio BigDecimal ), in modo tale che quando si ordina il modello di bit delle codifiche lessicograficamente, i numeri verranno ordinati numericamente. Questo è legato a questa domanda StackOverflow .

Un approccio semplice / ingenuo a questo sarebbe convertire il numero in una rappresentazione simile a IEEE con un esponente di 8 byte (che è ciò che RR nel NTL fa?), Ma ovviamente questa è una rappresentazione abbastanza inefficiente (*).

C'è forse qualche altro approccio a questo? Esistono ottimizzazioni possibili per gli interi in precisione arbitraria? La codifica non ha bisogno di supportare altre operazioni che l'ordinamento (e, se possibile, la decodifica di nuovo del numero).

(*) In termini ragionevoli, non intendo dire mettere insieme bit in byte come fa IEEE-754. Semplicemente non voglio avere campi inutilmente grandi che rimarranno per lo più vuoti in un gran numero di situazioni (come sarebbe il caso con un esponente di 8 byte). Il motivo per questo è che il numero (codificato) verrà successivamente elaborato da questo schema , che richiede alcuni millisecondi per byte da eseguire.

L'efficienza di runtime della codifica / decodifica d'altra parte non è un grosso problema (qualsiasi cosa in meno di 10 ms per 128 byte di dati sarà ancora oscurata dal runtime dello schema OPE apprezzato in precedenza).

(Nota anche, questa dovrebbe essere una rappresentazione decimale, quindi ci sono problemi di precisione dovuti a "cose binarie".)

numbers algorithms efficiency numeric-precision

posta Dexter 25.06.2014 - 08:24

fonte

2 risposte

Leggi altre domande sui tag numbers algorithms efficiency numeric-precision

"Proprietà contenitore" definizione del modello di progettazione approfondita Attraversare un AST usando Visitatori

score 2 · Answer 1

Lo schema generale per l'ordinamento di BigDecimal funziona come segue:

Ordina il bit del segno.
- Nota: se il bit del segno è negativo, l'ordinamento dei passaggi successivi deve essere annullato.
Rimuovi il bit del segno e converti i bit rimanenti in valore assoluto.
- In altre parole, viene utilizzata una rappresentazione della grandezza del segno.
Ordina per la posizione del "set di bit più alto".
- Se A > 0 e B > 0 e highestNonZeroBit(A) > highestNonZeroBit(B) , quindi A > B .
- Per altre basi come i decimali, usa highestNonZeroDigit della base corrispondente.
Se il più alto indice bit diverso da zero è lo stesso per A e B , risolvi il legame ordinando il resto dei bit. Ciò potrebbe richiedere di esaminare quanti bit ci sono nei numeri.

Il motivo per cui l'ordinamento tramite la rappresentazione IEEE funziona (come menzionato nel link OP alla domanda StackOverflow ) è che il La rappresentazione IEEE segue lo schema sopra descritto, a condizione che il problema byte-endian sia stato curato .

Il problema dello "spreco" di un campo esponenziale tipo IEEE-754 a 8 byte può essere risolto codificandolo in uno dei file codice universale . In particolare, codifica delta di Elias sembra essere utile per la tua applicazione.

Se la stringa di bit è memorizzata senza alcun campo o delimitatore di bit (come nel caso della codifica delta di Elias), la ricerca della cifra non zero più alta dovrà essere modificata come segue.

Supponiamo che la rappresentazione complessiva sia ancora "segno-grandezza", o "segno-esponente-grandezza", o "segno-esponente-esponente-grandezza".
Come affermato in precedenza, un segno negativo deve causare l'annullamento del successivo ordine di selezione.
Iniziando dal bit più significativo a sinistra, cerca il primo bit impostato.
Sottrai questo valore (indice del primo bit diverso da zero) dalla lunghezza della stringa di bit. Questa differenza può quindi essere utilizzata per il confronto.

score 2 · Answer 2

Un interessante problema di informatica. Una strategia di codifica che ha ottenuto ciò avrebbe necessariamente più o meno le seguenti caratteristiche.

Il segno è rappresentato in modo tale che il bit di ordine superiore è 1 per i valori positivi e tutti i bit successivi sono completati per il negativo.
L'esponente è codificato come la sua grandezza, preceduto dalla sua lunghezza (che deve essere corretta). Un esponente positivo ha una lunghezza preceduta da 1 bit, il negativo ha 0 e la lunghezza e l'ampiezza completate.
La mantissa è codificata come una frazione normalizzata, occupando il numero di bit necessario. La funzione di confronto dovrebbe assumere che i bit finali siano zero.

Il layout è qualcosa di simile.

S 1L EEEE MMMMMMMMMMMMMMM
S 0L EEEEE MMMM

È molto più semplice se il requisito di precisione arbitrario viene eliminato o leggermente allentato.

Si noti che ciò dipende dalla presenza di una rappresentazione canonica e non c'è spazio per NaN o valori simili. Zero non è zero.