Est-il raisonnable de supposer que n'importe quelle quantité physique peut être représentée par un entier 64 bits sans débordement ni débordement?

L'algorithme de recherche binaire d'origine dans le JDK utilisait des entiers 32 bits et avait un bogue de débordement si (low + high) > INT_MAX( http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html ) .

Si nous réécrivons le même algorithme de recherche binaire à l'aide d'entiers 64 bits (signés), pouvons-nous supposer qu'il low + highne dépassera jamais INT64_MAX car il est physiquement impossible d'avoir 10 ^ 18 octets de mémoire?

Lorsque vous utilisez des entiers 64 bits (signés) pour représenter des quantités physiques , est-il raisonnable de supposer que le dépassement et le dépassement ne peuvent pas se produire?

La réponse courte est non. Cependant, pour certaines applications, votre hypothèse peut être correcte.

En supposant un entier signé, 2 ^ 63, avec des virgules ajoutées pour plus de clarté, = 9,223,372,036,854,775,808. C'est donc à peu près 9 * 10 ^ 18. 10 ^ 18 est un "Exa".

Wikipédia dit: "En 2013, le World Wide Web aurait atteint 4 zettaoctets. [12]", soit 4 000 exaoctets. Par conséquent, le WWW est environ 400 fois plus grand que 2 ^ 63 octets.

Par conséquent, il existe au moins une quantité physique qui est beaucoup plus grande qu'un entier 64 bits signé (ou non signé). En supposant que vos unités sont des octets . Si vos unités étaient quelque chose de beaucoup plus grand, comme GigaBytes, alors vous seriez d'accord, mais votre précision de mesure serait faible.

Pour un autre exemple, considérons les galaxies lointaines. La galaxie d'Andromède est en fait l'une des plus proches, et elle se trouve à 2,5 * 10 ^ 6 années-lumière. Si vos unités étaient des miles , ce serait 14,5 * 10 ^ 18, plus qu'un entier signé de 64 bits. Maintenant, cela dépend évidemment des unités que vous utilisez pour vos mesures, mais certaines galaxies sont bien plus éloignées qu'Andromède. ( Le plus connu est à 13 * 10 ^ 9 LY de distance. ) Selon la précision que vous souhaitez pour votre mesure, elle peut déborder d'un entier de 64 bits.

( Ajouté ) Oui, les miles sont une unité minable pour la distance astronomique. Une unité plus normale pourrait être une unité astronomique , à environ 150 millions de kilomètres. En utilisant cette unité de mesure, la galaxie la plus éloignée connue est d'environ 10 ^ 15 AU (si mes calculs sont exacts), ce qui correspondrait à un int de 64 bits. Cependant, si vous souhaitez également mesurer la distance à la Lune, aux satellites en orbite à proximité, cette unité est trop grande.

Un autre exemple de l'électronique: le Farad (F), une unité de capacité . Les grands condensateurs vont jusqu'à 5kF. Et ce nombre augmentera probablement avec le temps à mesure que les voitures hybrides, les «réseaux intelligents», etc. s'améliorent. Une fois peut mesurer une capacité aussi petite que 10 ^ -18 F. Ainsi, la plage globale de capacité "réelle" que nous pouvons mesurer aujourd'hui est de 5 * 10 ^ 21, plus grande qu'un entier de 64 bits.

Vous n'avez même pas besoin de devenir cosmique lorsque la combinatoire est impliquée. Il y a 2 ^ 95 offres possibles dans un jeu de bridge et c'est du petit côté de la complexité.

La quantité physique la plus pertinente pour votre question est la RAM de l'ordinateur .

Windows Server 2012 prend en charge jusqu'à 4 To de mémoire physique. C'est 2 ⁴² octets. Si les capacités de RAM continuent de doubler chaque année, alors dans seulement 17 ans, "Windows Server 2032" prendra en charge 2 ⁶² octets de mémoire physique, date à laquelle vous low + highatteindrez 2 ⁶³ - 2 et embrasserez l'entier 64 bits maximum signé.

J'espère qu'aucun système critique pour la sécurité ne tombe en panne, en supposant que 64 bits seront toujours suffisants.

Pour une utilisation un peu plus générale, la quantité physique la plus pertinente est l' espace d'adressage mémoire . (Il est utile d'avoir un espace d'adressage beaucoup plus grand que la mémoire physique, par exemple pour mettre de nombreuses piles en mémoire, toutes avec de la place pour croître.) Les implémentations actuelles x86-64 prennent en charge les adresses virtuelles 48 bits, nous n'avons donc que 14 ans avant que ces CPU atteignent la limite d'espace d'adressage de 2 ⁶² octets.

Et puis il y a la mémoire partagée distribuée "où les mémoires (physiquement séparées) peuvent être adressées comme un seul espace d'adressage (logiquement partagé)".

Est-il raisonnable de supposer que n'importe quelle quantité physique peut être représentée par un entier 64 bits sans débordement ni débordement?

Pas exactement. Il y a beaucoup de nombres qui sont à la fois plus grands et plus petits que cela, c'est pourquoi nous avons des nombres à virgule flottante. Les nombres à virgule flottante compensent une moindre précision pour une meilleure portée.

Dans l'exemple spécifique que vous avez cité, il est très peu probable que vous ayez besoin d'un nombre supérieur à cela. 64 bits correspondent à environ 18 quintillions d'éléments. Mais ne dis jamais jamais.

Votre hypothèse ne gérera pas les quantités physiques qui ne peuvent être représentées que par des nombres à virgule flottante. Et même si vous avez décidé de mettre à l'échelle tous les nombres, par exemple en multipliant tous les nombres par 10000 (de sorte que les valeurs sont toujours des entiers mais peuvent être représentées en dix millièmes), ce schéma échoue toujours pour les nombres très proches de zéro, par exemple la masse électronique (9,1094 * 10⎻³¹ kg).

C'est une quantité physique très réelle (et extrêmement petite) , voici encore plus avec laquelle vous aurez des problèmes. Et si vous soutenez que ce n'est pas une vraie quantité physique (même si elle est en kg), considérez:

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

Vous voyez donc où je veux en venir. Le dernier que vous ne pouvez pas gérer non plus.

Bien sûr, vous pouvez avoir un champ spécial dans le nombre pour mettre à l'échelle une partie entière vers le haut ou vers le bas par un multiplicateur variable; gee maintenant vous venez d'inventer la virgule flottante.

Je répondrais d'abord à la question de savoir quelles valeurs physiques peuvent / devraient être représentées par un nombre entier?

Un entier est une représentation d'un nombre naturel (et des différences entre eux) dans un système informatique, donc l'appliquer à autre chose est faux. Ainsi, invoquer des distances ou d'autres quantités appartenant au domaine continu n'est pas un argument. Pour de telles quantités, il existe des représentations de nombres réels. Et vous pouvez toujours choisir une unité arbitrairement grande et adapter n'importe quelle valeur avec une précision donnée.

Alors, quelles sont les valeurs physiques qui sont des nombres naturels et peuvent-elles déborder d'un entier 64 bits?

Je peux penser à deux. Nombre d'objets physiques (comme les atomes) et niveaux d'énergie dans lesquels un système quantique peut se trouver. Ce sont deux choses strictement entières. Maintenant, je sais que vous pouvez diviser un atome, mais il produit toujours une quantité entière et vous ne pouvez pas le diviser indéfiniment. Les deux peuvent facilement dépasser la plage 64 bits d'entier non signé . Le nombre d'atomes est plus élevé et un atome peut être dans plus d'un état énergétique.

Que l'information soit physique ou non, est très discutable. Je dirais que non. Par conséquent, je ne dirais pas que la quantité d'informations est une chose physique. Ce n'est donc pas la quantité de RAM ou quelque chose comme ça. Si vous le permettez, le nombre d'atomes dépasse facilement ce nombre, car vous avez besoin de plus d'un atome pour stocker un bit avec la technologie d'aujourd'hui.

En plus de la réponse de Jerry101, je voudrais offrir ce test de correction très simple et pratique:

Supposons que vous allouiez de la mémoire via malloc, dans un système d'exploitation 64 bits. Supposons que l'allocateur de mémoire décide de vous renvoyer un bloc de mémoire valide, de la taille que vous avez demandée, mais où le 63e bit est défini.

En d'autres termes, supposons qu'il existe des environnements de programmation où se 0xFFFFFFFFxxxxxxxxtrouvent des plages de mémoire légitimes qui pourraient être renvoyées d'un appel à malloc.

La question est, votre code fonctionnera-t-il toujours comme prévu?

Lorsque la situation analogue se produit pour les systèmes d'exploitation 32 bits, certains logiciels ne fonctionnent pas correctement s'ils reçoivent des adresses mémoire "dans la moitié supérieure". À l'origine, ces adresses mémoire étaient censées être uniquement disponibles pour le code privilégié (systèmes d'exploitation, pilotes de périphériques et matériel périphérique), mais en raison de la pénurie d'espace d'adressage 32 bits, les fournisseurs de systèmes d'exploitation ont décidé de mettre une partie de cet espace réservé à la disposition de les applications qui le demandent.

Heureusement, cette situation est peu susceptible de se produire pour les programmes 64 bits pendant un certain temps, du moins pas dans une décennie.

Lorsque cette situation se produit enfin, cela signifie que les processeurs et systèmes d'exploitation adressables à 128 bits seraient devenus courants à ce moment-là, et qu'ils seraient en mesure de fournir un "environnement d'émulation 64 bits" pour permettre à ces "applications héritées" de fonctionner. sous des hypothèses similaires aux systèmes d'exploitation 64 bits d'aujourd'hui.

Enfin, notez que cette discussion se concentre uniquement sur les adresses mémoire. Un problème similaire avec les horodatages doit être pris avec plus de précaution, car certains formats d'horodatage allouent beaucoup de bits de précision aux microsecondes et laisse donc moins de bits disponibles pour représenter le temps à l'avenir. Ces problèmes sont résumés dans l'article de Wikipedia sur le problème de l'an 2038 .

C'est une question que vous devez vous poser au cas par cas. Vous ne devriez pas utiliser une hypothèse générale selon laquelle l'arithmétique 64 bits ne débordera pas, car même lorsque les quantités correctes seront dans une plage beaucoup plus petite, une source de données malveillante pourrait finir par vous donner des quantités déraisonnables qui pourraient déborder, et il vaut mieux être préparé à cette situation que d'être touché par elle de façon inattendue.

Il y a des cas où il est logique d'écrire du code qui dépend du non-débordement des nombres 64 bits. La principale classe d'exemples que je connais est celle des compteurs, où le compteur est incrémenté chaque fois qu'il est utilisé. Même à un rythme d'un incrément par nanoseconde (ce qui n'est pas pratique), il faudrait plus d'un siècle pour déborder.

Notez que même si au premier abord il peut sembler "toujours faux en principe" de s'appuyer sur le "temps jusqu'à l'échec" pour l'exactitude d'un système, nous le faisons tout le temps avec authentification / connexion. Avec suffisamment de temps (pour le forçage brutal), un tel système (qu'il soit basé sur des mots de passe, des clés privées, des jetons de session, etc.) est cassé.

Est-il POSSIBLE qu'une quantité physique ne tienne pas en 64 bits? Bien sûr. D'autres ont souligné le comptage du nombre d'atomes dans le soleil ou du nombre de millimètres jusqu'à la prochaine galaxie. La pertinence de tels cas pour votre application dépend de votre application. Si vous comptez le nombre d'articles dans un bac donné dans votre entrepôt, 16 bits seraient probablement suffisants. Si vous compilez des statistiques sur le nombre de personnes dans le monde remplissant diverses conditions, vous devez être en mesure d'enregistrer des milliards, vous aurez donc besoin de plus de 32 bits, auquel cas vous iriez probablement à 64 (comme peu d'ordinateurs ont un support intégré pour les nombres de 37 bits, etc.). S'il s'agit d'une application de chimie qui compte des moles d'atomes, 64 bits ne seront pas suffisants.

Techniquement, ce n'est pas parce qu'un ordinateur aujourd'hui a 2 ^ 64 octets de mémoire que l'index d'un tableau ne peut jamais dépasser 2 ^ 64. Il existe un concept appelé «tableau clairsemé» dans lequel de nombreux éléments du tableau ne sont physiquement stockés nulle part, et ces valeurs non stockées sont supposées avoir une valeur par défaut comme null ou zero. Mais je suppose que si vous écrivez une fonction pour rechercher un tableau ou une liste quelconque, et que la taille du champ que vous utilisez pour contenir l'index dans le tableau est plus du double de la plus grande adresse possible, puis vérifiez le débordement lorsque l'ajout de deux index ne serait pas strictement nécessaire.

Il est déraisonnable de supposer qu'un entier 64 bits peut contenir tous les nombres. Plusieurs raisons:

1. Les entiers max et min 64 bits sont des nombres finis. Pour chaque nombre fini, un nombre fini plus grand et plus petit existe.

2. Des calculs avec des nombres de 128 bits et 256 bits sont actuellement utilisés à divers endroits. De nombreux processeurs ont des instructions spécifiques qui fonctionnent sur des entiers de 128 bits.

3. Il y a 20 ans, un disque de 1 Go était considéré comme "grand". Aujourd'hui, un disque de 1 To est considéré comme petit. Il y a 20 ans, les ordinateurs de bureau moyens avaient environ 16 Mo de RAM. Mon bureau actuel a plus de 16 Go de RAM. L'espace disque dur et la RAM ont connu une croissance exponentielle dans le passé et devraient croître de façon exponentielle à l'avenir. À moins que quelqu'un ne trouve une très bonne raison pour laquelle cela devrait cesser de croître, il n'est pas logique de supposer que cela s'arrêtera.