Рубрика «числа»

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

Интересно? Читайте дальше

В сети и в развлекательной литературе нередко можно встретить разные математические фокусы: вас просят задумать какое-то число, затем выполнить с ним ряд арифметических действий. После этого собеседник точно называет получившееся у вас число. Большинство этих фокусов основано на том, что исходное число в ходе преобразований незаметно подменяется другим, а затем за несколько шагов сводится к известному ответу. Такие фокусы, например, можно встретить в книгах Якова Перельмана.

Читать полностью »

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

Так как язык, на котором всё это написано — C#, то есть нюансы. А именно, что стандартный HashSet<int> на хранение одного числа тратит 16 байт, также влияет филл фактор. Есть более эффективные реализации (когда-нибудь и про них напишу), но с другой стороны, можно же тупо хранить в массивах, по 4 байта на число (требуется хранить инты), что достаточно эффективно. Но можно ли уменьшить ещё?

Сразу скажу, у меня нет ответа, как лучше сделать, возможно его не существует, ибо есть множество факторов, связанных с особенностями распределения конкретных данных. Но есть идеи, которыми я поделюсь: какие варианты экономии памяти существуют. Также рекомендую до прочтения поста подумать самостоятельно, всё-таки это неплохая разминка для ума. Для определённости сформулирую задачу следующим образом:

Есть набор неотрицательных уникальных интов (32 бита). Требуется хранить их эффективно в оперативной памяти, из операций — создание набора и получение всех элементов. Не нужно получать элементы по индексу, добавлять новые или удалять.

В статье будет много букв и цифр и ни одной картинки (кроме упакованного котика на КДПВ).
Читать полностью »

Всем привет! Мы очень часто пользуемся привычными числами в наших любимых языках программирования. Привычные это 1, -1.5, pi или даже комплексные. А вот NaN, +Inf, -Inf используется нами гораздо реже.

Примечание:

В статье я использую элементарные функции Python версии 3.6.8, но многое будет актуально и для других языков, например для JS.
Читать полностью »

Неисчислимое: в поисках конечного числа - 1

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

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

В XX в. стала отчетливо проступать другая проблема. С бесконечностью мы можем разобраться при помощи одного символа (∞), но что делать с числами, которые меньше бесконечности, но при этом невообразимо огромны?

Мы вплотную подошли к числам, едва уступающим «уроборосу», но при этом все еще имеющим теоретическое и практическое значение. Вы, вероятно, могли слышать о числе Грэма, которое является верхней границей для решения определенной проблемы в теории Рамсея. Спустя 88 лет после появления теоремы Рамсея математики готовы отбросить старые методы и пойти еще дальше.

Добро пожаловать в кроличью нору без дна.
Читать полностью »

Краеугольный камень псевдослучайности: с чего начинается поиск чисел - 1
(с)

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

Когда речь заходит о генераторах случайных (или псевдослучайных) чисел, рассказ всегда строится вокруг поиска истинной случайности. Пока серьезные математики десятилетиями ведут дискуссии о том, что считать случайностью, в практическом отношении мы давно научились использовать «правильную» энтропию. Впрочем, «шум» — это лишь вершина айсберга.

С чего начать, если мы хотим распутать клубок самых сильных алгоритмов PRNG и TRNG? На самом деле, с какими бы алгоритмами вы не имели дело, все сводится к трем китам: seed, таблица предопределенных констант и математические формулы.

Каким бы ни был seed, еще есть алгоритмы, участвующие в генераторах истинных случайных чисел, и такие алгоритмы никогда не бывают случайными.

Читать полностью »

Поиск генераторов истинных случайных чисел - 1

Знай себе числа генерируй на основе непредсказуемых данных физического мира — немудреная мысль эта преследует человека на протяжении всего пути современной криптографии. Псевдослучайные генераторы чисел (PRNG), основанные на одних лишь математических алгоритмах, предсказуемы или подвержены внешнему влиянию, поэтому аппаратные генераторы, использующие различные источники энтропии, считаются золотым стандартом безопасности.

Однако даже генераторы реальных случайных чисел (RNG), собирающие непредсказуемые данные физических явлений, имеют недостатки: они могут быть громоздкими, медленными и дорогостоящими в производстве. Нет никакой гарантии, что проприетарная система не открыта для спецслужб — поэтому разработчики FreeBSD, отказались от непосредственного использования аппаратных генераторов, встроенных в чипы Intel.

Эволюция методов шифрования повлекла за собой необходимость создать более совершенные генераторы — о них и пойдет сегодня речь.

Читать полностью »

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

image

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

На самом деле нет, ничего подобного (в качестве подтверждения можете почитать про эту историю). Но в целом это объяснение вполне правдоподобно. Кассиры в наши дни не умеют делать расчеты в уме, не так ли?

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

Это утверждение, опять же, неверно. Неверно, но популярно? Что ж, вполне может быть.
Читать полностью »

Красота чисел. Адаптация чисел для мозга: округление и лингвистические модификаторы - 1

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

Человеческий мозг плохо приспособлен для представления и обработки цифр. Эволюция не сформировала этот навык. По большому счёту, цифры вообще не требуются для выживания, то есть для древнего человека знание арифметики не было эволюционным преимуществом. Такое эволюционное преимущество у индивидов появилось только после изобретения торговли и финансов. До этого древним людям в общении было достаточно слов «один», «два» и «много». Собственно, этими словами ограничены способности обычного человека и сегодня, если он не прошёл специальное обучение.

У людей исключительно слабые врождённые способности по обработке цифр: человек без подготовки обычно способен отличать числа только до трёх или четырёх. Это навык, который нужно специально осваивать и тщательно тренировать. Размышление о цифрах может активировать одновременно несколько когнитивных систем в мозге, в том числе систему обработки визуальной информации, как показало научное исследование Бурра и Росса 2008 года. Для такой сложной задачи в мозге просто нет специализированного отдела (арифметического сопроцессора), поэтому приходится задействовать сторонние отделы, приспосабливая их для этой задачи.
Читать полностью »

Красота чисел. Как быстро вычислять в уме - 1
Старинная запись на квитанции в уплате подати («ясака»). Она означает сумму 1232 руб. 24 коп. Иллюстрация из книги: Яков Перельман «Занимательная арифметика»

Ещё Ричард Фейнман в книге «Вы конечно шутите, мистер Фейнман!» поведал несколько приёмов устного счёта. Хотя это очень простые трюки, они не всегда входят в школьную программу.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js