I've been working on computational number theory for my book and recently wrote a few new articles on:

• calculating modular inverse using binary exponentiation and extended Euclidean algorithm (spoiler: Euclid wins on average);
• Montgomery multiplication and fast modulo / division / divisibility checks for when the divisor is constant (which can often be used to speed up modular arithmetic by 5-15x);
• how to use them in various factorization algorithms (upd: fixed link) (writing a 3x-faster-than-state-of-the-art implementation of Pollard's algorithm in the process).

This is largely inspired by Jakube's tutorials and Nyaan' library implementations. Thank you!

If someone is interested, I may or may not try to optimize the sieve of Eratosthenes next: I believe it is possible to find all primes among the first $$$10^9$$$ numbers in well under a second.

Tutorial: https://en.algorithmica.org/hpc/algorithms/matmul/

A version you can submit on CodeForces (it is optimized for a specific CPU that is very different from that of CF, so the speedup is smaller): https://github.com/sslotin/amh-code/blob/main/matmul/self-contained.cc

These blocking/vectorization techniques can also be applied to some dynamic programming algorithms, such as the Floyd-Warshall ("for-for-for") algorithm. Do you know any similar DP problems where the number of operations is larger than the number of states?

https://en.algorithmica.org/hpc/data-structures/b-tree/

As promised, I wrote a new tree data structure.

https://en.algorithmica.org/hpc/data-structures/segment-trees/

I wrote a SIMD-friendly segment tree ("wide segment tree") that is up to 10x faster than the Fenwick tree and the bottom-up segment tree:

The article also explains in detail how all the other popular segment tree implementations work and how to optimize them (fun fact: the Fenwick tree can be made 3x faster on large arrays if you insert "holes" in the array layout and make it ~0.1% larger). The article is long but hopefully accessible to beginners.

I only focused on the prefix sum case (partially to make the comparison with the Fenwick tree fair). While I have some ideas on generalizing it to more complex operations, and I will probably add I've added a separate section on implementing other operations, I highly encourage the community to try to efficiently implement mass assignment, RMQ, lazy propagation, persistency, and other common segment tree operations using wide segment trees.

https://en.algorithmica.org/hpc/data-structures/s-tree/

I announced this article a while ago but finally got to finish it just now.

Planned follow-ups: a 10-20x faster segment tree, std::priority_queue, and std::set.

I've got an interesting math problem.

Here is a binary search variant that picks the element to compare against at random instead of always picking the middle one:

int lower_bound(int x) {
    int l = 0, r = n; // [l, r]
    while (l < r) {
        int m = l + rand() % (r - l); // <- note that r is never picked because there's no point
        if (a[m] >= x)
            r = m;
        else
            l = m + 1;
    }
    return l;
}

Assuming that the keys and queries are also drawn independently at random, as $$$n \to \infty$$$, how many times more comparisons does the random binary search perform compared to the normal one?

Edit: the binary search used to return a value instead of index. This is not correct if the the lower bound doesn't exist.

Hi everyone! I'm writing a book on performance engineering, and a few days ago, I finished a draft of one of its main crown jewels: the SIMD programming chapter.

The main findings that are published:

• You can compute array sums and other reductions such as the minimum 2x faster than std::accumulate or an auto-vectorized loop would.
• You can sometimes copy and assign memory 2x faster than memcpy and memset respectively.
• You can search array elements 10x times faster than std::find or manually.
• You can count a value in an array 1.5x faster than std::count or manually.
• You can calculate population counts of large vectors ~2x faster than with the intrinsic.
• You can filter arrays 6-7x faster, which translates to e. g. a 6-7x faster quicksort (to be published).
• You can calculate the index of the minimum element ~10x faster than std::min_element or manually.
• UPD: you can calculate the prefix sum of an array ~2.5x faster than std::partial_sum or manually.

All speedup numbers are architecture-specific and may be different (usually larger) on CodeForces servers.

Enjoy — and as always, I'm happy to hear any comments and suggestions.

Hi everyone!

I'm writing a book about performance engineering: the art of optimizing algorithms beyond just asymptotic complexity.

The book walks through the main CPU optimization techniques such as caching, SIMD and pipelining while exploring many large case studies where we speed up some classic algorithm or a data structure, closely matching or even improving on the state-of-the-art.

You will probably not learn a single asymptotically faster algorithm there, but it will help you not to get TL when you are supposed to get AC, and sometimes get AC when you are supposed to get TL.

Among the stuff that you are probably most interested in:

• A version of segment tree that can compute prefix sums in 2ns plus the time of the slowest memory read if the array doesn't fit in L2 cache (is larger than ~2^16).
• An implementation of GCD that works 2-3 faster than std::gcd.
• A 4-7x faster binary search (I wrote about it before)
• Integer factorization taking ~0.5ms per 60-bit integer.
• Argmin at the speed of memory (~$$$3 \cdot 10^{10}$$$ integer / float elements per second)
• An algorithm for parsing series of integers ~2x faster than scanf("%d") does.
• An implementation of BLAS-level matrix multiplication that looks like 8 "for" loops wrapping a one-liner and works ~100x faster than the naive "for-for-for" one, and a similar ~50x implementation of the Floyd algorithm.

I've only recently finished the research stage and I'm now writing it all up. I've already completed ~120 pages, which is ~30% of what I intend to. I plan to finish a new article every 2-3 days and post any relevant updates here on CodeForces and on my revived twitter.

I'm not sure what I'm going to do with the book when I'm done, but it is definitely going to be available online for free.

Happy to hear any comments and suggestions.

cc: dmkz, MrDindows

Привет!

Для тех, кто впервые слышит, algorithmica.org — это живущий на гитхабе сайт со статьями про олимпиадную (и не только) информатику, который поддерживается преподавателями и студентами Tinkoff Generation и другими причастными.

Как некоторые могли заметить, недавно сайт обновился: статьи были зарефакторены в формат книги и стали более взаимосвязанными; мы переехали на более мощный движок и сделали небольшой редизайн; добавили встроенный редактор для коротких правок, и вообще сделали жизнь контрибьютеров проще.

Сейчас мы занимаемся тем, что доводим до готовности и публикуем под открытой лицензией остальные материалы наших курсов, а также «эвакуируем» с согласия авторов статьи с e-maxx.ru и других уже не обновляемых ресурсов — и здесь нам бы очень пригодилась помощь сообщества.

Поэтому хочу воспользоваться возможностью и напомнить, что с 1 по 31 октября проходит Hacktoberfest. По его правилам, если вы в течение месяца сделаете хотя бы 4 осмысленных правки (пулл реквеста, не обязательно в один проект), то помимо того, что их прочитают тысячи или десятки тысяч человек, вы ещё и сможете получить клёвую футболку (либо посадить дерево, если она вам не нравится).

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

Возможно, важная деталь — футболки получают не все, а только первые 50000 (по пока непонятному критерию). У меня в начале октября не очень много времени, но я постараюсь оперативно отвечать на вопросы и реагировать на прочий фидбек в комментариях тут, в issue к репозиторию или в телеграм.

Всем привет!

В Tinkoff Generation этой зимой будет проходить серия семинаров, посвященных High Performance Computing — тому, как писать высокопроизводительные программы, оптимальные не только асимптотически, но и в плане использования разных вычислительных ресурсов (кэши, SSE-инструкции, многоядерные процессоры, GPU, кластеры, etc.).

Спецкурс в основном ориентирован на тех, кто уже завершил или завершает свою «олимпиадную карьеру» и хочет дальше развиваться в этом же направлении, но и в контексте олимпиад большинство тем тоже будет полезно.

Примерная программа:

1. Memory-Bound Algorithms
2. Instruction-Level Parallelism
3. Single Instruction, Multiple Data
4. Concurrency
5. Parallelism
6. GPU Programming
7. Massively Parallel Algorithms
8. MapReduce
9. Cloud Computing

Пререквизиты (рекомендация):

• Алгоритмы уровня ≥B в олимпиадных школах / 1-2 курсов в вузах на сильных факультетах
• Желательно: архитектура компьютера, знание Linux
• C++, Python, русский и английский

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

Чат в Telegram: https://t.me/joinchat/FI6QYkfYU50ncTGzrvUL4Q
Тут будут записи лекций: https://www.youtube.com/watch?v=f-AQ3lWWOZY&list=PLuC78Z-ctguXZDvlWIC46QGZG2TnxSUBt
Тут будут задачи и остальные материалы: https://github.com/sslotin/tinkoff-hpc

There is a couple of things about sparse tables that a lot of people I think are doing slightly wrong (including the popular reference implementation by e-maxx).

First, you don't need to precalculate and store logarithms in an array. In fact, whichever procedure compiler will pick to calculate the logarithm is probably going to be much faster than looking it up somewhere in random access memory. The optimal way would be to use __builtin_clz ("count leading zeroes") which uses a separate instruction available on most modern x86's. This way you need just 2 memory reads instead of 3, so on large arrays this should be ~1.5x faster.

Second, memory layout and the order you iterate it matters when you're building the sparse table. There is a total of $$$2 \times 2 = 4$$$ ways to do it, and only one of them results in beautiful linear passes that work 1.5-2x faster.

It's easier to implement too:

int a[maxn], mn[logn][maxn];

int rmq(int l, int r) { // [l; r)
    int t = __lg(r - l);
    return min(mn[t][l], mn[t][r - (1 << t)]);
}

// somewhere in main:
memcpy(mn[0], a, sizeof a);
for (int l = 0; l < logn - 1; l++)
    for (int i = 0; i + (2 << l) <= n; i++)
        mn[l+1][i] = min(mn[l][i], mn[l][i + (1 << l)]);

Implementation was updated (tnx jef and plainstop):

int lg(int x) {
    return 31 - __builtin_clz(x);
}

int rmq(int l, int r) { // [l; r)
    int t = lg(r - l);
    return min(mn[l][t], mn[r - (1 << t)][t]);

Also, it's interesting that the last loop is not getting auto-vectorized by the compiler (because std::min is probably something overly complex), and replacing it with simple (x < y ? x : y) gets total speed up to ~3x if you include avx2, but I personally wouldn't do this because it looks cumbersome:

int x = mn[l][i];
int y = mn[l][i + (1 << l)];
mn[l+1][i] = (x < y ? x : y);

(Testing performed on my laptop; didn't run it on CF or other online judges.)

http://algorithmica.org/en/b-tree

Hi, it's me again. A couple of days ago I published a post about speeding up binary search by rearranging memory in a way that allows prefetching, which is basically a way of trading off memory bandwidth for latency.

As noted in the comments, it had a noisy neighbors issue when tested on online judges, as different solutions evaluating on the same machine could compete for the same memory bandwidth. The speedup was like 2x-3x (and very volatile) on Codeforces while on my laptop and my dedicated server it was 4-5x, depending on the array sizes.

And so I rewrited it using B-tree layout instead, and it worked, because it bluntly requires 4x less memory reads. It is still quite volatile on CF—compare this (6.6x) and this (5.1x)—but I've never seen it drop below 3x on adequate array sizing (yes, the title is a bit clickbaity; I think the average speedup is around 5x).

There are two implementations:

1. One is straightforward and uses nothing fancy
2. The other is compute-optimized with AVX2 instructions and is ~30% faster, but doesn't work with older hardware (notably ideone and Yandex.Contest servers)

For more details, check the article.

Also, it would be really cool if someone could figure out a way to make compiler produce an autovectorized version of the faster one, so that it could be more easily extendable. It's weird and annoying that the compiler can't produce these 3 lines of code.

https://algorithmica.org/en/eytzinger

This will probably be an hour-long read about the CPU memory model that explains 10 lines of code at the very end.

The following code is 4 to 5 times faster than calling std::lower_bound over a sorted array:

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

const int n = (1<<20);
const int block_size = 16;
alignas(64) int a[n], b[n+1];

int eytzinger(int i = 0, int k = 1) {
    if (k <= n) {
        i = eytzinger(i, 2 * k);
        b[k] = a[i++];
        i = eytzinger(i, 2 * k + 1);
    }
    return i;
}

int search(int x) {
    int k = 1;
    while (k <= n) {
        __builtin_prefetch(b + k * block_size);
        k = 2 * k + (b[k] < x);
    }
    k >>= __builtin_ffs(~k);
    return k;
}

tl;dr: it uses a segtree-like cache-friendly array reordering that allows trading off memory bandwidth for latency via prefetching.

This is technically not a drop-in replacement, since it requires some preprocessing, but I can't recall a lot of scenarios where you obtain a sorted array but can't spend linear time on preprocessing.

This method could also be used to speedup heaps, segment trees, and other static binary tree structures.

Дописываю https://algorithmica.org/ru/sqrt, большой туториал про всё, что относится к корневым эвристикам.

Кто-нибудь может помочь — подскажите образцовую реализацию какой-нибудь задачи, где нужен трюк с корзинами? Например, Dancing Elephants с IOI 2011.

https://algorithmica.org/ru/sse

Статья про то, как оптимизировать циклы с помощью SIMD-инструкций и ускорять в ~10 раз достаточно простые программы.

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

Всем привет!

Не очень много кто знает, но я последние пару лет вёл страницу с конспектами, которые писал для разных кружков и сборов. Несколько недель назад это всё было преобразовано в отдельный сайт: https://algorithmica.org.

Там сейчас ~35 статей разной степени дописанности (что отмечено буквами α / β в индексе), суммарно объёмом чуть более 50000 слов. Для сравнения: это примерно треть e-maxx.ru/algo.

Хочется из этого сделать что-то массовое вроде e-maxx-eng, но для русского. У проекта открытая лицензия, и он живёт на гитхабе: https://github.com/algorithmica-org/articles

На данный момент большинство статей мои — поэтому там всё в формате лекций, ориентированных на десятиклассников-самоучек из старших параллелей олимпиадных школ — но некоторые значимые штуки законтрибьютили также KiKoS, adamant и некоторые препы Tinkoff Generation. В репозитории есть почти автоматическая система для редактирования статей; будет клёво, если кто-нибудь ещё подключится и добавит что-то новое или исправит старое.

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

Всем привет!

Tinkoff.ru с сентября этого года запускает образовательные курсы для школьников по алгоритмам, математике, физике, машинному обучению и нейросетям. Отбор будет проходить в начале сентября, сами занятия с середины. Курсы будут бесплатными. Проходить в этом семестре будут в Москве, Нижнем Новгороде и Рязани — подробнее под катом.

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

This is my repo. There are many like it, but this one is mine. My repo is my best friend. It is my life. I must master it as I must master my life. Without me, my repo is useless. Without my repo, I am useless. I must maintain my repo true. I must commit faster than my collaborator who is trying to open issue. I must assign issue to him before he assigns issue to me. I will...

I will keep my repo clean and ready, even as I am clean and ready. We will become part of each other. We will...

Before Codeforces, I swear this creed. My repo and myself are the defenders of good solutions. We are the masters of our problemset. We are the saviors of my rating. So be it, until there is no WA, but AC. Amen.

— Maintainer's Creed

Hi. I am sharing my algorithms repository to the community and calling you to test / enrich it. It is designed to be minimalistic and copy-pastable. I use it during live contests. Most of the code is not designed to be standalone — you need to copy and tweak it a bit.

Мне стало интересно -- а откуда пошло упоминать в легендах задач страну Берляндию (Berland)? Гугл по соответствующему запросу ничего кроме олимпиадных задачек не выдает. Может, кто-нибудь из ветеранов знает?

So, I scraped stats.ioinformatics.org for some data to estimate the correlation between CF rating and place you get at IOI. I guess many will find these plots interesting.

I only considered contestants who had  ≥ 5 rated contests during last 2 years before 1st of August of the relevant year. Years 2013-2017 had more than 120 such contestants, but IOI '12 had only 55 and earlier IOIs had even less, so I didn't go any further.

By "normalized # of inversions" I mean this: , i. e. actual number of inversions divided by maximum possible. This is some kind of measure of a contest being close to a standard CF round.

For more details, check out the code: https://gist.github.com/sslotin/ae9557f68bb7e7aea1d565e2229a81c9

Most of ICPC veterans I know joined companies like Google, Facebook, Yandex or some younger tech startups (1, 2, 3) or stayed at university, getting their scientific degrees and training some high school / university students in the process. That's all quite boring. I recently found out about some unusual careers of former olympians. By "unusual" I mean something like this:

Nikolai Durov — won ICPCs of 2000 & 2001 and also performed really well at some IOIs and IMOs. He co-founded VK and Telegram. (I don't think I really needed to introduce him)

Jakub Pachocki — 2nd place at ICPC '12 and 1st at GCJ of the same year. Last month I saw him at The International presenting a Dota 2 bot by a really cool ML project

Leonid Volkov — 14th place (bronze) at ICPC '01. He went into politics and now he is the chief of staff of Alexei Navalny's campaign (he is quite a trending oppositioner in Russia)

Just for fun, what other examples do you know of?