Почему случайные числа, загруженные из памяти, часто бывают очень большими?

Иногда во время разработки, например. В коде C вы можете случайно проиндексировать массив за пределами его последнего элемента, что приведет к чтению по существу случайного фрагмента памяти. Я много работаю с массивами double и заметил, что когда это происходит, double, создаваемое из случайной памяти, часто бывает очень большим, например, больше, чем 1e+300. Интересно, почему это так.

Если бы 64 бита, используемые для интерпретации double, были действительно случайными, я бы ожидал, что показатель степени double будет равномерно распределен от 0 до 308 (игнорируя знак степени) из-за того, как числа с плавающей запятой расположены в памяти используя научную (экспоненциальную) запись. Конечно, значения случайно выбранных битов в памяти сами по себе не распределяются случайным образом, а соответствуют некоторому значимому состоянию любого процесса, установившего эти значения.

Чтобы исследовать этот эффект, я написал следующий скрипт Python 3, который отображает распределение действительно случайно сгенерированных doubles и doubles, взятых из случайной, но неиспользуемой памяти:

import random, struct
import numpy as np
import matplotlib.pyplot as plt

N = 10000

def random_floats(N=1):
    return np.array(struct.unpack('d'*N, bytes(random.randrange(256) for _ in range(8*N))))

def exp_hist(a, label=None):
    a = a[~np.isnan(a)]
    a = a[~np.isinf(a)]
    a = a[a != 0]
    if len(a) == 0:
        print('Zeros only!')
        return
    a = np.abs(np.log10(np.abs(a)))
    plt.hist(a, range=(0, 350), density=True, alpha=0.8, label=label)

# Floats generated from uniformly random bits
a = random_floats(N)
exp_hist(a, 'random')

# Floats generated from memory content
a = np.empty(N)
exp_hist(a, 'memory')

plt.xlabel('exponent')
plt.legend()
plt.savefig('plot.png')

Типичный результат запуска этого скрипта показан ниже:

Показатели действительно случайно сгенерированных doubles действительно равномерно распределены.

Показатели doubles, интерпретированные из содержимого памяти, либо очень малы, либо очень велики. На самом деле большая часть неиспользуемой памяти обнуляется, что приводит к большому количеству значений 0, что имеет смысл. Однако, как я часто сталкиваюсь с доступом к памяти без возврата, также появляется много значений около 1e+300.

Я хотел бы получить объяснение этого большого количества чрезвычайно больших doubles.

Примечание по запуску скрипта

Если вы хотите попробовать сценарий самостоятельно, имейте в виду, что вам, возможно, придется запустить его несколько раз, чтобы появилось что-нибудь интересное. Может случиться так, что каждое отдельное число, считанное из содержимого памяти, будет 0, и в этом случае он сообщит вам об этом. Если это происходит неоднократно, попробуйте уменьшить N (количество используемых doubles).


person jmd_dk    schedule 11.12.2019    source источник
comment
Под «случайным образом» вы на самом деле подразумеваете равномерно. Равномерное (случайное) распределение — это распределение, в котором каждый элемент имеет равную вероятность появления (или, для непрерывного распределения, каждый интервал имеет вероятность появления, пропорциональную размеру интервала). Распределения, в которых разные элементы имеют разные вероятности, по-прежнему случайны, просто неравномерны.   -  person Eric Postpischil    schedule 11.12.2019
comment
Макеты памяти имеют тенденцию группировать вещи в адресном пространстве вокруг 0, 0x7fff…, 0x8000… и 0xffff…. Таким образом, наличие указателей со значениями около 0x7ff… объясняет большие значения double.   -  person Eric Postpischil    schedule 11.12.2019
comment
@EricPostpischil В вопросе конкретно используется термин равномерно случайный, когда это предполагаемое значение. Почему макеты памяти имеют тенденцию группировать вещи вокруг этих значений?   -  person jmd_dk    schedule 11.12.2019
comment
«Если бы… были действительно случайными», должно быть «действительно случайными с равномерным распределением». «действительно случайно сгенерированный» должен быть «действительно случайно сгенерирован с равномерным распределением».   -  person Eric Postpischil    schedule 11.12.2019
comment
Макеты памяти сгруппированы вокруг этих значений, потому что давным-давно люди сидели и думали: «Куда мне положить вещи?» Некоторые из них начинали с 0, затем помещали следующую вещь в 1, затем 2 и так далее, или в 4, 8, 12 или любое другое кратное число, которое им было нужно. Потом кто-то сказал, хорошо, мы поместили туда наш код и некоторые наши данные. Эй, у меня есть идея, давайте сделаем стек. Куда мы должны его положить? Поскольку «низ» (0) уже использовался, возможно, они начали с вершины своего адресного пространства (тогда, возможно, 0xffff) и работали вниз.   -  person Eric Postpischil    schedule 11.12.2019
comment
В другом случае кто-то решил, что было бы полезно разделить адресное пространство на область, в которой пользователь может размещать данные, и область, в которой операционная система размещает информацию, и они решили, что все, что начинается с бита 0, предназначено для пользователя и все, что начинается с бита 1, предназначено для операционной системы. Затем пользователь помещает элементы в 0 и выше (возможно, пропуская первую страницу, чтобы зарезервировать ее для ловушек нулевого указателя) и помещает свой стек в 0x7ffff… и вниз, и операционная система аналогичным образом помещает некоторые элементы в 0x8000… и вверх, а другие элементы в 0xffff… и вниз.   -  person Eric Postpischil    schedule 11.12.2019
comment
По сути, пространство памяти дробится из-за того, что люди делят его так и сяк.   -  person Eric Postpischil    schedule 11.12.2019
comment
Не могли бы вы объяснить строку a = np.abs(np.log10(np.abs(a)))? Зачем брать абсолютное значение журнала?   -  person Patricia Shanahan    schedule 11.12.2019
comment
@PatriciaShanahan Первый abs() должен сделать число положительным, так как log10() не работает при отрицательных значениях. Результатом log10() является показатель степени исходного числа, который может быть любым от примерно -323 до 308 (т. е. диапазон doubles составляет примерно от 1e-323 до 1e+308, независимо от знака). Меня не волнует знак экспоненты, только то, что он далек от 1, поэтому я беру еще abs().   -  person jmd_dk    schedule 11.12.2019
comment
@PatriciaShanahan Знак экспоненты определяется из одного бита и поэтому не представляет большого интереса, за исключением, конечно, если окажется, что один знак появляется намного чаще, чем другой. Я игнорирую NaN и infs в основном только для того, чтобы остальные данные могли быть нанесены на график.   -  person jmd_dk    schedule 12.12.2019
comment
Я думаю, вы недооцениваете асимметрию между нулевыми битами экспоненты и единичными битами экспоненты.   -  person Patricia Shanahan    schedule 12.12.2019
comment
В частности, вполне вероятно, что то, что вы интерпретируете как очень большое, почти все на самом деле очень маленькое. Решение отказаться от знака экспоненты делает невозможным уверенность в выводе программы.   -  person Patricia Shanahan    schedule 12.12.2019


Ответы (1)


Есть много разных вещей, которые вы можете найти в памяти, но удивительное количество из них отображается на очень большие или очень маленькие числа с плавающей запятой, бесконечности или NaN. В дальнейшем «FP» означает 64-битный двоичный код IEEE 754 с плавающей запятой.

Во-первых, поскольку они уже обсуждались в комментариях к вопросу, рассмотрим адреса. В 64-битном адресе все биты экспоненты обычно равны нулю (нижний конец памяти) или все биты экспоненты имеют высокий уровень (верхний конец памяти, часто адреса стека). Если все биты экспоненты высокие, это бесконечность или NaN, которые программа, по-видимому, игнорирует. Если все биты экспоненты равны нулю, это субнормальное число или ноль. Все субнормальные числа меньше 2,3E-308, что считается показателем степени 308.

Теперь рассмотрим 32-битные целые числа, еще одну очень распространенную форму данных. Отрицательные 32-битные целые числа с дополнением до двух, которые сопоставляются с конечным FP, равны -1048577 или меньше. Числа вроде -42 или -1 сопоставляются с NaN, игнорируемыми программой. Точно так же положительные целые числа среднего значения имеют все биты экспоненты равными нулю и, таким образом, отображаются в субнормальные числа, отображаемые на конец гистограммы с большим показателем экспоненты. Даже маленькие нормальные числа соответствуют удивительно большим целым числам. Например, первые 32 бита 1e-300 имеют целочисленное значение 27 618 847.

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

person Patricia Shanahan    schedule 11.12.2019