Каковы шансы увидеть картинку с Реддита в мусоре из видеопамяти?

По поводу первоапрельской картинки с Реддита: если я правильно помню теорию вероятностей, то вероятность того, что из мусора в видеопамяти мы увидим такую картинку:
Каковы шансы увидеть картинку с Реддита в мусоре из видеопамяти? Теория вероятностей, Видеокарта, Рандом, Reddit, Длиннопост

равняется (1/16)^1 000 000, что эквивалентно 1 × 10^-1204120


Что если попытаться сгенерировать такую картинку рандомом? Ведь технический прогресс, мощное железо. Да и цветов всего 16. На фотографиях вон в миллион раз больше.


Чтож, если я правильно понимаю, то мы имеем дело с размещением с повторениями.

Это где-то 1 000 000 ^ 16 комбинаций, что эквивалентно 1 × 10^22. Запомним эту цифру, и будем стремиться к ней.


Скорость заполнения текстур у наиболее мощной видеокарты на сегодня (GTX 1080 Ti) примерно 130 гигапикселей/с.

Каковы шансы увидеть картинку с Реддита в мусоре из видеопамяти? Теория вероятностей, Видеокарта, Рандом, Reddit, Длиннопост

В картинке ровно один мегапиксел, значит в секунду мы можем перебрать 130 тысяч комбинаций, что дает нам 4 × 10^12 картинок в год.


Возьмем миллион видеокарт и поднимем наши возможности до 4 × 10^18. За 2.5 тысячи лет наш кластер переберет 1 × 10^22. Ну, вроде как победа)


А можно как-нибудь побыстрее? Берем 100 миллионов карточек и успеваем 25 лет. Берем в 10 раз более мощные карты и успеваем за два с половиной.


Да, по итогу человечество может позволить себе сгенерировать себе такую картинку рандомом) А если поставить их в России, то мы сможем позволить себе сэкономить на отоплении. Но расчета отопления в этом посте не будет, даже не просите)



Было бы неправильно останавливаться на 16 цветах, ведь у нас на фотографиях в миллион раз больше? Ладно-ладно, не надо кидаться тяжелыми предметами, возьмем 256 цветов, как на гифках.


Итак, вероятность (1/256)^1 000 000, что эквивалентно 1 × 10^-2 408 240. На самом деле выглядит почти так же как случай с 16 цветами, что одно маленькое, что другое.


Число комбинаций 1 × 10^262. Это да, разница очевидна.


Сразу возьмем миллион видеокарт за миллион лет, получим 4 × 10^24. За миллиард лет выйдет 4 × 10^30.


У Солнца осталось топлива где-то на 5 миллиардов лет, так что умножим на них, выцарапаем еще один порядок, пусть будет 2 × 10^31. Game over? Не успели?

Каковы шансы увидеть картинку с Реддита в мусоре из видеопамяти? Теория вероятностей, Видеокарта, Рандом, Reddit, Длиннопост

Поднажмем, заставим каждого человека купить по две видеокарты. Грубо примем среднее население Земли в ближайшие 5 миллиардов лет за 50 миллиардов человек, значит видеокарт у нас уже 100 миллиардов в среднем.


Что? Всего 2 × 10^36? Мы так просто не сдадимся, бросим все силы человечества на проектирование видеокарт, поднимем среднюю производительность в триллион раз!


2 × 10^48...


P. S. Хорошо, все-таки, что 16 миллионов цветов не взяли

P. P. S. Просьба проверить расчеты, писал без бумаги, тервер изучал почти 10 миллионов лет назад :/

Наука | Научпоп

7.7K постов78.5K подписчиков

Добавить пост

Правила сообщества

Основные условия публикации

- Посты должны иметь отношение к науке, актуальным открытиям или жизни научного сообщества и содержать ссылки на авторитетный источник.

- Посты должны по возможности избегать кликбейта и броских фраз, вводящих в заблуждение.

- Научные статьи должны сопровождаться описанием исследования, доступным на популярном уровне. Слишком профессиональный материал может быть отклонён.

- Видеоматериалы должны иметь описание.

- Названия должны отражать суть исследования.

- Если пост содержит материал, оригинал которого написан или снят на иностранном языке, русская версия должна содержать все основные положения.


Не принимаются к публикации

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

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

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


Наказывается баном

- Оскорбления, выраженные лично пользователю или категории пользователей.

- Попытки использовать сообщество для рекламы.

- Фальсификация фактов.

- Многократные попытки публикации материалов, не удовлетворяющих правилам.

- Троллинг, флейм.

- Нарушение правил сайта в целом.


Окончательное решение по соответствию поста или комментария правилам принимается модерацией сообщества. Просьбы о разбане и жалобы на модерацию принимает администратор сообщества. Жалобы на администратора принимает @SupportComunity и общество Пикабу.

9
Автор поста оценил этот комментарий

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

раскрыть ветку (1)
4
Автор поста оценил этот комментарий

Если бы у нас был полный перебор, то да, можно было бы высчитать с точностью до итерации, и соответственно миллисекунды.


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

показать ответы
2
Автор поста оценил этот комментарий

а если добавить закон Мура, то через 2 года производительность возрастет в 2 раза

раскрыть ветку (1)
3
Автор поста оценил этот комментарий
Скорость заполнения текстур у наиболее мощной видеокарты двухлетней давности (GTX 980 Ti) примерно 96 гигапикселей/с. Как видите, рост не в два раза, где-то 30% по этому параметру. Но вообще, увеличение мощности карт в статье рассмотрено.
19
Автор поста оценил этот комментарий
А как проверить, что нужная картинка сгенерировалась? Для этого надо добавить код для сравнения с исходной картинкой, а на это тоже машинное время уйдет.
раскрыть ветку (1)
2
Автор поста оценил этот комментарий

Можно добавить в видеокарты новый блок, который на уровне железа будет сравнивать текущее состояние видеопамяти с искомой картинкой. Какая-нибудь маска. Я думаю делать это можно очень-очень быстро, картинка маленькая, сравнение простое. Так что этим временем я решил пренебречь.

показать ответы
Автор поста оценил этот комментарий

а что если генерировать данную картину не полным рандомом, а изменяя только те пиксели которые не соответствуют оригиналу?

раскрыть ветку (1)
Автор поста оценил этот комментарий

Это вообще другая задача, а в целом — почему нет.

4
Автор поста оценил этот комментарий

Если бы у нас был полный перебор, то да, можно было бы высчитать с точностью до итерации, и соответственно миллисекунды.


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

раскрыть ветку (1)
Автор поста оценил этот комментарий
Я таки накосячил с расчетами, комбинаций будет 16^1000000, расходимся.
2
Автор поста оценил этот комментарий

Верно, (10^6)^16 = 10^(6*16) = 10^96
А то, что количество комбинаций будет не 1000000^16, а 16^1000000 вас не смущает?

раскрыть ветку (1)
Автор поста оценил этот комментарий
По сути, получается, что искомое число комбинаций равно 16^1000000 в первой части, и 256^1000000 во второй, соответственно вывод будет что точно не успеваем. А остальное верно?
1
Автор поста оценил этот комментарий

Вначале:

"равняется (1/16)^1 000 000" -- Логично. Всего 1кк пикселей и шанс того что каждый будет нужного цвета 1/16. 1/16*1/16*1/16 и так 1кк раз. Упрощаем получаем 1/16^1000000


"Это где-то 1 000 000 ^ 16 комбинаций, что эквивалентно 1 × 10^22"

Почему внезапно тут наоборот.

Ведь по такой же логике каждый пиксель может быть любым из 16 цветов.

Если два пикселя то всего вариантов 16*16. Если 3 -- 16*16*16. Если 1кк -- 16^1000000

Если брать ту же вики (картинка):

Количество вариантов миллионной-картинки в котором каждый пиксель является от 1 до 16 равно:

Вместо n - 16, вместо k - 1000000 и по формуле получаем то что я выше написал.

Иллюстрация к комментарию
раскрыть ветку (1)
Автор поста оценил этот комментарий
Спасибо, что указали на ошибку. Действительно, но там еще и в вычислении степени косяк.
3
Автор поста оценил этот комментарий
Конечно, смущает. Просто в арифметику проще ткнуть носом, чем в комбинаторику)
раскрыть ветку (1)
Автор поста оценил этот комментарий
Действительно, с расчетами я накосячил, спасибо что указали на ошибку :/
Автор поста оценил этот комментарий

Но ведь она может сгенерироваться на 5 раз, или на 1525, или на 24355 раз, это же вероятность, или я чего то не знаю?

раскрыть ветку (1)
Автор поста оценил этот комментарий
Может, но это маловероятно.
1
Автор поста оценил этот комментарий

Плохо помните теорию вероятностей.


На одном из первых занятий по этому предмету должны были рассказать что всегда стоит задаваться вопросом "где в задаче случайность?". Обычно эту проблему иллюстрируют задачей про человека который садится в первый пришедший автобус но в результате количество отправлений в одну сторону существенно отличается от количества в противоположную. Так и тут задача может сильно меняться при формализации случайных факторов задачи.


Кроме того память видеокарты не обязаны изменять полностью - замена даже одного бита картинки приведет к другой картинке таким образом скорость перебора картинок это скорость изменения одного бита в памяти карты (есть соответствующая задача в курсе дискретной математики)


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


А можно пойти еще дальше - бывают сложные виды размещения картинок. Для примера если заданную картинку вставить посередине картинки большей площади то картинка же все равно будет в памяти, но занимаемое ей место не будет последовательным. И тут уже вопрос насколько далеко можно зайти. Потому как найти полностью Евангелие в полном собрании сочинений Ленина совершенно несложная задача.

раскрыть ветку (1)
Автор поста оценил этот комментарий
Перебор — отдельно, рандом — отдельно. Если занимаемое место не будет последовательным, значит эту картинку на экране мы и не увидим.
3
Автор поста оценил этот комментарий

насколько я знаю, квантовый компьютер проверяет все результаты одновременно, так что он сразу выведет нужную картинку

раскрыть ветку (1)
Автор поста оценил этот комментарий
А откуда он узнает какая нужна?)
показать ответы
5
Автор поста оценил этот комментарий
1000000^16 != 10^22
раскрыть ветку (1)
Автор поста оценил этот комментарий
Возможно я ошибся, чему оно равно?
показать ответы
Автор поста оценил этот комментарий

@Zifix, а если использовать мощность гипотетического квантового компьютера, умножающего мощность на 8?

раскрыть ветку (1)
Автор поста оценил этот комментарий

Умножающего мощность чего? Ну и потом, более мощные карты в посте упомянуты.

показать ответы
Автор поста оценил этот комментарий

а как же случай с духовым оркестром? может и выпасть картинка почти сразу

раскрыть ветку (1)
Автор поста оценил этот комментарий
Конечно есть, что прям на первой попытке, и вероятность этого — 1 × 10^-1 204 120
1
Автор поста оценил этот комментарий

сравнивает с искомой

раскрыть ветку (1)
Автор поста оценил этот комментарий
И генерирует рандомную комбинацию эквивалентную искомой? А где тут рандом?
показать ответы