È ragionevole presumere che qualsiasi quantità fisica possa essere rappresentata da un numero intero a 64 bit senza overflow o underflow?

31

L'algoritmo di ricerca binaria originale nel JDK utilizzava interi a 32 bit e presentava un bug di overflow se (low + high) > INT_MAX ( link ).

Se abbiamo riscritto lo stesso algoritmo di ricerca binaria utilizzando interi (firmati) a 64 bit, possiamo supporre che low + high non superi mai INT64_MAX perché è fisicamente impossibile avere 10 ^ 18 byte di memoria?

Quando si usano interi (firmati) a 64 bit per rappresentare quantità fisiche , è ragionevole supporre che l'underflow e l'overflow non possano accadere?

    
posta Siqi Lin 24.02.2015 - 00:55
fonte

10 risposte

58

La risposta breve è no. Tuttavia, per alcune applicazioni la tua ipotesi potrebbe essere corretta.

Supponendo un int firmato, 2 ^ 63, con le virgole aggiunte per chiarezza, = 9,223,372,036,854,775,808. Quindi è all'incirca 9 * 10 ^ 18. 10 ^ 18 è un "Exa".

Wikipedia dice "A partire dal 2013, si stima che il World Wide Web abbia raggiunto 4 zettabyte. [12]" , che è 4000 Exabytes. Pertanto, il WWW è approssimativamente 400 volte più grande di 2 ^ 63 byte.

Pertanto, esiste almeno una quantità fisica che è molto più grande di un intero a 64 bit con segno (o senza segno). Supponendo che le tue unità siano byte . Se le tue unità fossero qualcosa di molto più grande, come GigaBytes, allora saresti o.k., ma la precisione della misurazione sarebbe bassa.

Per un altro esempio, considera le galassie lontane. La Galassia di Andromeda è in realtà una delle più vicine ed è a 2,5 * 10 ^ 6 anni luce di distanza. Se le tue unità fossero miglia , sarebbe 14,5 * 10 ^ 18, più di un intero con segno a 64 bit. Ora, ovviamente dipende dalle unità che usi per le tue misure, ma alcune galassie sono molto più lontane di Andromeda. ( Il più noto è 13 * 10 ^ 9 LY di distanza. ) A seconda sulla precisione che desideri per la tua misura, potrebbe sovrasfruttare un numero intero a 64 bit.

( Aggiunto ) Sì, le miglia sono un'unità schifosa per la distanza astronomica. Un'unità più normale potrebbe essere un'unità Astronomical , circa 93 milioni di miglia. Usando quell'unità di misura, la galassia più lontana è circa 10 ^ 15 A.U. (se la mia matematica è giusta), che si adatterebbe in un int di 64 bit. Tuttavia, se si desidera misurare anche la distanza dalla Luna, verso satelliti orbitanti vicini, quell'unità è troppo grande.

Un altro esempio di elettronica: il Farad (F), un'unità di capacità . I condensatori di grandi dimensioni vanno da 5 kF. E questo numero probabilmente aumenterà col passare del tempo mentre le auto ibride, le "smart grids", ecc. Migliorano. Una volta può misurare una capacità piccola come 10 ^ -18 F. Quindi l'intervallo complessivo nella capacità "reale" che possiamo misurare oggi è 5 * 10 ^ 21, più grande di un intero a 64 bit.

    
risposta data 24.02.2015 - 02:11
fonte
20

Non hai nemmeno bisogno di andare cosmico quando sono coinvolti i combinatorici. Ci sono 2 ^ 95 offerte possibili in un gioco di bridge e questo è sul lato piccolo della complessità.

    
risposta data 24.02.2015 - 17:01
fonte
17

La quantità fisica più pertinente per la tua domanda è RAM del computer .

Windows Server 2012 supporta fino a 4 TB della memoria fisica. Questo è 2 42 byte. Se le capacità della RAM continuano a raddoppiare circa ogni anno, in solo 17 anni da oggi "Windows Server 2032" supporterà 2 byte 62 di memoria fisica, momento in cui low + high raggiungerà 2 63 - 2 e bacierà il numero intero a 64 bit con segno massimo.

Spero che nessun sistema critico per la sicurezza fallisca, supponendo che 64 bit siano sempre sufficienti.

Per un uso leggermente più generale, la quantità fisica più rilevante è spazio indirizzo memoria . (È utile avere uno spazio di indirizzamento molto più ampio della memoria fisica, ad esempio per mettere molti stack in memoria, tutti con spazio per crescere.) Current x86-64 supportano gli indirizzi virtuali a 48 bit, quindi abbiamo solo 14 anni prima che queste CPU raggiungano il limite di spazio-indirizzo a 2 62 byte .

E poi c'è memoria condivisa distribuita "dove i ricordi (fisicamente separati) possono essere indirizzato come uno spazio di indirizzi (logicamente condiviso) ".

    
risposta data 24.02.2015 - 06:46
fonte
10

Is it reasonable to assume that any physical quantity can be represented by a 64-bit integer without overflow or underflow?

Non esattamente. Ci sono molti numeri che sono entrambi più grandi e più piccoli di questo, ed è per questo che abbiamo numeri in virgola mobile. I numeri in virgola mobile alterano la precisione minore per un intervallo migliore.

Nell'esempio specifico che hai citato, è altamente improbabile che tu abbia mai bisogno di un numero più grande di quello. 64 bit corrispondono a circa 18 quintilioni di elementi. Ma mai dire mai.

    
risposta data 24.02.2015 - 01:45
fonte
7

La tua ipotesi non gestirà le quantità fisiche che possono essere rappresentate solo da numeri in virgola mobile. E anche se decidessi di ridimensionare tutti i numeri, ad esempio moltiplicando tutti i numeri per 10000 (quindi i valori sono ancora interi ma possono essere rappresentati in decimillesimi), questo schema fallisce ancora per i numeri molto vicini allo zero, ad esempio la massa di elettroni (9.1094 * 10⎻³¹ kg).

Questa è una quantità fisica molto reale (ed estremamente piccola) , eccone altri avrai problemi con. E se si sostiene che non è una quantità fisica reale (anche se è in kg), prendere in considerazione:

10 kg (obviously physical quantity)
1 kg (same)
10⎻² kg (1/100 kg, or about 1/3 ounce) (also quite real)

Quindi vedi dove sto andando con questo. L'ultimo che non puoi gestire neanche.

Naturalmente, potresti avere un campo speciale all'interno del numero per scalare una porzione intera verso l'alto o verso il basso di un moltiplicatore di variabile; ora hai appena inventato il floating point.

    
risposta data 24.02.2015 - 08:58
fonte
5

Innanzitutto vorrei rispondere alla domanda su quali valori fisici possono / devono essere rappresentati da un numero intero?

L'intero è una rappresentazione di un numero naturale (e le differenze tra di loro) in un sistema informatico, quindi applicarlo a qualsiasi altra cosa è sbagliato. Quindi, invocare distanze o altre quantità che appartengono al dominio continuo non è un argomento. Per tali quantità ci sono rappresentazioni di numeri reali. E puoi sempre scegliere un'unità di dimensioni arbitrarie e adattare qualsiasi valore con una precisione data.

Quindi quali sono i valori fisici che sono numeri naturali e possono eccedere l'intero a 64 bit?

Posso pensare a due. Numero di oggetti fisici (come gli atomi) e livelli di energia in cui può essere inserito un sistema quantico. Sono due cose che sono strettamente intere. Ora, so che puoi dividere un atomo, ma produce ancora un numero intero e non puoi dividerlo indefinitamente. Entrambi possono superare facilmente l'intervallo a 64 bit dell'intero senza segno . Il numero di atomi è più alto e un atomo può essere in più di uno stato di energia.

Se l'informazione è fisica o meno, è molto discutibile. Direi che non lo è. Pertanto, non direi che la quantità di informazioni è una cosa fisica. Quindi non è la quantità di RAM o qualcosa del genere. Se lo permetti, allora il numero di atomi facilmente supera questo numero, perché hai bisogno di più di un atomo per archiviare un bit con la tecnologia di oggi.

    
risposta data 24.02.2015 - 15:22
fonte
4

Oltre alla risposta di Jerry101, vorrei offrire questo test molto semplice e pratico per la correttezza:

Supponiamo di allocare memoria tramite malloc , in un sistema operativo a 64 bit. Supponiamo che l'allocatore di memoria decida di restituire un blocco di memoria valido, della dimensione richiesta, ma in cui è impostato il 63 ° bit.

In altre parole, supponiamo che esistano alcuni ambienti di programmazione in cui 0xFFFFFFFFxxxxxxxx sono intervalli di memoria legittimi che potrebbero essere restituiti da una chiamata a malloc .

La domanda è: il tuo codice funzionerà ancora come previsto?

Quando la situazione analoga si verifica nei sistemi operativi a 32 bit, alcuni software non funzionano correttamente se vengono assegnati indirizzi di memoria "nella metà superiore". Originariamente, si pensava che tali indirizzi di memoria fossero disponibili solo per il codice privilegiato (sistemi operativi, driver di periferica e hardware periferico), ma a causa dello scricchiolio dello spazio degli indirizzi a 32 bit, i fornitori di sistemi operativi hanno deciso di far parte di quello spazio riservato disponibile per applicazioni che lo richiedono.

Fortunatamente, questa situazione è abbastanza improbabile che accada per i programmi a 64 bit per un po ', almeno non in un decennio.

Quando finalmente si verifica questa situazione, significa che i processori e i sistemi operativi indirizzabili a 128 bit sarebbero diventati mainstream in quel momento e che sarebbero stati in grado di fornire un "ambiente di emulazione a 64 bit" per consentire quelle "applicazioni legacy" "operare in base a presupposti simili ai sistemi operativi odierni a 64 bit.

Infine, si noti che questa discussione si concentra solo sugli indirizzi di memoria. Un problema simile ai timestamp deve essere preso con maggiore cautela, poiché alcuni formati di timestamp allocano un sacco di bit di precisione ai microsecondi, e quindi lascia meno bit disponibili per rappresentare il tempo in futuro. Questi problemi sono riepilogati nell'articolo di Wikipedia su Problema dell'anno 2038 .

    
risposta data 24.02.2015 - 08:18
fonte
4

Questa è una domanda che devi porre caso per caso. non dovresti utilizzare un'ipotesi generale secondo cui l'aritmetica a 64 bit non andrà in overflow, perché anche quando le quantità corrette si troveranno in un intervallo molto più piccolo, un'origine dati dannosa potrebbe finire per fornirti quantità irragionevoli che potrebbero overflow, ed è meglio essere preparati per questa situazione piuttosto che essere colpiti da esso in modo imprevisto.

Ci sono alcuni casi in cui ha senso scrivere codice che dipende dal non overflow dei numeri a 64 bit. La classe principale di esempio che conosco è il contatore, in cui il contatore viene incrementato ogni volta che viene utilizzato. Anche a un ritmo di un incremento per nanosecondo (non pratico) ci vorrebbe più di un secolo per traboccare.

Si noti che, sebbene a prima vista possa sembrare "sempre sbagliato in linea di principio" basarsi sul "tempo fino al fallimento" per la correttezza di un sistema, facciamo questo sempre con autenticazione / login. Dato un tempo sufficiente (per forzatura bruta), qualsiasi sistema di questo tipo (basato su password, chiavi private, token di sessione, ecc.) È rotto.

    
risposta data 24.02.2015 - 19:25
fonte
2

È POSSIBILE che una grandezza fisica non si adatti a 64 bit? Ovviamente. Altri hanno sottolineato il conteggio del numero di atomi al sole o del numero di millimetri per la prossima galassia. Se tali casi sono rilevanti per la tua applicazione dipende da quale sia la tua applicazione. Se stai contando il numero di articoli in un determinato raccoglitore nel tuo magazzino, probabilmente 16 bit sarebbero sufficienti. Se stai compilando statistiche sul numero di persone nel mondo che soddisfano varie condizioni, devi essere in grado di registrare miliardi, quindi avrai bisogno di più di 32 bit, a quel punto presumibilmente andresti a 64 (come pochi computer avere supporto integrato per numeri a 37 bit, ecc.). Se questa è un'applicazione chimica che conta il valore di atomi di talpe, 64 bit non saranno sufficienti.

Tecnicamente, solo perché nessun computer ha oggi 2 ^ 64 byte di memoria non significa necessariamente che un indice di array non possa mai essere più di 2 ^ 64. Esiste un concetto chiamato "array sparse" in cui molti degli elementi dell'array non sono fisicamente memorizzati da nessuna parte, e si presume che tali valori non memorizzati abbiano un valore predefinito come zero o zero. Ma suppongo che se stai scrivendo una funzione per cercare una matrice o un elenco di qualche tipo, e la dimensione del campo che stai usando per tenere l'indice nella matrice è più del doppio dell'indirizzo più grande possibile, quindi controlla l'overflow quando l'aggiunta di due indici non sarebbe strettamente necessaria.

    
risposta data 24.02.2015 - 16:27
fonte
0

È irragionevole supporre che un numero intero a 64 bit possa contenere tutti i numeri. Molte ragioni:

  1. I numeri massimi e minimi a 64 bit sono numeri finiti. Per ogni numero finito esiste un numero finito più grande e più piccolo.

  2. I calcoli con numeri a 128 e 256 bit sono attualmente utilizzati in vari luoghi. Molti processori hanno istruzioni specifiche che operano su numeri interi a 128 bit.

  3. 20 anni fa, un disco da 1 GB era considerato "grande". Oggi un disco da 1 TB è considerato piccolo. 20 anni fa i desktop medi avevano circa 16 MB di RAM. Il mio desktop attuale ha più di 16 GB di RAM. Lo spazio su disco rigido e la RAM sono cresciuti in modo esponenziale nel passato e si prevede che crescano esponenzialmente in futuro. A meno che qualcuno non riesca a trovare una buona ragione per cui dovrebbe smettere di crescere, non ha senso presumere che si fermerà.

risposta data 24.02.2015 - 10:06
fonte

Leggi altre domande sui tag