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

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

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

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

30 голосов | спросил Siqi Lin 24 FebruaryEurope/MoscowbTue, 24 Feb 2015 02:55:34 +0300000000amTue, 24 Feb 2015 02:55:34 +030015 2015, 02:55:34

10 ответов


57

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

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

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

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

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

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

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

ответил user949300 24 FebruaryEurope/MoscowbTue, 24 Feb 2015 04:11:22 +0300000000amTue, 24 Feb 2015 04:11:22 +030015 2015, 04:11:22
19

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

ответил msw 24 FebruaryEurope/MoscowbTue, 24 Feb 2015 19:01:53 +0300000000pmTue, 24 Feb 2015 19:01:53 +030015 2015, 19:01:53
16

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

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

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

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

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

ответил Jerry101 24 FebruaryEurope/MoscowbTue, 24 Feb 2015 08:46:52 +0300000000amTue, 24 Feb 2015 08:46:52 +030015 2015, 08:46:52
9
  

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

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

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

ответил Robert Harvey 24 FebruaryEurope/MoscowbTue, 24 Feb 2015 03:45:24 +0300000000amTue, 24 Feb 2015 03:45:24 +030015 2015, 03:45:24
6

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

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

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

Итак, вы видите, где я собираюсь с этим. Последнее, с которым вы не можете справиться.

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

ответил tcrosley 24 FebruaryEurope/MoscowbTue, 24 Feb 2015 10:58:48 +0300000000amTue, 24 Feb 2015 10:58:48 +030015 2015, 10:58:48
4

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

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

Другими словами, предположим, что существуют некоторые программные environements, где 0xFFFFFFFFxxxxxxxx являются допустимыми диапазонами памяти, которые могут быть возвращены из вызова ---- +: = 2 =:. + ----

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

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

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

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

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

ответил rwong 24 FebruaryEurope/MoscowbTue, 24 Feb 2015 10:18:30 +0300000000amTue, 24 Feb 2015 10:18:30 +030015 2015, 10:18:30
4

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

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

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

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

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

ответил luk32 24 FebruaryEurope/MoscowbTue, 24 Feb 2015 17:22:26 +0300000000pmTue, 24 Feb 2015 17:22:26 +030015 2015, 17:22:26
4

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

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

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

ответил R.. 24 FebruaryEurope/MoscowbTue, 24 Feb 2015 21:25:24 +0300000000pmTue, 24 Feb 2015 21:25:24 +030015 2015, 21:25:24
2

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

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

ответил Jay 24 FebruaryEurope/MoscowbTue, 24 Feb 2015 18:27:38 +0300000000pmTue, 24 Feb 2015 18:27:38 +030015 2015, 18:27:38
0

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

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

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

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

ответил Peter 24 FebruaryEurope/MoscowbTue, 24 Feb 2015 12:06:34 +0300000000pmTue, 24 Feb 2015 12:06:34 +030015 2015, 12:06:34

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132