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

Вычислительный кластер Google Compute Engine за 121 день на 25 виртуальных машинах рассчитал наибольшее количество цифр в числе пи, установив новый мировой рекорд: 31,4 триллиона знаков после запятой. Это первый раз, когда для расчёта числа пи такой величины использовалось общедоступное облачное программное обеспечение.

Рекорд будет записан на имя Эммы Харуки Ивао (Emma Haruka Iwao) из подразделения высокопроизводительных вычислений в Google. Именно она использовала инфраструктуру Google Cloud для вычислений. Предыдущий мировой рекорд был установлен Питером Трубом в 2016 году, он рассчитал число до 22,4 триллиона цифр на специально сделанном сервере, который тоже спонсировал работодатель.

Вместо эпиграфа.

Больше всего лайков собирают «котики». Можно ли это считать признаком эпидемии токсоплазмоза?



В 1636 году, некий француз, Пьер де Ферма, по образованию и профессии юрист, написал трактат «Введение к теории плоских и пространственных мест», где изложил то, что сейчас называется аналитической геометрией. Его работа никого не заинтересовала и он, выражаясь на современном сленге, был отправлен в «игнор», что задержало развитие математики на 70 лет, пока работами Ферма не заинтересовался Эйлер.

С 1856 по 1863 год австрийский монах Грегор Иоганн Мендель проводил опыты на горохе в монастырском саду и открыл основные законы современной генетики, известные нам как «Законы Менделя».

8 марта 1865 года Мендель опубликовал результаты своих опытов. Но работа не вызвала интереса у профессионалов. Менделя тоже отправили в «игнор».

Только в начале XX века профессионалы поняли важность сделанных им выводов. Правда, для этого им пришлось заново открыть уже выведенные Менделем законы наследования.

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

Привет, Хабр! Представляю вашему вниманию перевод статьи "Removing a recursion in Python, part 1" автора Эрика Липперта (Eric Lippert).

На протяжении последних 20 лет я восхищался простоте и возможностям Python, хотя на самом деле никогда не работал с ним и не изучал подробно.

В последнее время я присмотрелся к нему поближе — и он оказался действительно приятным языком.

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

У того, кто в детстве не писал на Прологе — нет сердца, а у того, кто пишет на нём сегодня — нет мозгов. (оригинал)

Если вас всегда терзали мучительные сомнения — что за фигня это Логическое Программирование (ЛП) и вообще зачем оно нужно? То это статья для вас.

Можно по-разному разделить языки программирования на группы (часто их называют парадигмами программирования), например, вот так:

• структурное: программа разбивается на блоки — подпрограммы (изолированные друг от друга), а основными элементами управления являются последовательность команд, ветвление и цикл.
• объектно-ориентированное: задача моделируется в виде объектов, которые отправляют друг другу сообщения. Объекты обладают свойствами и методами. Абстракция. Инкапсуляция. Полиморфизм. Ну в общем, все в курсе.
• функциональное: базовым элементом является функция и сама задача моделируется в виде функции, а, точнее, чаще всего в виде их композиции, если f(.) и g(.) — это функции, то f(g(.)) — это их композиция.
• логическое: вот тут, как правило, начинается феерия — если про первые три написаны сотни статей, книг, обзоров, презентаций и учебников, то здесь мы в лучшем случае видим что-то про Prolog и разработки времён Pink Floyd и Procol Harum (ну хоть с музыкой им тогда повезло) и на этом история заканчивается.

Вот эту оплошность я и собираюсь сегодня исправить.

Важнейший тезис этой статьи:

Логическое программирование != Prolog.

И вообще последний вам скорее всего не нужен. А вот первое вполне может быть.

Структура статьи:

• Что такое Пролог и почему он вам скорее всего не нужен
• Зачем оно надо, или краткое введение в Answer Set Programming
• Решаем задачи на ASP
• Комбинаторная оптимизация
• Вероятностное ЛП: ProbLog
• ЛП на классической логике FO(.) и IDP
• Sketched Answer Set Programming
• Экспериментальный анализ
• Тестирование и корректность программ
• Заключение

Мысль о том, что в разработке любой более-менее сложной бизнес-логики приоритет должен отдаваться композиции объектов, нежели наследованию популярна в среде разработчиков программных продуктов самых разных типов. На очередной волне популярности функциональной парадигмы программирования, запущенной состоявшимся успехом ReactJS, разговоры о преимуществах композиционных решений пришли и во фронтенд. В данном посте есть немного раскладки по полкам теории о композиции объектов в Javascript, конкретный пример, его разбор и ответ на вопрос сколько стоит смысловая элегантность для пользователя (спойлер: немало).


Василий Кандинский — «Композиция X»

Предлагаем вашему вниманию перевод статьи, посвящённой рассмотрению используемых в программировании моделей памяти.

Сегодня в программировании доминируют шесть основных моделей памяти (не путать с моделями памяти Intel 8086). Три из них проистекают из трех исторически наиболее важных языков программирования 1950-х годов — COBOL, LISP и FORTRAN, а остальные связаны с тремя исторически важными системами хранения данных: магнитная лента, иерархическая файловая система в Unix-стиле и реляционная база данных.

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

Научная статья опубликована в журнале Communications of the ACM, октябрь 2018, том 61, номер 10, стр. 68−77, doi: 10.1145/3230627

В феврале 2017 года со взлётной площадки «Боинга» в Аризоне поднялся вертолёт с обычным заданием: облёт ближайших холмов. Он летел полностью автономно. Согласно требованиям по технике безопасности Федерального управления авиации США, пилот не прикасался к органам управления. Это был не первый автономный полёт AH-6, которого в компании называют Беспилотной Птичкой (Unmanned Little Bird, ULB). Он так летает уже много лет. Однако на этот раз посреди полёта вертолёт подвергся кибератаке. Бортовой компьютер атаковало вредоносное программное обеспечение видеокамеры, а также вирус, доставленный через заражённую флэшку, которую вставили во время техобслуживания. Атака поставила под угрозу некоторые подсистемы, но не смогла повлиять на безопасную эксплуатацию воздушного судна.

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

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

Внимание: просто рассматривать мой код, равно как и просто читать эту статью с чашкой чая в руке, смысла не имеет. Эта статья рассчитана на то, что вы возьмётесь за клавиатуру и напишете ваш собственный движок. Он наверняка будет лучше моего. Ну или просто смените язык программирования!

Итак, сегодня я покажу, как отрисовывать подобные картинки:

Если вы открыли данную статью, то наверняка уже слышали о кватернионах, и возможно даже используете их в своих разработках. Но пора подняться на уровень выше — к бикватернионам.

В данной статье даны основные понятия о бикватернионах и операции работы с ними. Для лучшего понимания работы с бикватернионами показан наглядный пример на Javascript с использованием Canvas.

В соседнем посте была приведена интересная задача, условие которой звучит следующим образом:

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

На ближайшее время позволим себе абстрагироваться от точных численных значений и положим вероятность того, что бриллианты зашиты, равной p, а количество стульев — n.

Хотите узнать правильное решение этой задачи? Добро пожаловать под кат!

Простое объяснение простоты

КДПВ с областями, которые нам придется посетить, чтобы ответить на ГЛАВНЫЙ вопрос.

Предисловие

Я часто слышал совет: сделай проще.

А что значит простой? Когда мы говорим, что объект X — простой, каковы наши ожидания от X? Когда мы говорим, что какая-то вещь проще чем другая — как мы это оцениваем?

Что проще:
“Небольшое предложение из пяти слов” или слово “Дезоксирибонуклеиновый”?
“6*5” или “481”?

Или так:
У вас есть экран настроек. Пять пунктов из них относятся к графике, другие пять к уведомлениям. Надо ли вам создавать отдельные пункты «графика» и «уведомления» в основном меню? Или оставить все 10 пунктов на одном экране? Что будет проще для пользователя?

Работа Александра Смита по гипотезе Голдфелда раскрыла фундаментальные свойства эллиптических кривых

Две эллиптические кривые демонстрируют странности концепции ранга. Кривая слева описывается уравнением y² = x³ + 1, проходит только через пять рациональных точек и имеет ранг 0. Кривая справа описывается уравнением y² = x³ + 8, проходит через бесконечное число рациональных точек, и имеет ранг 1.

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

Эллиптические кривые кажутся чем-то экзотическим, однако это непримечательные геометрические объекты, не сложнее прямых, парабол или эллипсов. В своей работе, опубликованной в онлайне в прошлом году, Алексадр Смит доказал гипотезу сорокалетней давности, касающуюся фундаментальной особенности эллиптических кривых, ранга. Смит доказал, что из определённого семейства кривых, имеющих одну характеристику, половина имеют ранг, равный 0, а половина – 1.

"No matter how hard you try, you can't make a racehorse out of a pig. You can, however, make a faster pig" (комментарий в исходном коде Емакса)

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

Во второй части серии статей об интерпретаторах байт-кодов я на примере небольшой стековой виртуальной машины ПВМ («Поросячья Виртуальная Машина») постараюсь показать, что не всё потеряно для трудолюбивых поросят с амбициями и что в рамках (в основном) стандартного C вполне возможно ускорить работу таких интерпретаторов по меньшей мере в полтора раза.

Большинство парадигм программирования, которые мы используем сегодня, были впервые математически изучены в 1930-х годах с использованием идей лямбда-исчисления и машины Тьюринга, которые представляют собой варианты модели универсальных вычислений (это формализованные системы, которые могут выполнять вычисления общего назначения). Тезис Чёрча-Тьюринга показал, что лямбда-исчисление и машины Тьюринга функционально эквивалентны. А именно, речь идёт о том, что всё, что можно вычислить с использованием машины Тьюринга, можно вычислить и с использованием лямбда-исчисления, и наоборот.

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

Будем сочетать теорию с практикой — покажем, что улучшение энтропии случайных последовательностей возможно, после чего посмотрим исходные коды, которые это делают.

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

В погоне за качественными случайными числами люди изобретают весьма остроумные приспособления (см. например здесь и здесь). В принципе, весьма неплохие источники случайности встроены в API операционных систем, но дело серьёзное, и нас всегда немножко гложет червячок сомнения: а достаточно ли хорош тот ГСЧ, который я использую, и не подпорчен ли он… скажем так, третьими лицами?

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

newtype Foo a = Bar a
newtype Id = MkId Word

Типичные вопросы новичка

В чём же отличие от data типа данных?

data Foo a = Bar a
data Id = MkId Word

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

Да это ничего не значит для меня… Буду использовать data
Не, ну в конце-концов, всегда можно включить расширение -funpack-strict-fields :) для строгих(не ленивых) полей или указать прямо

data Id = MkId !Word

Всё же сила newtype не ограничивается лишь эффективностью вычислений. Они значительно сильнее!

Я сегодня изучал индекс TIOBE, как делаю часто, и как часто делает большинство из тех профессиональных программистов, которых я знаю. Он претендует на измерение популярности языков программирования в мире, а его график изменения популярности со временем рассказывает простую историю: Java и C с незапамятных времён остаются королями языков с большим отрывом.

Но, погодите-ка, давайте не так быстро. Конкурирующий список PYPL Index (PopularitY of Programming Languages) говорит, что королями являются Python и Java, а C (учитываемый, внезапно, совместно с C++) находится где-то в глубине списка. Что происходит?

Просто у двух этих списков очень разные методологии подсчётов. Однако их объединяет одно – спорность их методологий, если учитывать, что их целью является измерение популярности языков программирования. TIOBE измеряет просто количество запросов в поисковике. PYPL измеряет, как часто люди гуглят обучающие материалы по тому или иному языку.

Отрывок из книги "The End of Average" Тодда Роуза


В начале 1950-х американцы измерили тела более 4000 пилотов по 140 характеристикам, чтобы спроектировать идеальную кабину для среднего пилота

В конце 1940-х у американских военно-воздушных сил была серьёзная проблема: пилоты теряли контроль над самолётами. Тогда наступала эпоха реактивных двигателей, так что самолёты стали более быстрыми и сложными в управлении. Но катастрофы случались так часто и на таком количестве разнообразных самолётов, что ВВС США столкнулись с реальной проблемой спасения жизней. В худшее время разбивалось до 17 пилотов за день.

«Это самое глубокое эссе, которое я видел относительно философии науки; на самом деле, оно важно для всего нашего понимания мысли, познания или реальности.»

Пролог

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

Человек, насколько мы знаем, всегда задавался вопросом о себе, мире вокруг и смысле жизни. Во множестве мифов повествуется о том почему и как Бог или боги создали человека и вселенную. Это теологические объяснения. Их отличительная черта — нет смысла спрашивать почему вещи таковы, как они есть, если боги создали их такими.

Философия возникла тогда, когда человек задался вопросом о мире вне этих теологических рамок. Например, мир древние философы представляли как сочетание земли, огня, воды и воздуха. Без сомнения их убеждали в том, что мир создан богами и не нужно беспокоиться по этому поводу.

Из этих ранних попыток объяснить мир постепенно возникла философия, также как и современная наука. Не то чтобы наука объясняет «почему» вещи таковы, как они есть — гравитация не объясняет «почему» предметы падают, но наука дает нам столь детальное объяснение «каким образом» это происходит, что у нас появляется чувство, будто мы знаем «почему». Давайте проясним; море связанных между собой фактов позволяет науке сказать «почему» вселенная именно такая.

Наука в программировании — быль или реальность? Сколько её в языках и почему идут холивары о приемуществах одних языков над другими? Если интересно — прошу под кат.