Разумно ли предположить, что любая физическая величина может быть представлена ​​64-разрядным целым числом без переполнения или переполнения?

31

Исходный алгоритм двоичного поиска в JDK использовал 32-разрядные целые числа и имел ошибку переполнения if (low + high) > INT_MAX( http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html ) ,

Если мы переписали тот же алгоритм двоичного поиска с использованием (подписанных) 64-разрядных целых чисел, можем ли мы предположить, что low + highон никогда не превысит INT64_MAX, поскольку физически невозможно иметь 10 ^ 18 байт памяти?

При использовании (подписанных) 64-битных целых чисел для представления физических величин , разумно ли предполагать, что переполнение не может произойти?

design algorithms Сики Лин
источник
4
Посмотрите на любое физическое явление, связанное с иррациональным числом. Круги и пи например. Числа с плавающей точкой по своей природе рациональны, поэтому вы не можете точно представить их без ошибок.
Томас Эдинг
92
Число атомов на Солнце составляет приблизительно 1,2e57, что соответствует целому числу без знака в 190 бит. Противоречие, 64 бита не могут быть достаточно большими, чтобы представить любую физическую величину.
6
Название вашего вопроса вводит в заблуждение. Вы должны спросить: «Существуют ли количества, для которых можно ожидать, что приложение использует отсортированный массив размером больше 2 ^ 64?»
Док Браун
7
или количество секунд в секундах с тех пор, как вы начали читать этот комментарий.
Джодрелл
4
Было время, когда все думали, что никогда не будет 2 ^ 32 компьютеров, соединенных друг с другом. Вы не хотите, чтобы ваши атомы использовали NAT, не так ли?
Себб

Ответы:

58

Короткий ответ: нет. Однако для некоторых приложений ваше предположение может быть правильным.

Предполагая, что подписанное целое число 2 ^ 63 с запятыми, добавленными для некоторой ясности, = 9,223,372,036,854,775,808. Так что примерно 9 * 10 ^ 18. 10 ^ 18 это «Exa».

Википедия говорит: «По состоянию на 2013 год, Всемирная паутина, по оценкам, достигла 4 зетабайтов. [12]», что составляет 4000 экзабайт. Таким образом, WWW примерно в 400 раз больше, чем 2 ^ 63 байта.

Следовательно, существует по крайней мере одна физическая величина, которая намного больше 64-разрядного целого числа со знаком (или без знака). Предполагая, что ваши единицы являются байтами . Если бы ваши единицы измерения были намного больше, например, GigaBytes, то все было бы в порядке, но ваша точность измерения была бы низкой.

Для другого примера рассмотрим далекие галактики. Галактика Андромеды на самом деле одна из ближайших, и она находится на расстоянии 2,5 * 10 ^ 6 световых лет. Если ваши единицы были милями , это было бы 14,5 * 10 ^ 18, больше, чем 64-разрядное целое число со знаком. Теперь, очевидно, это зависит от единиц измерения, которые вы используете для своих измерений, но некоторые галактики намного дальше, чем Андромеда. ( Самый дальний из известных - 13 * 10 ^ 9 LY ). В зависимости от точности, которую вы хотите для своего измерения, он может переполнить 64-битное целое число.

( Добавлено ) Да, мили - это паршивая единица астрономического расстояния. Более нормальной единицей может быть астрономическая единица , примерно 93 миллиона миль. Используя эту единицу измерения, самая дальняя известная галактика составляет примерно 10 ^ 15 а.е. (если моя математика верна), что соответствует 64-битному целому. Однако, если вы хотите измерить расстояние до Луны, до ближайших орбитальных спутников, эта единица слишком велика.

Еще один пример из электроники: Фарад (F), единица измерения емкости . Большие конденсаторы до 5 кФ. И это число, вероятно, со временем будет увеличиваться по мере улучшения гибридных автомобилей, «умных сетей» и т. Д. Однажды можно измерить емкость всего 10 ^ -18 F. Таким образом, общий диапазон "реальной" емкости, который мы можем измерить сегодня, составляет 5 * 10 ^ 21, больше, чем 64-битное целое число.

user949300
источник
3
Все это верно, но с практической точки зрения мы можем поставить под сомнение точку измерения расстояния до галактики Андромеды от Млечного пути в милях (где именно это точка отсчета?) Или всего WWW в байтах (с такой точностью, он меняется каждую миллисекунду)
Дживан,
45
@Jivan С практической точки зрения я не вижу причин, по которым вам когда-либо понадобится использовать более 640 КБ памяти. Конечно, это больше, чем вам когда-либо нужно.
АрЦ
2
Еще один недостаток измерения астрономических расстояний в милях: вы можете быть сбиты кошкой.
Виллихам Тотланд
2
@ Дживан Хороший вопрос. Это напоминает мне о разглагольствованиях Ричарда Фейнмана о глупости суммирования температуры группы звезд. Я понимаю, почему вы хотите среднее, минимальное, максимальное, но сумма? Что это за физическое значение?
piojo
6
@piojo - по общему признанию сумма полезна при вычислении среднего значения.
Скотт Уитлок
20

Вам даже не нужно быть космическим, когда комбинаторика задействована. Есть 2 95 возможных сделок в игре в бридж, и это небольшая сложность.

MSW
источник
Можно задаться вопросом, считается ли это «физической величиной».
Пол Дрэйпер
2
С другой стороны, комбинаторика, связанная с химией или математикой, квалифицируется как «физическая».
Руон
@PaulDraper, если у вас достаточно колод карт, чтобы разложить по земле все эти сделки, это будет физически. Тогда у вас будет более 2 ^ 95 карт .
Брэд
1
@ Брэд, я думаю, что ОП просит количество, которое «существует» (хорошо, существование - нечеткая концепция). 2 ^ 95 карт, которые удовлетворяют математической концепции, не существуют (назовите Гиннеса, если они есть). Трудно сказать, что «считается», а что нет. Этот ответ просто не удовлетворяет моему мягкому представлению о физической величине.
Пол Дрейпер
17

Самая важная физическая величина для вашего вопроса - это оперативная память компьютера .

Windows Server 2012 поддерживает до 4 ТБ физической памяти. Это 2 42 байта. Если объем оперативной памяти будет удваиваться примерно каждый год, то всего через 17 лет Windows Server 2032 будет поддерживать 2 62 байта физической памяти, и в это время вы low + highдостигнете 2 63 - 2 и поцелуете максимальное 64-разрядное целое число со знаком.

Я надеюсь, что ни одна критическая по безопасности система не выйдет из строя, так как предположим, что 64-битных всегда будет достаточно.

Для более общего использования наиболее важной физической величиной является адресное пространство памяти . (Полезно иметь гораздо большее адресное пространство, чем физическая память, например, чтобы поместить много стеков в память, все с возможностью расширения.) Современные реализации x86-64 поддерживают 48-битные виртуальные адреса, поэтому у нас есть только 14 лет, чтобы эти процессоры достигли 2 62 байта ограничения адресного пространства.

И еще есть распределенная разделяемая память «где (физически разделенные) памяти могут быть адресованы как одно (логически разделяемое) адресное пространство».

Jerry101
источник
4
+1 Ваш ответ почти точный, за исключением того, что некоторые типы современного программного обеспечения уже встречают адреса памяти в диапазоне 0xFFFFFFFFxxxxxxxx(т. Е. Более высокая половина ), например, операционная система или драйверы устройств.
Rwong
2
@SiqiLin, вероятно, не так сильно, как персональные компьютеры. Однако распределенная общая память или DGAS (упомянутые в статье) реальны; Суперкомпьютеры работают в этом стиле в течение многих лет, и вполне возможно, что это может стать нормой для многонациональной инфраструктуры облачных вычислений. Очевидно, что типичный программный код, написанный типичным программистом, не будет работать в такой среде - в необычных средах запускается необычное (то есть инфраструктурное) программное обеспечение. Но часть читателей P.SE может просто попасть на такой карьерный путь; на всякий случай.
Rwong
1
@ Джошуа: С современной технологией (32 ГБ DDR4) для света будет 7 м или 23 нс, что, по-видимому, соответствует современным задержкам CAS. Если вы подтолкнете его к экстремальному принципу Ландауэра, с плотностью кремния вы получите 31 нм или 10 ^ -16 секунд для физического предела. Это не кажется слишком сумасшедшим ... ну, может быть, немного.
Чарльз
3
@ Джошуа Это технологический предел, а не физический. (Например, проблема в том, что мы не знаем, как это сделать практически, а не в том, что какой-то физический закон запрещает это.) Поэтому, хотя и актуально на этой неделе, оно может измениться в любой момент с новым прорывом. Приблизительно 60 лет назад люди бы сделали комментарии, очень похожие на ваши, около 50 килобайт памяти считали ОЗУ на том основании, что проволочные катушки с ручным заводом, которые затем использовались как части ядер памяти, могли не только стать настолько маленькими и все еще функция, но требуется пространство между ними, чтобы избежать электромагнитных помех.
Мэтью Наджмон
2
Я помню, когда 24 бит адресного пространства (16 мегабайт) было больше, чем кто-либо когда-либо нуждался бы - или мог себе позволить. :-)
Боб Джарвис - Восстановить Монику
10

Разумно ли предположить, что любая физическая величина может быть представлена ​​64-разрядным целым числом без переполнения или переполнения?

Не совсем. Есть много чисел, которые как больше, так и меньше, поэтому у нас есть числа с плавающей запятой. Числа с плавающей точкой компенсируют меньшую точность для лучшего диапазона.

В приведенном вами конкретном примере крайне маловероятно, что вам когда-нибудь понадобится число, которое больше этого. 64 бита соответствуют примерно 18 квинтиллионным элементам. Но никогда не говори никогда.

Роберт Харви
источник
7

Ваше предположение не будет обрабатывать физические величины, которые могут быть представлены только числами с плавающей запятой. И даже если вы решили масштабировать все числа, скажем, умножив все числа на 10000 (таким образом, значения все еще являются целыми числами, но могут быть представлены в десятитысячных долях), эта схема все еще не работает для чисел, очень близких к нулю, например, массы электрона (9,1094 * 10⎻⎻¹ кг).

Это очень реальная (и чрезвычайно малая) физическая величина , вот еще некоторые, с которыми у вас будут проблемы. И если вы утверждаете, что это не реальная физическая величина (даже если она в килограммах), подумайте:

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

Итак, вы видите, куда я иду с этим. Последний, с которым ты не справишься.

Конечно, у вас может быть специальное поле в числе, чтобы масштабировать целую часть вверх или вниз с помощью переменного множителя; ну и дела, вы только что изобрели с плавающей точкой.

tcrosley
источник
1
Но вы можете назначить минимальное физическое значение (IIRC, для массы это была масса, эквивалентная 1 электрон-вольт). Например, вы можете измерить длину юниверса, используя единицы длины Планка с (IIRC) 200 цифрами. Вы можете мысленно говорить о 1/10 длины Планка, но физически это не имеет смысла.
SJuan76
Разве вы не имеете в виду делить на 10000? Умножение на 10000 сделало бы предположение о том, что средство открывания потока с большей вероятностью потерпит неудачу. Также возможно мое устройство не отображает массу электрона правильно, но это должно быть 10 ^ -31
Майк
Я имею в виду умножение на 10000. Если вы хотите сохранить 1.0001 как целое число, вам нужно умножить его на 10000, прежде чем сохранять его как 10001. Я использовал символы верхнего индекса для -31, возможно, они отображаются некорректно во всех браузерах , Хорошо смотрится в Firefox.
tcrosley
@ SJuan76 Есть что-то, что называется будущим. В 1850 году мы могли говорить о единице 10 ^ -20 метров (намного меньше, чем атом, но все же намного больше, чем длина Планка), но физически это не имело смысла. Тогда люди выяснили внутреннюю структуру атома. Конечно, кварки выглядят фундаментально, но все, что мы можем на самом деле сказать, это (а) они действуют так, как мы ожидаем, что фундаментальные частицы будут вести себя, и (б) мы еще не нашли следующую черепаху. В 1850 году мы могли бы сказать то же самое об атомах. Если мы найдем следующую черепаху, единицы 1/10 Планка станут весьма полезными.
Мэтью Наджмон,
Это распространенное заблуждение, что пространство или время квантуется в единицах Планка! Вы не можете представить вселенную с помощью 4-мерного массива, по крайней мере, в настоящее время теории ... Так доли длины Планка имеют физический смысл (но результаты , которые выходят из общей теории относительности и / или QM начинают взрывать или противореча друг другу).
yatima2975
5

Сначала я бы ответил на вопрос, какие физические значения могут / должны быть представлены целым числом?

Целое число представляет собой представление натурального числа (и различий между ними) в компьютерной системе, поэтому применять его к чему-либо другому неправильно. Таким образом, использование расстояний или других величин, принадлежащих непрерывной области, не является аргументом. Для таких величин существуют действительные числовые представления. И вы всегда можете выбрать произвольно большой блок и подобрать любое значение с заданной точностью.

Итак, каковы физические значения, которые являются натуральными числами и могут ли они переполнять 64-битное целое число?

Я могу думать о двух. Количество физических объектов (таких как атомы) и энергетические уровни, на которых может находиться квантовая система. Это две вещи, которые являются строго целочисленными. Теперь я знаю, что вы можете разделить атом, но он все равно дает целое число, и вы не можете разделить его бесконечно. Оба из них могут легко превзойти 64-битный диапазон целого числа без знака . Количество атомов больше, и один атом может находиться в более чем одном энергетическом состоянии.

Если информация является физической или нет, очень спорно. Я бы сказал, что это не так. Поэтому я бы не сказал, что количество информации - это физическая вещь. Так что не объем оперативной памяти или что-то в этом роде. Если вы позволите это, то число атомов легко превосходит это число, потому что вам нужно более одного атома для хранения одного бита с помощью современной технологии.

luk32
источник
Множество N натуральных чисел включает только неотрицательные целые числа. Я знаю, что вы имели в виду, но у «натурального числа» есть определенное математическое определение, несовместимое с тем, как вы его используете.
Я не совсем уверен. Целочисленные типы представляют собой натуральные числа (в определенном диапазоне, что подразумевается). Разве это не правда? Я думаю, вы предположили, что я подразумевал равенство между наборами. Это не так, любое натуральное число может быть представлено целым числом. Обратите внимание, что я также сказал различия между ними. Я не чувствовал, что вход в подписанный / неподписанный был необходим. Опаленный тип необходим только тогда, когда вы имеете дело с различиями.
luk32
В то время как физичность хранимой информации является дискуссионной, и вопрос для философов больше, чем для физиков, физичность механизмов, с помощью которых она хранится, является вполне определенной. Таким образом, в то время как применимость к числу бит информации сомнительна, число бит на сумму чипов RAM не является.
Мэтью Наджмон,
@ MatthewNajmon Конечно, я согласен, поэтому я оставил последнее предложение. Число битов чипа ОЗУ в течение некоторого времени будет меньше количества атомов, поэтому вы можете использовать последний. Другими словами, зачем использовать количество бит, когда вы можете использовать количество атомов одного и того же чипа ОЗУ? В настоящее время часть информации представлена ​​состоянием, в котором находится физическая система, поэтому вы можете хранить более одного бита на атом, но в настоящее время это далеко от применения, и я до сих пор не вижу, как оно может быть больше, чем число квантовые состояния такой системы. Но я полностью согласен с вашей предпосылкой.
luk32
4

В дополнение к ответу Jerry101 я хотел бы предложить этот очень простой и практичный тест на правильность:

Предположим, вы распределяете некоторую память через malloc64-битную ОС. Давайте предположим, что распределитель памяти решает вернуть вам действительный блок памяти того размера, который вы запрашивали, но в котором установлен 63-й бит.

Другими словами, давайте предположим, что существуют некоторые программные среды, в которых 0xFFFFFFFFxxxxxxxxдопустимые диапазоны памяти могут быть возвращены из вызова malloc.

Вопрос в том, будет ли ваш код работать так, как задумано?

Когда аналогичная ситуация возникает с 32-разрядными операционными системами, некоторые программы работают неправильно, если им присваиваются адреса памяти «в верхней половине». Первоначально считалось, что такие адреса памяти доступны только для привилегированного кода (операционные системы, драйверы устройств и периферийное оборудование), но из-за проблем с 32-разрядным адресным пространством поставщики ОС решили сделать часть этого зарезервированного пространства доступной для приложения, которые просят об этом.

К счастью, такая ситуация вряд ли случится с 64-битными программами какое-то время, по крайней мере, через десять лет.

Когда такая ситуация, наконец, происходит, это означает, что к тому времени 128-разрядные адресуемые процессоры и операционные системы стали бы мейнстримом и что они могли бы обеспечить «среду 64-разрядной эмуляции», позволяющую этим «устаревшим приложениям» работать. по предположениям, аналогичным современным 64-разрядным операционным системам.

Наконец, обратите внимание, что это обсуждение сосредоточено только на адресах памяти. Аналогичную проблему с метками времени следует принимать с большей осторожностью, поскольку определенные форматы меток времени выделяют много битов точности микросекундам и поэтому оставляют меньше битов, доступных для представления времени в будущем. Эти проблемы обобщены в статье Википедии о проблеме 2038 года .

rwong
источник
4

Это вопрос, который вы должны задать в каждом конкретном случае. Вы не должны использовать общее предположение о том, что 64-битной арифметике не будет переполнение, потому что даже тогда , когда правильные величины будут в гораздо меньшем диапазоне, злонамеренный источник данных может в конечном итоге дать вам необоснованные количества , которые могли бы переполнение, и это лучше , чтобы быть готов к этой ситуации, чем быть пораженным ею неожиданно.

В некоторых случаях имеет смысл написать код, который зависит от не переполнения 64-битных чисел. Основной класс примера, который я знаю, это счетчики, где счетчик увеличивается каждый раз, когда его используют. Даже со скоростью одного приращения в наносекунду (не практично) переполнение заняло бы больше столетия.

Обратите внимание, что хотя на первый взгляд может показаться, что «всегда неправильно» полагаться на «время до отказа» для правильности системы, мы делаем это все время с аутентификацией / входом в систему. При наличии достаточного количества времени (для перебора) любая такая система (основанная на паролях, закрытых ключах, токенах сеансов и т. Д.) Не работает.

Р..
источник
2

МОЖНО ли физическое количество не вписаться в 64 бита? Конечно. Другие указали подсчет количества атомов на Солнце или миллиметров до следующей галактики. Относятся ли такие случаи к вашей заявке, зависит от того, какая ваша заявка. Если вы подсчитываете количество предметов в любой данной корзине на вашем складе, 16 бит, скорее всего, будет достаточно. Если вы собираете статистику о количестве людей в мире, удовлетворяющих различным условиям, вам необходимо иметь возможность записывать миллиарды, поэтому вам потребуется более 32 бит, и в этот момент вы, вероятно, перейдете на 64 (так мало компьютеров). иметь встроенную поддержку 37-битных чисел и т. д.). Если это приложение для химии, которое рассчитывает количество атомов в молях, 64 битов будет недостаточно.

Технически, просто потому, что ни один компьютер сегодня не имеет 2 ^ 64 байта памяти, не обязательно означает, что индекс массива никогда не может быть больше чем 2 ^ 64. Существует концепция, называемая «разреженный массив», в которой многие элементы массива физически нигде не хранятся, и предполагается, что такие не сохраненные значения имеют некоторое значение по умолчанию, например, ноль или ноль. Но я предполагаю, что если вы пишете функцию для поиска в массиве или списке какого-либо вида, а размер поля, которое вы используете для хранения индекса в массиве, более чем вдвое превышает максимально возможный адрес, тогда выполняется проверка на переполнение, когда добавление двух индексов не будет строго необходимым.

сойка
источник
Хороший вопрос о разреженных массивах. Кроме того, даже с массивом, который полностью заполнен, все еще вполне возможно, хотя и довольно медленно, а в некоторых случаях совершенно необходимо, работать с массивом, слишком большим, чтобы вместить весь массив в ОЗУ одновременно. Это можно сделать, просто сохранив все это в более медленной, но гораздо большей среде, например, на жестком диске, а затем вытянув в ОЗУ только те элементы, с которыми вы работаете в данный момент. Даже маленький жесткий диск достаточно большой, чтобы вместить массив намного больше, чем тот, на который рассчитывает ОП.
Мэтью Наджмон,
0

Неразумно предполагать, что 64-разрядное целое число может содержать все числа. Несколько причин:

  1. Максимальное и минимальное 64-битное целое число являются конечными числами. Для каждого конечного числа существует большее и меньшее конечное число.

  2. Расчеты с 128-битными и 256-битными числами в настоящее время используются в разных местах. Многие процессоры имеют специальные инструкции, которые работают с 128-битными целыми числами.

  3. 20 лет назад диск объемом 1 ГБ считался «большим». Сегодня диск объемом 1 ТБ считается маленьким. 20 лет назад средние рабочие столы имели около 16 МБ ОЗУ. Мой текущий рабочий стол имеет более 16 ГБ ОЗУ. В прошлом пространство на жестком диске и объем оперативной памяти росли в геометрической прогрессии, а в будущем прогнозируется их экспоненциальный рост. Если кто-то не может придумать очень вескую причину, почему он должен прекратить расти, не имеет смысла предполагать, что это прекратится.

Питер
источник