Как стать автором
Обновить

Методы вычисления мультиномиальных коэффициентов

Программирование *Алгоритмы *C# *
Однажды, пролистывая популярный Q&A по математике (math.stackexchange.com), я обнаружил вопрос про расчет мультиномиальных коэффициентов и он меня заинтересовал. На заметку, для тех, кто не знает что это такое, существует статья в википедии. Итак, нужно вычислить следующее выражение:



Казалось, зачем на хабре выкладывать решение такой простой задачи? Ответ заключается в том, что самый простой наивный способ, заключающийся в перемножении факториала суммы с последующим делением его на произведение факториалов, не подойдет из-за того, что промежуточные вычисления выйдут за разрядную сетку типа uint и даже ulong, хотя результат может оказаться в пределах значений этих типов. Мне понравилась эта задача, и я сразу же сел за ее решение и придумал три способа. Остальные два способа я позаимствовал из других ответов. Итак, статья будет об описании и сравнении всех реализованных мною методов на C# под .NET.
Читать дальше →
Всего голосов 41: ↑36 и ↓5 +31
Просмотры 13K
Комментарии 12

Невычислимые функции на примере Busy Beaver Game

Высокая производительность *Алгоритмы *Математика *

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


В этой статье я предлагаю заглянуть за границы возможностей компьютеров и рассмотреть чего же они не могут. И почему. Алан Тьюринг еще в 30-е годы обозначил невозможные для компьютера задачи.

Читать дальше →
Всего голосов 26: ↑26 и ↓0 +26
Просмотры 19K
Комментарии 14

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

Блог компании VK Информационная безопасность *Алгоритмы *Математика *


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

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

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

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

Добро пожаловать в кроличью нору без дна.
Читать дальше →
Всего голосов 48: ↑45 и ↓3 +42
Просмотры 34K
Комментарии 17

Создание статической библиотеки на С++ для работы с большими числами

Блог компании RUVDS.com C++ *Visual Studio *
Tutorial

Я всегда слышал, что с библиотеками в С++ что-то не так, как и с ограничением максимального целочисленного значения, да и вообще то, что язык сложный и непонятный. Что же, сегодня, мы начнём писать собственную библиотеку больших чисел, полностью своими руками c 0, и узнаем, так ли страшен С++, как его малюют?

Если вы не разбираетесь в С++, не переживайте, эта статья имеет нулевой порог вхождения. Мы начнём с лёгкого, но вы даже не заметите, как начнёте разбираться в более сложных и непонятных, на первый взгляд, вещах. Главное, писать код логично. Думаю, данная статья будет интересна не только начинающим, ведь я постарался затронуть достаточно много тем. (для старожилов: моя цель не сделать оптимизирование или быстрее, а показать, что С++ не такой уж и сложный язык программирования. И да, я знаю, что существуют другие библиотеки, которые делают это быстрее и лучше. И да, было бы круче, если бы мы использовали булевую алгебру. И да, С++ про вечную оптимизацию, но это статья не про это. Спасибо.)

За сегодня мы узнаем, что такое: Перегрузка функций/конструкторов, прототипы функций, обработка исключений, пространство имён, псевдонимы типов, заголовок.h, как пользоваться отладчиком и как писать продвинутые/красивые комментарии. Пристёгивайтесь, будет безумно интересно.
Читать дальше →
Всего голосов 49: ↑35 и ↓14 +21
Просмотры 9.8K
Комментарии 52