Тема: math


Since solving some Euler project’s task, I have the Roman-Arabic numerals converter.

Recently I found the way to use it just for fun!

Check, how the multiplication table up to 100×100 does look like, colored by length of the corresponding roman number (in symbols):


What about the Ulam spiral?


And, it could not be complete without the Peano curve:

Tags: , , , , | Make a comment


Once upon a time… Fifteen years ago my friend Gevor and I (among a lot of other people) had the computer graphics course at Moscow State University. Mentors gave us a freedom of choice so we could develop almost any computer graphics algorithm.

We decided to choose a raytracing approach with several light sources, shadows, textures, mirrors, semitransparent objects and etc. Our ultimate goal was to render the Klein bottle’s 3D projection. We used the triangulation of the “Klein bagel”, the special parameterization of the Klein bottle shaped like a “figure-8″ torus with a 180 degree “Möbius” twist.

We were going to compile a short FLI-movie from a sequence of BMP-formatted frames. Our renderer was developed as a cross-platform pure C code, and we had several hectic weeks trying to catch the deadline. We spent 20+ days to build the single 40 second 320×200 movie.

* * *

The other day my old friend, Gevor, visited me, and we recalled that funny pastime.
Just for fun I dug up that ancient piece of code. We compiled it promptly under my Win7x64 with cygwin’s gcc and build this hires movie:



No code modifications were done except quality and screen resolution constants correction.

Tags: , , , , , , | Make a comment


How would look a 3D structure with layers corresponding to the cascade of generations of Conway’s Life?
 I thought that the simplest way to check it is to build some visualization environment and look at the actual results:

Conway Tree teaser

The interested readers are able to:

Tags: , , , , , , , , , | Make a comment


Just returned from SIGIR 2013 @ Dublin.

Nice place, clever people, lots of impressions and ideas.

Tags: , , , , | Make a comment


How do you think a one-dimensional Wolfram’s automata will look like, if we map it into Peano (Hilbert) curve?

Have no idea? Me too. So I decided to check it out:

I could have done this in a hour or so using python, but I had never sought for easy ways, so I tried to make the online interactive visualization.

It took a dozen of nights and a lot of nerve, considering the fact I didn’t mess with clientside development for ten years, and looks like it became even much more chaotic since then. But now I know some kung fu.

Tags: , , , , , | Make a comment


A year ago, Stephan Rafler from Germany published a paper about the continuous generalization of Conway’s Game of Life:

Actually, it’s more of an approach rather than a strict set of rules; so, there is enough space for experiments. Among other types of such systems’ behaviour, gliders, tubes and some kind of carousels were discovered. A lot of videos of various simulations can be found at the author’s youtube-channel, and the emulation software itself is available there (including the sources).

In addition:

Tags: , , , , , | Make a comment


Pat Ashforth and Steve Plummer, the couple from UK, run a nice site, WoollyThoughts, dedicated to the “mathematical knitting”:

Among other things, there are some knitted optical illusions, flexagons, math puzzles and fractals.

Sarah-Marie Belcastro, US, runs a similar site, The Home of Mathematical Knitting, with a more serious mathematical bias — she has some knitted projective planes, hyperbolic surfaces and even the hat in the form of Klein bottle. Also, she provides an extensive collection of links to other sites and resources on this topic.

And Jana from Germany knits different patterns based on Escher’s works:


Tags: , , , , , | Make a comment


Daniel Sýkora — крутой дядька из Чехии, специализирующийся в том числе на алгоритмах для классической мультипликации. Собственно, на его странице собраны его (+соавторов) же разнообразные статьи с описанием различных алгоритмов и инструментов для компьютерной обработки рисунков. В том числе:

* Автоматическое “объемное” текстурирование:

* Реалистичная деформация нарисованных плоских изображений:

* Быстрое создание осмысленных слоёв и придание объема плоскому изображению:

Ну, и много всякого прочего.

Tags: , , , | Make a comment


Нашел страничку, где собрано на данный момент около 90 известных доказательств равенства и неравенства P и NP (включая несколько доказательств невозможности доказать равенство или неравенство).
Страничка пополняется и содержит, по возможности, прямые ссылки на работы.

Недолго думая, нарисовал график, иллюстрирующий, в каком году каких доказательств было больше:

В этом году P=NP явно не дотягивает, но еще не вечер :)

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

Tags: , , , | Make a comment


В начале июля всплыл отличный проект GraphChi, которой может сильно облегчить жизнь исследователям, работающим с большими объемами информации.

Авторы предлагают подход, позволяющий гонять на обычном десктопе обработку больших графов с эффективностью, сопоставимой с работой среднего кластера. Так, три итерации расчёта по этому методу PageRank-а над графом из 1.5 миллиардов ребёр на Mac Mini с SSD-диском заняли 13 минут (сравнить Spark-кластером из 50 машин, где эта же задача заняла 8.1 минуты).

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

Не очень понятно, сколько в таком режиме протянет обычная SSD-шка, но сама идея выглядит очень изящной.

Сама система (с несколькими уже готовыми примерами применения, типа PageRank, Community Detection, etc) доступна в исходном коде на C++ здесь. Кроме того, есть её частичный порт на Java, он лежит тут. Жду, когда кто-нибудь сподобится переписать на питоне ;)

Tags: , , , , | Make a comment