Тяжелые хвосты
Жара спала, и в целом, наступила суббота на наш замечательный перенаселённый город. Вспомнилось мне, что когда-то я усиленно учился теории вероятности и всякой статистике, однако занудствовать прям с формулами мне не хочется, давайте лучше немного порассуждаем. Для этого возьмём очень наглядную и физическую вещь – рост взрослого мужчины (старше 18 лет), вспомните ваших знакомых, и просто людей, которых вы видите на улице, предполагаю, что их рост будет, в основном, варьироваться между 160 и 195 сантиметрами, причём пограничные случаи будут довольно редки (предполагается, что вы не зависаете в компании баскетболистов). Можно встретить человека выше или ниже? Да, определённо, особенно если живёте в городе-миллионике и ездите на метро, а часто ли? – Ну не то, чтобы. Вот вам статья на тему, что людей сильно выше совсем немного, учитывая, что на планете живёт несколько миллиардов человек.
Надеюсь, к этому моменту все осознали, что рост, в основном, размазан в определённом диапазоне, а теперь я вам скажу, что это всё давно формализовано и изложено в виде тех самых скучных формул, что я не буду тут упоминать, и называется Нормальным или Гауссовым распределением. В трёх словах его суть в следующем: если по оси X отложить рост, а по оси Y отложить процент, как часто данный рост встречается в популяции, то получится колоколообразная фигура с максимумом у среднего значения, более того, с крайне высокой вероятность рост не отклоняется дальше определённой величины. А вот тут для нас уже всё нарисовали, листайте до слов “Height is normally distributed”. И да…с большой вероятностью в Вузе вас пытались этому научить даже на нетехнической специальности.
А все ли величины распределены согласно этому распределению? – Очевидно, что нет – иначе почему учебник математической статистики такой толстый и не заканчивается на нормальном распределении. А если серьёзнее, можно рассмотреть другую очень жизненную величину – доходы отдельно взятого человека. Может показаться, что величина эта не случайна – и действительно, для каждого отдельного человека она зависит от множества факторов, но мы эти факторы не изучаем, поэтому считаем, что она случайна. Попробуем тут порассуждать примерно, как про рост: и так, вы знаете собственную зарплату, можете предположить, что люди в той же должности и отрасли получают примерно столько ж (умножить поделить на 3), а вот там элитный район в городе – там, видимо, доходы побольше, а вот люди ездят на теслах – у них ещё побольше, ну и все мы знаем про существование списка Форбс. Тут важно заметить, что учителей и врачей довольно много – миллионы, элитные районы и поселки явно поменьше, на теслах, Бентли и прочая ездят ещё поменьше, а список Форбс это меньше трёх тысяч людей на всём свете. И тут я опять не открываю Америку – всё давно посчитано и написано, просто посмотрите на первую картинку — там максимум концентрируется в районе низких значений и потом хвост бесконечно уходит вправо. Если применить на пример выше сотни миллионов людей получают несколько сот долларов в месяц, но потом всё реже и реже идут экземпляры с более высоким доходом, заканчивая единичными случаями почти 20 миллиардов в месяц. А если применить на пример с ростом, получалось бы примерно так: большинство людей в районе 170 см, но можно найти хоть и редко ростом с Эйфелеву башню, Эмпайр-стейт-билдинг, от Земли до Плутона…
Подобные распределения называются - распределениями с тяжелыми хвостами, когда-то я читал книжку "Черный Лебедь" – не дочитал, бросил на середине, потому что к тому моменту я уже тер. вер. знал :)
#today #flood #education #math #probability_theory #books
Жара спала, и в целом, наступила суббота на наш замечательный перенаселённый город. Вспомнилось мне, что когда-то я усиленно учился теории вероятности и всякой статистике, однако занудствовать прям с формулами мне не хочется, давайте лучше немного порассуждаем. Для этого возьмём очень наглядную и физическую вещь – рост взрослого мужчины (старше 18 лет), вспомните ваших знакомых, и просто людей, которых вы видите на улице, предполагаю, что их рост будет, в основном, варьироваться между 160 и 195 сантиметрами, причём пограничные случаи будут довольно редки (предполагается, что вы не зависаете в компании баскетболистов). Можно встретить человека выше или ниже? Да, определённо, особенно если живёте в городе-миллионике и ездите на метро, а часто ли? – Ну не то, чтобы. Вот вам статья на тему, что людей сильно выше совсем немного, учитывая, что на планете живёт несколько миллиардов человек.
Надеюсь, к этому моменту все осознали, что рост, в основном, размазан в определённом диапазоне, а теперь я вам скажу, что это всё давно формализовано и изложено в виде тех самых скучных формул, что я не буду тут упоминать, и называется Нормальным или Гауссовым распределением. В трёх словах его суть в следующем: если по оси X отложить рост, а по оси Y отложить процент, как часто данный рост встречается в популяции, то получится колоколообразная фигура с максимумом у среднего значения, более того, с крайне высокой вероятность рост не отклоняется дальше определённой величины. А вот тут для нас уже всё нарисовали, листайте до слов “Height is normally distributed”. И да…с большой вероятностью в Вузе вас пытались этому научить даже на нетехнической специальности.
А все ли величины распределены согласно этому распределению? – Очевидно, что нет – иначе почему учебник математической статистики такой толстый и не заканчивается на нормальном распределении. А если серьёзнее, можно рассмотреть другую очень жизненную величину – доходы отдельно взятого человека. Может показаться, что величина эта не случайна – и действительно, для каждого отдельного человека она зависит от множества факторов, но мы эти факторы не изучаем, поэтому считаем, что она случайна. Попробуем тут порассуждать примерно, как про рост: и так, вы знаете собственную зарплату, можете предположить, что люди в той же должности и отрасли получают примерно столько ж (умножить поделить на 3), а вот там элитный район в городе – там, видимо, доходы побольше, а вот люди ездят на теслах – у них ещё побольше, ну и все мы знаем про существование списка Форбс. Тут важно заметить, что учителей и врачей довольно много – миллионы, элитные районы и поселки явно поменьше, на теслах, Бентли и прочая ездят ещё поменьше, а список Форбс это меньше трёх тысяч людей на всём свете. И тут я опять не открываю Америку – всё давно посчитано и написано, просто посмотрите на первую картинку — там максимум концентрируется в районе низких значений и потом хвост бесконечно уходит вправо. Если применить на пример выше сотни миллионов людей получают несколько сот долларов в месяц, но потом всё реже и реже идут экземпляры с более высоким доходом, заканчивая единичными случаями почти 20 миллиардов в месяц. А если применить на пример с ростом, получалось бы примерно так: большинство людей в районе 170 см, но можно найти хоть и редко ростом с Эйфелеву башню, Эмпайр-стейт-билдинг, от Земли до Плутона…
Подобные распределения называются - распределениями с тяжелыми хвостами, когда-то я читал книжку "Черный Лебедь" – не дочитал, бросил на середине, потому что к тому моменту я уже тер. вер. знал :)
#today #flood #education #math #probability_theory #books
🔥1
А есть ли вероятность?
Выходные продолжаются, как и наша рубрика “Тервер для самых маленьких”. Если вы открывали и пробежались глазами через эту ссылку в прошлой статье, то могли заметить довольно-таки очевидные вещи: рост зависит от многих факторов, включая генетические и нет, средний рост разный в разных поколениях, в разных регионах мира средний рост сильно отличается – жители Черногории высокие даже для европейцев, жители Таиланда – довольно низкие. Это означает, что, если б мы взяли данные по одному регионы, а желательно ещё и моноэтнические и только людей одного и того же года рождения, то получили бы тот же самый “колокол”, но более узкий. Кстати, ширина “колокола” обусловлена так называемым среднеквадратичным отклонением – СКО (квадратным корнем из дисперсии). Воздействие же множества довольно разнообразных факторов – причина, приводящая к нормальному распределению роста.
А есть ли другие величины, распределённые согласно нормальному распределению? Конечно! И очень много, особенно, это касается настоящих физических величин: результатов экспериментов, измерений, результатов работы производственных линий, да хоть линии производства мороженного, объема кофе из кофемашины при одинаковых настройках и т.д. Если вдруг кто не верит, что даже заводские продукты ежедневного потребления немного варьируются, то вот ссылка. Другое дело, что, когда погрешность (3 * СКО), много меньше номинального значения (среднего значения) конечному потребителю не стоит и волноваться – так в приведенной ссылке они обещают, что-то вроде +- 5 грамм на килограмм. Обратите внимание, я написал +-, это не значит, что, если вы купите 100 пакетов молока, вы получите недовесок или перевесок в 500 грамм, а вот настоящий результат тут – это тема для отдельной статьи.
Тут можно заодно упомянуть наивное заблуждение, что в “точных” науках всё абсолютно точно. Нет – все физические величины всегда идут с погрешность, максимум, что возможно сделать это ограничить эту величину при соблюдении определённых условий. И касается это не только пищевых продуктов, но и высокотехнологичных производств: производство CPU требует миллиардов долларов, да и каждое отдельное изделие стоит несколько сот долларов, тем не менее производитель не может штамповать все процессоры с одинаково хорошими заданными характеристиками даже на одной и той же линии, вместо этого постфактум их тестируют после чего классифицируют кто тут Core-i5, ну а кто Core-i3.
#today #flood #math #education #probability_theory
Выходные продолжаются, как и наша рубрика “Тервер для самых маленьких”. Если вы открывали и пробежались глазами через эту ссылку в прошлой статье, то могли заметить довольно-таки очевидные вещи: рост зависит от многих факторов, включая генетические и нет, средний рост разный в разных поколениях, в разных регионах мира средний рост сильно отличается – жители Черногории высокие даже для европейцев, жители Таиланда – довольно низкие. Это означает, что, если б мы взяли данные по одному регионы, а желательно ещё и моноэтнические и только людей одного и того же года рождения, то получили бы тот же самый “колокол”, но более узкий. Кстати, ширина “колокола” обусловлена так называемым среднеквадратичным отклонением – СКО (квадратным корнем из дисперсии). Воздействие же множества довольно разнообразных факторов – причина, приводящая к нормальному распределению роста.
А есть ли другие величины, распределённые согласно нормальному распределению? Конечно! И очень много, особенно, это касается настоящих физических величин: результатов экспериментов, измерений, результатов работы производственных линий, да хоть линии производства мороженного, объема кофе из кофемашины при одинаковых настройках и т.д. Если вдруг кто не верит, что даже заводские продукты ежедневного потребления немного варьируются, то вот ссылка. Другое дело, что, когда погрешность (3 * СКО), много меньше номинального значения (среднего значения) конечному потребителю не стоит и волноваться – так в приведенной ссылке они обещают, что-то вроде +- 5 грамм на килограмм. Обратите внимание, я написал +-, это не значит, что, если вы купите 100 пакетов молока, вы получите недовесок или перевесок в 500 грамм, а вот настоящий результат тут – это тема для отдельной статьи.
Тут можно заодно упомянуть наивное заблуждение, что в “точных” науках всё абсолютно точно. Нет – все физические величины всегда идут с погрешность, максимум, что возможно сделать это ограничить эту величину при соблюдении определённых условий. И касается это не только пищевых продуктов, но и высокотехнологичных производств: производство CPU требует миллиардов долларов, да и каждое отдельное изделие стоит несколько сот долларов, тем не менее производитель не может штамповать все процессоры с одинаково хорошими заданными характеристиками даже на одной и той же линии, вместо этого постфактум их тестируют после чего классифицируют кто тут Core-i5, ну а кто Core-i3.
#today #flood #math #education #probability_theory
🔥2
Неожиданные проблемы нативных типов
Недавно попалась на глаза статья про редкие языки программирования и была там фраза, что мол в Cobol есть отдельный тип для представления денег…и я вспомнил, что когда-то, уже очень давно, я и мои коллеги, тоже сталкивались с проблемами представления денежных сумм в C++. Казалось бы – ерунда какая? В C++ (Java, C# – туда же) есть типы float и double для представления чисел с запятой, почему бы их не использовать? Потому что они не подходят: float уже на вот таком примере “сломается”:
Выведя 999999.
С double надо искать пример посложнее, но, поверьте, когда его найдут у вас в программе – будет не до смеха. Тут можно отметить пару основных недостатков: большинство дробей типа 0.1, 0.2 и т.д. не имеют конечного представления в двоичной системе, при сложениях и вычитаниях эти числа “выравниваются” внутри что б быть представлены с той же самой степень, а число знаков, выделенных под мантиссу – конечно, можно тут потерять одно из чисел совсем, как в примере выше.
Как же хранить денежные величины в C++ – легко, храните их (в Сберегательной кассе) как целое – число копеек, используя long long int, перегрузите соответствующие операторы конструкторы и так далее. Забавно, что в Standard C++ library нет ничего подходящего для решения проблемы, как и в Qt. В sql есть, например, decimal.
Тут можно заметить, что основные типы данных в C++, по сути, те же, что в языке Си, в котором они те же, что дает архитектура процессора – т.к. язык Си – это высокоуровневый ассемблер, то есть байт, 2 байта, 4, возможно 8 для целых типов, и 4, 8 байтов для чисел с плавающей запятой. Так оно и тянется с тех пор… В тоже время, те же double/float неплохо подходят для инженерных расчетов, если бы в примере выше мы бы считали силу тока, движущий момент, любую другую физическую величину, никого бы не взволновала потеря одной сотой, на фоне величины числа a – эта ошибка вписывается в допустимую погрешность.
#job #IT #c_plus_plus #math
Недавно попалась на глаза статья про редкие языки программирования и была там фраза, что мол в Cobol есть отдельный тип для представления денег…и я вспомнил, что когда-то, уже очень давно, я и мои коллеги, тоже сталкивались с проблемами представления денежных сумм в C++. Казалось бы – ерунда какая? В C++ (Java, C# – туда же) есть типы float и double для представления чисел с запятой, почему бы их не использовать? Потому что они не подходят: float уже на вот таком примере “сломается”:
float a = 0.01;
float b = 999999.00;
float sum = a + b;
std::cout << sum << std::endl;
Выведя 999999.
С double надо искать пример посложнее, но, поверьте, когда его найдут у вас в программе – будет не до смеха. Тут можно отметить пару основных недостатков: большинство дробей типа 0.1, 0.2 и т.д. не имеют конечного представления в двоичной системе, при сложениях и вычитаниях эти числа “выравниваются” внутри что б быть представлены с той же самой степень, а число знаков, выделенных под мантиссу – конечно, можно тут потерять одно из чисел совсем, как в примере выше.
Как же хранить денежные величины в C++ – легко, храните их (в Сберегательной кассе) как целое – число копеек, используя long long int, перегрузите соответствующие операторы конструкторы и так далее. Забавно, что в Standard C++ library нет ничего подходящего для решения проблемы, как и в Qt. В sql есть, например, decimal.
Тут можно заметить, что основные типы данных в C++, по сути, те же, что в языке Си, в котором они те же, что дает архитектура процессора – т.к. язык Си – это высокоуровневый ассемблер, то есть байт, 2 байта, 4, возможно 8 для целых типов, и 4, 8 байтов для чисел с плавающей запятой. Так оно и тянется с тех пор… В тоже время, те же double/float неплохо подходят для инженерных расчетов, если бы в примере выше мы бы считали силу тока, движущий момент, любую другую физическую величину, никого бы не взволновала потеря одной сотой, на фоне величины числа a – эта ошибка вписывается в допустимую погрешность.
#job #IT #c_plus_plus #math
👍1
Сложите это, пожалуйста
Написав эту заметку про типы с плавающей точкой, вспомнил, что был и другой интересный случай с этими числами, правда, из практики собеседований, но не суть. Вопрос звучал примерно так: дан массив чисел типа double, как лучше его отсортировать (по возрастающей или убывающей), чтобы просуммировать его с большой точностью.
В этом вопросе, с точки зрения, обывателя или программиста, не вникшего в тонкости работы с этими числами, прекрасно абсолютно всё. Наверняка в школе, вы слышали о том, что перестановка мест слагаемых суммы не меняет (хотя бы в такой формулировке), если этому верить, значит задача лишена смысла. Но раз спрашивают, и я об этом пишу, наверное, смысл есть, но как так?
Начну издалека: когда нас в детстве учат устному счёту 1, 2, 3…нас учат натуральным числам N и их свойствам - числам, которыми я могу посчитать количество предметов, далее, “добавляя” к ним 0 и отрицательные числа, мы получаем Z - целые числа, “присоединяя” к ним обыкновенные дроби мы получаем множество Q – множество рациональных чисел , наконец, решая квадратные и не только уравнения и рассматривая другие конструкции, мы получаем множество вещественных чисел R (примеры, корень из двух, экспонента и так далее). Эту цепочку можно было бы продолжить: комплексные числа, дуальные, кватернионы, а в вещественных выделить алгебраические и трансцендентные…Но я не буду об этом говорить, потому что, они все не имеют отношения к тем числам, что мы имеем в C++ как базовый типы. Об этом немножечко позже.
Непосредственно с числами, даже каким-то образом со способом их определения, связанны основные арифметические операции: сложение, вычитание, умножение, деление. На эту заметку нам хватит сложения: даже эти операции не так уж элементарны…особенно деление. Бинарная операция сложения (т.е. принимающая два аргумента) для множеств N, Z, Q, R (на самом деле и все остальные как я помню, но это не важно) обладает свойствами коммутативности и ассоциативности. Коммутативность — значит всего лишь, что a+b = b+a, совсем просто, а вот ассоциативность, посложнее: a + (b+c) = (a+b) + c. Иными словами, операция у нас бинарная, мы умеет сложить 2 числа, а вот если написать, что мы складываем 3 числа, то можно сначала сложить первые 2, или последние 2, но результат будет одинаков. Если вы думаете, что это какая-то глупость и так всегда, то посмотрите на вычитание: (1 – 2) – 3 = -4, но 1 – (2 – 3) = 0 (вычитание не ассоциативно). На самом деле Z – это кольцо, Q, R – это поле, но мы с этим не будем работать.
В C++ (и во многих остальных ЯП), есть различные операторы, конечно, включая и арифметические, не буду тут давать формального определения оператора в С++, понятно, что это некоторая синтаксическая сущность, тут важно, что для всех операторов стандарт языка предоставляет информацию об их ассоциативности, а именно, либо слева направо, либо справа налево. Большинство слева направо, но нас интересует только operator +.
Прошу ещё раз заметить: в C++ a+b+c это (a+b) + c, то есть в математике, скобки я могу ставить, как угодно, а компилятор, видя выражение без скобок, неявно поставит их таким образом, то есть, на самом деле, нет там никаких скобок, а есть ассемблерные инструкции (картинки с https://godbolt.org/ будут под постами)
#IT #job #c_plus_plus #math #weird #interview
Написав эту заметку про типы с плавающей точкой, вспомнил, что был и другой интересный случай с этими числами, правда, из практики собеседований, но не суть. Вопрос звучал примерно так: дан массив чисел типа double, как лучше его отсортировать (по возрастающей или убывающей), чтобы просуммировать его с большой точностью.
В этом вопросе, с точки зрения, обывателя или программиста, не вникшего в тонкости работы с этими числами, прекрасно абсолютно всё. Наверняка в школе, вы слышали о том, что перестановка мест слагаемых суммы не меняет (хотя бы в такой формулировке), если этому верить, значит задача лишена смысла. Но раз спрашивают, и я об этом пишу, наверное, смысл есть, но как так?
Начну издалека: когда нас в детстве учат устному счёту 1, 2, 3…нас учат натуральным числам N и их свойствам - числам, которыми я могу посчитать количество предметов, далее, “добавляя” к ним 0 и отрицательные числа, мы получаем Z - целые числа, “присоединяя” к ним обыкновенные дроби мы получаем множество Q – множество рациональных чисел , наконец, решая квадратные и не только уравнения и рассматривая другие конструкции, мы получаем множество вещественных чисел R (примеры, корень из двух, экспонента и так далее). Эту цепочку можно было бы продолжить: комплексные числа, дуальные, кватернионы, а в вещественных выделить алгебраические и трансцендентные…Но я не буду об этом говорить, потому что, они все не имеют отношения к тем числам, что мы имеем в C++ как базовый типы. Об этом немножечко позже.
Непосредственно с числами, даже каким-то образом со способом их определения, связанны основные арифметические операции: сложение, вычитание, умножение, деление. На эту заметку нам хватит сложения: даже эти операции не так уж элементарны…особенно деление. Бинарная операция сложения (т.е. принимающая два аргумента) для множеств N, Z, Q, R (на самом деле и все остальные как я помню, но это не важно) обладает свойствами коммутативности и ассоциативности. Коммутативность — значит всего лишь, что a+b = b+a, совсем просто, а вот ассоциативность, посложнее: a + (b+c) = (a+b) + c. Иными словами, операция у нас бинарная, мы умеет сложить 2 числа, а вот если написать, что мы складываем 3 числа, то можно сначала сложить первые 2, или последние 2, но результат будет одинаков. Если вы думаете, что это какая-то глупость и так всегда, то посмотрите на вычитание: (1 – 2) – 3 = -4, но 1 – (2 – 3) = 0 (вычитание не ассоциативно). На самом деле Z – это кольцо, Q, R – это поле, но мы с этим не будем работать.
В C++ (и во многих остальных ЯП), есть различные операторы, конечно, включая и арифметические, не буду тут давать формального определения оператора в С++, понятно, что это некоторая синтаксическая сущность, тут важно, что для всех операторов стандарт языка предоставляет информацию об их ассоциативности, а именно, либо слева направо, либо справа налево. Большинство слева направо, но нас интересует только operator +.
Прошу ещё раз заметить: в C++ a+b+c это (a+b) + c, то есть в математике, скобки я могу ставить, как угодно, а компилятор, видя выражение без скобок, неявно поставит их таким образом, то есть, на самом деле, нет там никаких скобок, а есть ассемблерные инструкции (картинки с https://godbolt.org/ будут под постами)
#IT #job #c_plus_plus #math #weird #interview
Продолжение
Теперь вернемся, к тому какие встроенные типы для чисел в C++ мы имеем – integra и floating point…Первые мы пропускаем, насчёт вторых зададимся вопросом, вот в верху я представил множество различных чисел из алгебры – к чему относятся floating points? Правильный ответ: float и double способны представить некоторые рациональные числа. На этом всё, да, никаких настоящих вещественных чисел они не могут представить, корень из двух будет аппроксимирован некоторым рациональным приближением и так далее. Но, выше я писал, что рациональные числа обладают коммутативностью и ассоциативностью по сложению? Да…но… Уже случай из предыдущего поста, явно не ложится в наше пониманием рациональных чисел, демонстрируя, некоторое “поглощение”. Сложение чисел с плавающей точкой имеет свойства отличные от общеалгебраических, в результат их представления и реализации арифметических операций над ними. При этом, CPU, как и целочисленными значениями, складывает по 2 числа с плавающей точкой за одну инструкцию, было бы странно, если б мы сломали коммутативность: это был бы очевидный баг.
Я утверждаю следующее: можно найти тройку чисел с плавающей точкой (одновременно все float или double), такие что (a+b) +c не равно a + (b +c).
И сейчас я объясню, как я собираюсь их искать. Опять апеллирую к примеру с поглощением малого числа из прошлого поста, идея сводится к тому, что для начала мне нужно найти пару чисел, “большое” число a, и “малое” число b. Причём, число a “поглощает” число b, но число 2*a уже не будет поглощаться… Ещё раз: поскольку это поглощение основано на том, что при сложении числа выравниваются (представляются с одинаковыми экспонентами), малое число должно быть настолько малым, что б выровняться за правый край мантиссы. А если я умножу его на 2 (сдвину на разряд влево) оно учтётся пройдёт по последнему разряду мантиссы и учтётся.
Так же, я хочу числа с простым бинарным представлением, число a=1, число b…подсмотрим сюда, мантисса у нас 23 бита, т .е. я предполагаю, что нужно сдвинуть единицу направо на 24 разряда, иначе говоря мантисса у нас опять 1, а экспонента -24 (минус 24). Да нам удобнее для числа b использовать так называемую научную нотацию, да ещё и наполовину в 16ричной системе счисления…
Вот листинг, берем float т.к. он короче, и берем format т. к. он обещает “умный вывод”, с нулями только если они имеют смысл, и собираем всё с C++20:
Вывод будет:
То есть: во-первых, тройку чисел я нашёл, во-вторых, мы разобрались, что изначальная задача действительно имеет смысл, в-третьих, мы получили ответ на неё, а именно, нужно отсортировать от меньшего числа к большему (в силу ассоциативности слева направо и всех остальных выкладок).
#IT #job #c_plus_plus #math #weird #interview
Теперь вернемся, к тому какие встроенные типы для чисел в C++ мы имеем – integra и floating point…Первые мы пропускаем, насчёт вторых зададимся вопросом, вот в верху я представил множество различных чисел из алгебры – к чему относятся floating points? Правильный ответ: float и double способны представить некоторые рациональные числа. На этом всё, да, никаких настоящих вещественных чисел они не могут представить, корень из двух будет аппроксимирован некоторым рациональным приближением и так далее. Но, выше я писал, что рациональные числа обладают коммутативностью и ассоциативностью по сложению? Да…но… Уже случай из предыдущего поста, явно не ложится в наше пониманием рациональных чисел, демонстрируя, некоторое “поглощение”. Сложение чисел с плавающей точкой имеет свойства отличные от общеалгебраических, в результат их представления и реализации арифметических операций над ними. При этом, CPU, как и целочисленными значениями, складывает по 2 числа с плавающей точкой за одну инструкцию, было бы странно, если б мы сломали коммутативность: это был бы очевидный баг.
Я утверждаю следующее: можно найти тройку чисел с плавающей точкой (одновременно все float или double), такие что (a+b) +c не равно a + (b +c).
И сейчас я объясню, как я собираюсь их искать. Опять апеллирую к примеру с поглощением малого числа из прошлого поста, идея сводится к тому, что для начала мне нужно найти пару чисел, “большое” число a, и “малое” число b. Причём, число a “поглощает” число b, но число 2*a уже не будет поглощаться… Ещё раз: поскольку это поглощение основано на том, что при сложении числа выравниваются (представляются с одинаковыми экспонентами), малое число должно быть настолько малым, что б выровняться за правый край мантиссы. А если я умножу его на 2 (сдвину на разряд влево) оно учтётся пройдёт по последнему разряду мантиссы и учтётся.
Так же, я хочу числа с простым бинарным представлением, число a=1, число b…подсмотрим сюда, мантисса у нас 23 бита, т .е. я предполагаю, что нужно сдвинуть единицу направо на 24 разряда, иначе говоря мантисса у нас опять 1, а экспонента -24 (минус 24). Да нам удобнее для числа b использовать так называемую научную нотацию, да ещё и наполовину в 16ричной системе счисления…
Вот листинг, берем float т.к. он короче, и берем format т. к. он обещает “умный вывод”, с нулями только если они имеют смысл, и собираем всё с C++20:
#include <iostream>
#include <format>
int main()
{
float a = 1.0;
float b = 0x1.p-24;
std::cout << std::format("{}", a+b) << std::endl;
std::cout << std::format("{}", (a + b) + b) << std::endl;
std::cout << std::format("{}", a + (b + b)) << std::endl;
return 0;
}
Вывод будет:
1
1
1.0000001
То есть: во-первых, тройку чисел я нашёл, во-вторых, мы разобрались, что изначальная задача действительно имеет смысл, в-третьих, мы получили ответ на неё, а именно, нужно отсортировать от меньшего числа к большему (в силу ассоциативности слева направо и всех остальных выкладок).
#IT #job #c_plus_plus #math #weird #interview
Не надо плавать
В прошлых постах я довольно подробно расписал подводные камни работы с числами с плавающей точкой, которые моделируют дробные(рациональные) числа. И тут есть интересный момент: это не единственный вариант работы с такими числами (Википедия не даст соврать), я и сам уже упоминал это, но… в C++ их нет ни как базового типа, ни как класса в стандартной библиотеке. Зато, в C++ есть вызывающая много споров возможность перегружать операторы, что подталкивает нас попробовать создать так называемые числа с фиксированной точке “на коленке”, сделав свой класс и перегрузив (хотя бы часть) арифметических операторов.
Тут прежде, чем изливать тонны кода, давайте остановимся на основах: почему это возможно и как это сделать. Итак, язык нам предоставляет базовые integral types, обычно 1,2,4, 8 байтовые со знаком или без (ну уж точно на x86-64 платформе это так) и предоставляет нам арифметические операторы для этих типов. Рассмотрим базовые моменты работы арифметических операторов на примере типов uint8_t, int8_t:
• Сложение для uint8_t происходит по модулю 256 т.е. 1+2 = 3, но 1+255=0
• Сложение знаковых чисел происходит той же самой инструкций ассемблера, т.е. для CPU нет никаких отрицательных чисел, границы этого типа -128…+127
• Перемножение двух int8_t дает результат типа int16_t
• Частное от деления int16_t \ int8_t дает результат типа int8_t, остаток отбрасывается
А теперь основная идея (или трюк, если хотите), я могу взять переменную типа int8_t и мысленно сказать, что она хранит не целое число…а например, число четвертей, то есть мысленно поставить точку после двух левых разрядов. Давайте на примере десятичной системы: я возьму какие-то числа, например 3.14 и 2.71 и скажу – “у меня есть 314 сотых, а также 271 сотая”. Если меня попросят их сложить или вычесть это можно сделать, не выходя за нотацию сотых прямо сразу: 314 + 271 = 585, 314 – 271 = 43. Давайте попробуем умножить, 314*271 = 85094 эм...это точно в сотых? Нет, это точно не в них – правильно будет вот так 851 т.е. сдвинуть на 2 разряда вправо. А причём тут сотые, и какие-то четверти, которые я упоминал ранее? Четверти – это одни четвертые (богатый русский язык), для двоичной системы, это тоже самое, что сотые для десятичной.
В следующий раз понемногу начну показывать код.
#IT #job #c_plus_plus #math #weird #ToBeContinued
В прошлых постах я довольно подробно расписал подводные камни работы с числами с плавающей точкой, которые моделируют дробные(рациональные) числа. И тут есть интересный момент: это не единственный вариант работы с такими числами (Википедия не даст соврать), я и сам уже упоминал это, но… в C++ их нет ни как базового типа, ни как класса в стандартной библиотеке. Зато, в C++ есть вызывающая много споров возможность перегружать операторы, что подталкивает нас попробовать создать так называемые числа с фиксированной точке “на коленке”, сделав свой класс и перегрузив (хотя бы часть) арифметических операторов.
Тут прежде, чем изливать тонны кода, давайте остановимся на основах: почему это возможно и как это сделать. Итак, язык нам предоставляет базовые integral types, обычно 1,2,4, 8 байтовые со знаком или без (ну уж точно на x86-64 платформе это так) и предоставляет нам арифметические операторы для этих типов. Рассмотрим базовые моменты работы арифметических операторов на примере типов uint8_t, int8_t:
• Сложение для uint8_t происходит по модулю 256 т.е. 1+2 = 3, но 1+255=0
• Сложение знаковых чисел происходит той же самой инструкций ассемблера, т.е. для CPU нет никаких отрицательных чисел, границы этого типа -128…+127
• Перемножение двух int8_t дает результат типа int16_t
• Частное от деления int16_t \ int8_t дает результат типа int8_t, остаток отбрасывается
А теперь основная идея (или трюк, если хотите), я могу взять переменную типа int8_t и мысленно сказать, что она хранит не целое число…а например, число четвертей, то есть мысленно поставить точку после двух левых разрядов. Давайте на примере десятичной системы: я возьму какие-то числа, например 3.14 и 2.71 и скажу – “у меня есть 314 сотых, а также 271 сотая”. Если меня попросят их сложить или вычесть это можно сделать, не выходя за нотацию сотых прямо сразу: 314 + 271 = 585, 314 – 271 = 43. Давайте попробуем умножить, 314*271 = 85094 эм...это точно в сотых? Нет, это точно не в них – правильно будет вот так 851 т.е. сдвинуть на 2 разряда вправо. А причём тут сотые, и какие-то четверти, которые я упоминал ранее? Четверти – это одни четвертые (богатый русский язык), для двоичной системы, это тоже самое, что сотые для десятичной.
В следующий раз понемногу начну показывать код.
#IT #job #c_plus_plus #math #weird #ToBeContinued
👍1🔥1
Не надо плавать
Часть 2
Поскольку код вышел на Хабре, и более-того, комментаторы и я сам нашли довольно большое количество ошибок и переусложненных моментов, хотелось бы тут остановиться ещё раз на идее.
В языке C++ есть типы double и float, реализованные в соответствии со стандартом IEEE-754.
Знаменитая картинка из Википедии говорит о том, что мы храним отдельно знак, степень 2ки (экспоненту), и мантиссу – считай наши двоичные цифры. Тут хочется напомнить, что целые либо беззнаковые числа хранятся абсолютно иначе: нет ни отдельно знака, ни степени, по сути, хранится только само число.
Смысл статьи на Хабре и потуг предыдущего поста состоит в том, что можно взять целое число произвольного размера (но из тех, что нативно поддерживается компилятором) и сказать, что теперь я трактую n правых разрядов как значение идущее после точки – дробную часть числа, а остальные разряды как левую часть числа, вот пример для 8 битного числа где 2 младших разряда я отдаю под дробную часть 0000 1101, это тоже самое что 11.01 (2) = 3.25 (10) .
Соответственно, написанный код – всего лишь является отражением этой идеи.
#today #IT #c_plus_plus #math #habr #ToBeContinued
Часть 2
Поскольку код вышел на Хабре, и более-того, комментаторы и я сам нашли довольно большое количество ошибок и переусложненных моментов, хотелось бы тут остановиться ещё раз на идее.
В языке C++ есть типы double и float, реализованные в соответствии со стандартом IEEE-754.
Знаменитая картинка из Википедии говорит о том, что мы храним отдельно знак, степень 2ки (экспоненту), и мантиссу – считай наши двоичные цифры. Тут хочется напомнить, что целые либо беззнаковые числа хранятся абсолютно иначе: нет ни отдельно знака, ни степени, по сути, хранится только само число.
Смысл статьи на Хабре и потуг предыдущего поста состоит в том, что можно взять целое число произвольного размера (но из тех, что нативно поддерживается компилятором) и сказать, что теперь я трактую n правых разрядов как значение идущее после точки – дробную часть числа, а остальные разряды как левую часть числа, вот пример для 8 битного числа где 2 младших разряда я отдаю под дробную часть 0000 1101, это тоже самое что 11.01 (2) = 3.25 (10) .
Соответственно, написанный код – всего лишь является отражением этой идеи.
#today #IT #c_plus_plus #math #habr #ToBeContinued
👍1
А вот и она
Сюрприз-сюрприз! Обещанная в прошлый раз статья – уже вышла и набирает неплохое количество лайков. Вероятно, если лайков будет больше 30 – буду думать о продолжении. Вообще говоря, тема линейной алгебры и связанных численных алгоритмов столь обширна, что писать об этом можно почти бесконечно. Тут другой вопрос: сегодняшнюю статью можно охарактеризовать английским словом introductory, либо русским – введение: всё остальное будет существенно посложнее – найдёт ли это всё своего читателя? Изначальная задумка была перейти от элементарного алгоритма Power iteration к QR-методу, но в процессе работы над статьей я осознал, что результирующий объём был бы запредельным.
Кстати, забавный факт о моей памяти: только написав прошлый пост, я вспомнил, что изначально, до "линейки", я собирался писать статью/развернутый ответ на комментарий к одной из моих предыдущих статей и посту на Хабре – а то он выглядит "магически": есть какое-то соотношение и вот так оно работает, а что и почему не очень понятно. И уже код у меня написан для неё процентов на 70 и теорию я разобрал – собственно оттуда, по определенным причинам я пошёл почитать про алгоритмы поиска собственных значений...
И тут я попадаю в своего рода ментальную ловушку: для меня этот материал уже пройден и особого интереса не представляет – да, можно лишний раз поспекулировать о представлении вещественных чисел, да, можно подвести читателя к фундаментальной проблеме память/точность...но непонятно, а нужно ли. Всё это выглядит скорее забавным приколом нежели чем-то заслуживающим внимания.
#today #habr #flood #plans #math
Сюрприз-сюрприз! Обещанная в прошлый раз статья – уже вышла и набирает неплохое количество лайков. Вероятно, если лайков будет больше 30 – буду думать о продолжении. Вообще говоря, тема линейной алгебры и связанных численных алгоритмов столь обширна, что писать об этом можно почти бесконечно. Тут другой вопрос: сегодняшнюю статью можно охарактеризовать английским словом introductory, либо русским – введение: всё остальное будет существенно посложнее – найдёт ли это всё своего читателя? Изначальная задумка была перейти от элементарного алгоритма Power iteration к QR-методу, но в процессе работы над статьей я осознал, что результирующий объём был бы запредельным.
Кстати, забавный факт о моей памяти: только написав прошлый пост, я вспомнил, что изначально, до "линейки", я собирался писать статью/развернутый ответ на комментарий к одной из моих предыдущих статей и посту на Хабре – а то он выглядит "магически": есть какое-то соотношение и вот так оно работает, а что и почему не очень понятно. И уже код у меня написан для неё процентов на 70 и теорию я разобрал – собственно оттуда, по определенным причинам я пошёл почитать про алгоритмы поиска собственных значений...
И тут я попадаю в своего рода ментальную ловушку: для меня этот материал уже пройден и особого интереса не представляет – да, можно лишний раз поспекулировать о представлении вещественных чисел, да, можно подвести читателя к фундаментальной проблеме память/точность...но непонятно, а нужно ли. Всё это выглядит скорее забавным приколом нежели чем-то заслуживающим внимания.
#today #habr #flood #plans #math
Хабр
В поиске собственных значений (матриц)
Как найти собственные числа и собственные значения матрицы? Методы, излагаемые в курсе линейной алгебры, основанные на определении — применимы ли они к реальным данным? Существует ли простой алгоритм...
🔥2
Монстр
Вчера, глобально замедленный – локально ускоренный, YouTube, видимо, в качестве ответа на мой пост про необычные названия математических объектов, выдал мне в рекомендациях видео про Монстра – не буду писать, что это такое: лучше посмотрите видео или почитайте Википедию.
Конечно, я давно лелею мысли написать статью, посвященную или основанную на Теории групп, однако дело это непростое: давать одну теорию – зачем? – Во-первых, есть много "мест", где об этом можно почитать или посмотреть, во-вторых, я, конечно, что-то знаю, но, вероятно, в лучшем случае это половина знаний выпускника нормального матфака, посещавшего полноценные курсы алгебры. Соответственно – нужно найти алгоритм ссылающийся на группы. Пока что – кроме дискретного логарифма ничего в голову не приходит.
И, с одной стороны, это хорошая задача – можно рассматривать "простейшую" мультипликативную группу поля Галуа, оперируя только "числами", без полиномов, с другой стороны, очевидно, что дискретный логарифм применяется в криптографии, а это огромная область...можно по незнанию написать какую-то ерунду. Так что – это даже не план, а так – мысли вслух.
Вообще, история этой области шокирует, в обычном человеческом смысле этого слова, – как Галуа, трагически погибший в 20 лет, смог создать вот это всё? – Конечные поля их расширения, и вся та теория, относящаяся к теореме Абеля-Руффини. Вот о чём можно было бы снять кино, только кто в наши дни умеет это делать...
В процессе написания поста я осознал, что всё-таки Теорию групп я изучал не только в рамках самообразования – был у меня курс дискретной математики, где мы (зачем-то) решали задачи наподобие следующей: есть правильная пирамида (тетраэдр) её ребра (или вершины) могут быть выкрашены в следующие (какие-то) цвета, нужно найти число раскрасок с учётом всех возможных симметрий, иначе говоря, если пирамиду можно взять и покрутить совместив разные раскраски – это на самом деле одна раскраска. Как обычно, just in case, я просто оставлю тут ссылку.
#today #flood #humor #math
Вчера, глобально замедленный – локально ускоренный, YouTube, видимо, в качестве ответа на мой пост про необычные названия математических объектов, выдал мне в рекомендациях видео про Монстра – не буду писать, что это такое: лучше посмотрите видео или почитайте Википедию.
Конечно, я давно лелею мысли написать статью, посвященную или основанную на Теории групп, однако дело это непростое: давать одну теорию – зачем? – Во-первых, есть много "мест", где об этом можно почитать или посмотреть, во-вторых, я, конечно, что-то знаю, но, вероятно, в лучшем случае это половина знаний выпускника нормального матфака, посещавшего полноценные курсы алгебры. Соответственно – нужно найти алгоритм ссылающийся на группы. Пока что – кроме дискретного логарифма ничего в голову не приходит.
И, с одной стороны, это хорошая задача – можно рассматривать "простейшую" мультипликативную группу поля Галуа, оперируя только "числами", без полиномов, с другой стороны, очевидно, что дискретный логарифм применяется в криптографии, а это огромная область...можно по незнанию написать какую-то ерунду. Так что – это даже не план, а так – мысли вслух.
Вообще, история этой области шокирует, в обычном человеческом смысле этого слова, – как Галуа, трагически погибший в 20 лет, смог создать вот это всё? – Конечные поля их расширения, и вся та теория, относящаяся к теореме Абеля-Руффини. Вот о чём можно было бы снять кино, только кто в наши дни умеет это делать...
В процессе написания поста я осознал, что всё-таки Теорию групп я изучал не только в рамках самообразования – был у меня курс дискретной математики, где мы (зачем-то) решали задачи наподобие следующей: есть правильная пирамида (тетраэдр) её ребра (или вершины) могут быть выкрашены в следующие (какие-то) цвета, нужно найти число раскрасок с учётом всех возможных симметрий, иначе говоря, если пирамиду можно взять и покрутить совместив разные раскраски – это на самом деле одна раскраска. Как обычно, just in case, я просто оставлю тут ссылку.
#today #flood #humor #math
👍1
Когда-то, на одной из предыдущих работ, где трудоемкость задач оценивали в числах Фибоначчи, мои коллеги погрузились в глубокую дискуссию на тему: "'эта задача где-то между 5 и 8", а я был столь глубоко вовлечен, что подумал: "да поставьте уже 6 - это тоже число Фибоначчи, в каком-то смысле". В каком это смысле?🤨
В тот момент я понял, что любое натуральное число представимо суммой чисел Фибоначчи, перебрав в уме числа в районе первой 30-ки, я пришёл к выводу, что я (как всегда) прав. Ну ладно, точнее, я просто нашёл это.
Если немного задуматься: существуют и другие подобные последовательности, и все они содержат 1 (куда от неё деться? больше её нечем представить), 2 (по той же причине), а вот дальше идёт некий простор. Действительно, имея 1 и 2, можно представить 3, а можно взять его как очередное "базисное" число. Предположим, мы уже взяли 1, 2, 3 - ими можно представить числа до 6 включительно, поэтому возьмём 7. С помощью 1,2, 3, 7 можно уже представить все числа до 13 включительно: 8 = 7+ 1, 9 = 7+ 2, 10 = 7 + 3, 11 = 1 + 3 + 7, 12 = 2 + 3 + 7, 13 = 1 + 2 + 3 + 7. Думаю, принцип понятен.
Кстати, из подобного же принципа можно получить и двоичную систему: берем 1 и 2, далее, действуем максимально жадно: 4 мы представить не можем - берем его, имея 1, 2, 4 - не "добиваем" до 8-ки. Берем её и т.д. Если что: это так называемое условие полноты.
Поскольку я так и не смог найти приложения этим сакральным знаниям, я отнёс их к категории навязчивых мыслей и посчитал, что один из лучших способов избавиться от них - написать их на (почти) бумаге:) . Если серьёзно, то коли последовательность не образует позиционную систему (а все они не такие, кроме степеней двойки), то умножение в ней производить неудобно, хотя сложение и вычитание в системе Фибоначчи выглядят красиво.
#today #math #humor #Friday
В тот момент я понял, что любое натуральное число представимо суммой чисел Фибоначчи, перебрав в уме числа в районе первой 30-ки, я пришёл к выводу, что я (как всегда) прав. Ну ладно, точнее, я просто нашёл это.
Если немного задуматься: существуют и другие подобные последовательности, и все они содержат 1 (куда от неё деться? больше её нечем представить), 2 (по той же причине), а вот дальше идёт некий простор. Действительно, имея 1 и 2, можно представить 3, а можно взять его как очередное "базисное" число. Предположим, мы уже взяли 1, 2, 3 - ими можно представить числа до 6 включительно, поэтому возьмём 7. С помощью 1,2, 3, 7 можно уже представить все числа до 13 включительно: 8 = 7+ 1, 9 = 7+ 2, 10 = 7 + 3, 11 = 1 + 3 + 7, 12 = 2 + 3 + 7, 13 = 1 + 2 + 3 + 7. Думаю, принцип понятен.
Кстати, из подобного же принципа можно получить и двоичную систему: берем 1 и 2, далее, действуем максимально жадно: 4 мы представить не можем - берем его, имея 1, 2, 4 - не "добиваем" до 8-ки. Берем её и т.д. Если что: это так называемое условие полноты.
Поскольку я так и не смог найти приложения этим сакральным знаниям, я отнёс их к категории навязчивых мыслей и посчитал, что один из лучших способов избавиться от них - написать их на (почти) бумаге:) . Если серьёзно, то коли последовательность не образует позиционную систему (а все они не такие, кроме степеней двойки), то умножение в ней производить неудобно, хотя сложение и вычитание в системе Фибоначчи выглядят красиво.
#today #math #humor #Friday
🔥2