Сегодня исполняется 114 лет со дня рождения Конрада Цузе, пионера создания вычислительной техники, человека, которому сама судьба пыталась помешать двигать прогресс, но не помешала создать первый язык программирования высокого уровня, один из первых компьютеров и первую книгу по цифровой физике.Читать полностью »
Недавно на работе столкнулись с интересной ситуацией, о которой захотелось написать тут, потому что случай довольно интересный, хотя как и оказалось простой. На одном из агрегатов, управляемым контроллером от Allen Bradley Compact Logix L33ER, в контроллере постоянно сыпались предупреждения, а точнее даже минорный ошибки (Minor Faults) - которые на функциональность никак не влияют, но раздражают своим присутствием. В секунду по нескольку десятков таких ошибок без перерыва: Type 04 Program fault (Code 04) Arithmetic overflow. Result of an arithmetic instruction out of range, что переводится примерно как "Арифметическое переполнение. Результат арифметической инструкции вышел за предел."
В прошлой статье речь шла о том, как можно сложить массив из чисел типа double наиболее точно, то есть получить такую сумму, как если бы мы выполняли вычисления в рамках арифметики с бесконечной точностью, а затем один раз округлили бы результат. Был показан алгоритм, который эквивалентен применению типа данных double-double, в котором сложение происходит сразу в двух переменных: основная сумма и хвостик-погрешность. Опытные читатели сразу догадались, что сложение хвостиков-погрешностей также допускает по отношению к себе рекурсивное применение того же алгоритма, что приводит не к удвоенной, а к утроенной точности, и вообще, можно организовать каскад сложений произвольного размера, получая любую наперёд заданную точность расчётов, поэтому фактически в прошлой статье была показана предпосылка к так называемой «дробной длинной арифметике». Опытный программист без труда разберётся как её реализовать, ну а я обещал дать аналогичные фундаментальные основы для скалярного произведения и вычисления полинома в точке. Поскольку все базовые вводные слова уже были сказаны в двух предшествующих статьях, в этой будет меньше «воды» и «лишних», по мнению опытных математиков, сведений. Прошу под кат.
Больше не всегда значит лучше. Этой фразой можно четко описать соотношение умственных способностей существа с размером его мозга. Рекордсменом в мире животных является кашалот, чей мозг весит порядка 9 кг. Среди сухопутных существ этот титул заслужил индийский слон с 5 кг мозгов в своем распоряжении. Мозг страуса меньше его глазного яблока и весит 26 грамм. А вот мозг одного из самых интеллектуальных видов пернатых — серых попугаев — весит примерно 118 грамм, то есть около 22 % от общего веса тела. У человека же мозг в среднем весит 1.3 кг, при этом именно человек является венцом эволюции. Эти цифры наглядно демонстрируют, что дело не в количестве, а в качестве, так сказать.
Но что, если мозг существа весит всего лишь около 0.065 грамм и состоит из 950 000 нейронов (для сравнения, у человека их порядка 100 миллиардов)? Сможет ли такое существо показать интеллектуальные способности, способные удивить ученых? Еще как сможет, и этим существом является медоносная пчела, которая дружит с арифметикой. Сегодня мы с вами ознакомимся с исследованием математических способностей пчел, открывающее новые сведения для понимания их индивидуального, а не коллективного интеллекта. Помимо этого ученые стали лучше понимать соотношения веса и структуры мозга с уровнем интеллекта. Как ученые заставили пчел считать без калькулятора, как хорошо справились пчелы с поставленной задачей, и что ученым удалось выяснить? Ответы найдем в докладе исследовательской группы. Поехали.Читать полностью »
Рассмотрим следующую задачу. Найти период дроби 1/81. Уверяю, что для решения не потребуется ни калькулятор, ни деление столбиком. Для начала вспомним чему равно 81*(Период). Пусть длина периода n, тогда исходная дробь запишется как:
Перепишем данное представление в следующем виде:
Последнее выражение можно представить так:
Ну а теперь то соотношение, которое мы искали:
Для нашего случая это тождество будет следующим:
Разделим левую и правую часть на 9, получим:
Пока подготовка к московскому DotNext идёт полным ходом, мы открыли доступ к видеозаписям докладов с прошедшей летом конференции. По ссылке — полный плейлист, а под катом — топ-5 докладов по отзывам участников. Говоря «топ», мы не имеем в виду наши любимые доклады или выбор каких-то «экспертов» — лучшие отобраны на основе взвешенной оценки от 80% участников конференции. Как думаете, чьё выступление зрители оценили выше — перфоманс-эксперта Саши Гольдштейна или харизматичного Дино Эспозито?
Читать полностью »
Старинная запись на квитанции в уплате подати («ясака»). Она означает сумму 1232 руб. 24 коп. Иллюстрация из книги: Яков Перельман «Занимательная арифметика»
Ещё Ричард Фейнман в книге «Вы конечно шутите, мистер Фейнман!» поведал несколько приёмов устного счёта. Хотя это очень простые трюки, они не всегда входят в школьную программу.
Читать полностью »
В 2010 году по сообществу людей, изучающих теорию чисел, прошёл поразительный слух – и дошёл до Джареда Вайнштейна [Jared Weinstein]. Якобы какой-то аспирант из Боннского университета в Германии опубликовал работу, в которой 288-страничное доказательство теоремы из теории чисел ужато всего до 37 страниц. 22-летний студент Петер Шольце нашёл способ обойти одну из самых сложных частей доказательства, сопоставив теорию чисел и геометрию.
«Просто невероятно, что такой молодой человек смог сделать нечто настолько революционное,- говорит Вайнштейн, 34-летний специалист по теории чисел из Бостонского университета. – Это несомненный повод для уважения».
Математики из Боннского университета, присвоившие Шольце звание профессора всего два года спустя, уже знали о его экстраординарных умственных способностях. После публикации работы его начали замечать эксперты и по теории чисел, и по геометрии.
С того момента Шольце, которому сейчас 28, дорос до высокого положения уже в более широком математическом сообществе. Его называют "одним из самых влиятельных математиков мира", и "редким талантом, появляющимся раз в несколько десятилетий". О нём говорят, как о фаворите среди претендентов на Филдсовскую премию, одну из высочайших наград для математика.
Ключевому нововведению Шольце – классу фрактальных структур, названных им перфектоидными пространствами – исполнилось всего несколько лет, но оно уже ведёт к далеко идущим последствиям в области арифметической геометрии, в которой сливаются теория чисел и геометрия. Вайнштейн говорит, что работа Шольце была провидческой. «Он смог увидеть последствия до того, как те начали происходить».
Читать полностью »
Наверное, все знают, что при вычислениях с ограниченной точностью два математически эквивалентных выражения могут оказаться не равны друг другу. Например, следующее очевидное математическое равенство при вычислении в Haskell неожиданно оказывается ложным:
ghci> 3 * sqrt(24 ^ 2 + 16 ^ 2) == sqrt(72 ^ 2 + 48 ^ 2)
False
Причина такого нарушения в том, что выражения в этом равенстве вычисляются лишь приближенно:
ghci> 3 * sqrt(24 ^ 2 + 16 ^ 2)
86.53323061113574
ghci> sqrt(72 ^ 2 + 48 ^ 2)
86.53323061113575
ghci> sqrt(72 ^ 2 + 48 ^ 2) - 3 * sqrt(24 ^ 2 + 16 ^ 2)
1.4210854715202004e-14
Различие здесь только в последнем (четырнадцатом!) знаке после запятой, но этого уже достаточно, чтобы сравнение оказалось ложным.
Несмотря на то, что эта проблема хорошо известна, программисты уделяют ей мало внимания. Во-первых, считается, что сравнения такого рода возникают только в узкой области численных методов, а во-вторых, что нарушение равенства происходит крайне редко. Как оказалось, и то и другое не совсем верно. Приведенный случай возник, когда мне понадобилось реализовать функцию вычисления длины вектора с целочисленными координатами. При этом для модульного тестирования используются средства пакета QuickCheck, который довольно быстро нашел случай нарушения инварианта масштабирования для длины вектора. Замечу, что это далеко не единственный инвариант, нарушение которого было обнаружено при тестировании.
Возникает вопрос: как проще всего описать проверку приблизительного равенства двух чисел, полученных в результате вычислений с ограниченной точностью? Для решения этой задачи в Haskell достаточно определить еще один оператор сравнения (скажем, ~=), который используется так же, как и обычный оператор равенства. Предлагаю рассмотреть реализацию такого оператора, которую можно оформить в виде достаточно простого модуля Circa.
Недавно на Хабре появилась удивительная статья «Папа, а почему на ноль делить нельзя?», которая собрала массу не менее удивительных комментариев.
Детские вопросы обычно очень сложны («Почему небо ночью темное?», «Почему яблоки падают на землю?») и у взрослых обычно не хватает времени, чтобы их доходчиво объяснить. Да и не всегда взрослые знают ответ на эти вопросы.
Однако, вопрос о делении на ноль ни разу не относится к числу сложных вопросов, и для меня остается загадкой, почему с ним возникает столько проблем. Наверное, виной тому какие-то изъяны в методике преподавания математики в средней школе, в трудностях перехода от изучения арифметики к изучению буквенной алгебры и свойств элементарных функций.
Самые серьезные сомнения появляются, я думаю, после изучения рациональных чисел, когда для любого числа x, кроме нуля, вводится понятие обратного числа 1/x, и графика гиперболы y(x)=1/x.
Очевидно, что при делении 1 на очень маленькие числа появляются очень большие числа, и чем меньше мы берем x, тем больше становится 1/x. Почему же мы не можем сказать, что 1/x=∞ — есть некоторое число?
Алгебраическое возражение против этого состоит в следующем. Предположим, что ∞=1/x является числом. Тогда на это число должны распространяться все правила, которые имеют место быть для обычных чисел. В частности, с одной стороны должно быть верно соотношение 0⋅∞=1, а с другой стороны поскольку 0=1−1 должно быть выполнено 0⋅∞=1⋅∞−1⋅∞=0. Таким образом, имеем 1=0, а из этого уже следует, что все числа равны между собой и равны нулю. В самом деле, поскольку для любого числа x верно 1⋅x=x, то 1⋅x=0⋅x=0.
«Ну разве это не полная чушь?» — спросим себя, добравшись до этого места.
Разумеется, это полная чушь, если мы говорим об обычных числах. Но я недаром подчеркнул выше слово «правила». К ним мы вернемся чуть позже, после рассмотрения арифметического возражения против деления на ноль, и поможет нам в этом фасоль.
Вернемся в те времена, когда не было ни компьютеров, ни калькуляторов, ни логарифмических линеек, и поставим перед собой задачу разделить некоторое случайное число, например, на 5.
Для этого берем чашу с фасолью, символизирующую натуральный ряд, и высыпаем из нее какое-то количество зерен на разлинованный лист бумаги:
Тем самым, мы установили делимое на нашем бобовом калькуляторе.