Полезный алгоритм - Modular exponentiation

Суть алгоритма в вычислении a^b mod c без вычесления значения a^b.

Подробное описание алгоритма

(Псевдо)код

Bignum modpow(Bignum b, Bignum e, Bignum m) {

 

   Bignum result = 1;

 

   while (e > 0) {

      if ((e & 1) == 1) result = (result * b) % m;

      e >>= 1;

      b = (b * b) % m;

   }

   return result;

}

Поверь я сердцем чист. Враньем по горло сыт.

Самое полезное и приятное что я вынес из текущего скандальчика в ЖЖ на тему отмены базовых аккаунтов - вот это ответ одного из пользователей Носику.



Мое отношение к произошедшему совпадает на 100% с такими выводами:

Что делать Супу: повесить большую надпись "Простите нас", ввести обратно бесплатные аккаунты и заняться делом.

Взято отсюда (ссылка на архив поскольку автор удалил журнал. толи в знак поддержки акции, толи еще по каким причинам)

Синхронизация файлов через интернет

Новый сервис - dropbox, пока в стадии beta тестирования. Видео впечатляет. Как всегда в подобных случаях вопрос - почему это не было сделано раньше.

Как я МАК полюбил, аутотренинг

Это серией заметок "Как я Мак полюбил" я хочу выработать в себе любовь к продуктам Apple в целом и к макам в частности. К тому времени, как это случится, мои финансы теоритически должны достигнуть той планки, при которой я буду способен обеспечить себя МакБуком той или иной модели.

с ума сойти...
"я хочу выработать в себе любовь к продуктам Apple". выработать.
Вообщем то именно поэтому я читаю хабру так же как баш - сборник забавных цитат.

Project Euler, problem 127

Чем мне нравится Project Euler - практически на любой задаче можно что-то для себя открыть/переоткрыть.

The radical of n, rad(n), is the product of distinct prime factors of n. For example, 504 = 23 × 32 × 7, so rad(504) = 2 × 3 × 7 = 42.
We shall define the triplet of positive integers (a, b, c) to be an abc-hit if:
1. GCD(a, b) = GCD(a, c) = GCD(b, c) = 1
2. a < b
3. a + b = c
4. rad(abc) < c
For example, (5, 27, 32) is an abc-hit, because:
1. GCD(5, 27) = GCD(5, 32) = GCD(27, 32) = 1
2. 5 < 27
3. 5 + 27 = 32
4. rad(4320) = 30 < 32
It turns out that abc-hits are quite rare and there are only thirty-one abc-hits for c < 1000, with ∑c = 12523.
Find ∑c for c < 110000.

После некоторого достаточно бесплодного с точки зрения результата размышления(о котором тоже в принципе интересно было бы написать) я пришел к решению проблемы практически "в лоб" - перебираем все числа a b c такие что a<b,a+b=c и с<110000
и проверяем выполняются ли для них условия 1. и 4.
Код:

    int count = 0;

    ulong64  sum = 0;

    for(int a=1;a<limit ;++a){

        int b = a+1;//a < b

        int c = a+b;//c = a + b

        while(c<limit){

            if( ! (cross(dpf[a],dpf[b]) || cross(dpf[a],dpf[c]) || cross(dpf[b],dpf[c]))){//GCD(a, b) = GCD(a, c) = GCD(b, c) = 1

                if(rad[a]*rad[b]*rad[c]<c_long){//rad(abc) < c

                    ++count;

                    sum+=c;

                }

            }

            c = a+(++b);

        }

    }

Здесь dpf[i] - массив из простых делителей числа i (например для 504 это будет [2,3,7])
rad[i] - произведение все чисел из массива dpf[i].
Функция cross(a,b) возвращает false если массивы a и b не пересекаются, т.е. нет такого числа i входящего одновременно в оба массива.
соответственно
if( ! (cross(dpf[a],dpf[b]) || cross(dpf[a],dpf[c]) || cross(dpf[b],dpf[c]))){
соответствует условию
1. GCD(a, b) = GCD(a, c) = GCD(b, c) = 1
Далее из этого же условия следует что rad(a*b*c) == rad(a)*rad)b)*rad(c), соответственно
if(rad[a]*rad[b]*rad[c]<c_long)
соответствует условию
4.rad(abc) < c

Вообщем надеюсь логика более менее понятна. На тестовом условии (для c<1000 count == 31 и sum == 12523) этот подход отрабатывал. Оставалась мелочь - запустить его же для c<110000.

Первая проблема была - ну оооочень долго выполняется. Когда спустя минут 10 я добрался до a=4000 я прервал выполнение.

Первая попытка оптимизации - если а и b четные их можно не проверять. Поэтому добавилось условие
if(a%2 == 1 || b%2 == 1)

Все равно очень долго...да и явно неправильный результат.
В чем проблема? переполнение... переполнение может происходить при проверке условия rad(a)*rad)b)*rad(c). Переходим к unsigned long long. Результат вроде становится правильным...но все равно ооочень долго.

Хм...хм...
Возможно кому-то решение видно сразу. Я думал достаточно долго. Даже было желание вновь придумать другой подход.
В результате прогнав несколько тестов (на меньшем значении c) я понял в чем дело.
Во внутреннем цикле используются два условия - 1. и 4. Результат должен удовлетворять обеим условиям. С этой точки зрения условия равнозначны. Но - они не равнозначны с точки зрения времени выполнения и частоты срабатывания.
Условие 4. срабатывает реже чем условие 1. И в то же время выполняется намного быстрее.

Поэтому все что нужно - поменять условия 1. и 4. местами...
Результат (я убрал переход к unsigned long long для наглядности):

    int count = 0;

    ulong64  sum = 0;

    for(int a=1;a<limit ;++a){

        int b = a+1;//a < b

        int c = a+b;//c = a + b

        while(c<limit){

            if(a%2 == 1 ||  b%2 == 1){

                if(rad[a]*rad[b]*rad[c]<c_long){//rad(abc) < c

                    if( ! (cross(dpf[a],dpf[b]) || cross(dpf[a],dpf[c]) || cross(dpf[b],dpf[c]))){//GCD(a, b) = GCD(a, c) = GCD(b, c) = 1

                        ++count;

                        sum+=c;

                    }

                }

            }

            c = a+(++b);

        }

    }

Время выполнения стало 29 секунд.

Выводы.
Порядок выполнения проверок имеет значение... Вывод в общем то очевидный. Но про него часто забывают.

Кстати, родилась простая задачка которую можно использовать на собеседованиях.

Есть два отсортированных по возрастанию массива целых чисел. Определить пересекаются ли эти массивы за время O(n+m), где n и m - длина массивов.

Монополия, стандарты, IE

Только факты.
CSS1 спецификация получила статус рекомендации в 1996 году. Первый броузер который поддерживал CSS1 был Internet Explorer 3.
Первый броузер который полностью поддерживал CSS1 был Internet Explorer 5.0 дла Мac, и вышел он в марте 2000 года.
Опера начала более-менее поддерживать CSS1 в 1998 году.
Ни один броузер не имел нормальной поддержки CSS2. Ни один и никогда. Именно это вынудило W3C пересмотреть CSS2 и выпустить CSS2.1

CSS2.1 получил статус Candidate Recommendation в феврале 2004 года, но в июне 2005 года его статус был изменен на "черновик". Статус Candidate Recommendation обратно он получил в июле 2007 года.

По состоянию на июль 2006 года (на эту дату ссылается статья в википедии) ни один броузер не поддерживал полностью CSS2.1. Ни один, включая FireFox 1.5 в котором была значительно улучшенна поддержка CSS2.1
Firefox 1.0 вышел в ноябре 2004 года.
Internet Explorer 6 вышел в августе 2001 года.

Firefox 2.0 вышел в конце 2006 года.
Internet Explorer 7 вышел в октябре 2006 года.

Firefox 2.0 не проходит acid2. Internet Explorer 7 не проходит acid2.
Выход Internet Explorer 8 и FireFox 3 планируется на 2008 год.
Internet Explorer 8 и FireFox 3 будут проходить acid2.

По состоянию на январь 2008 года IE7 занимает 43% рынка броузеров, IE6 - 32%, FF2 - 16%, SF 3 - 4%, FF1.x и IE5 меньше 0.5%.

Принцип 80/20

Думаю если не все то многие знакомы с этим принципом. Формулируется он обычно так - "20% усилий приносят 80% результата". Ну или "в любом сообществе 20% нормальные люди. Ну а остальные...".
Всегда считал что это такая "народная мудрость".
Оказывается нет. Оказывается у этого принципа есть автор, и зовут его Вильфредо Парето, а сам принцип называется законом Парето. И был..эээ..открыт... в 1897 году.

Важнейшие положения закона Парето

• Значимых факторов немного, а факторов тривиальных множество — лишь единичные действия приводят к важным результатам.


• Большая часть усилий не даёт желаемых результатов.


• То, что мы видим, как правило отличается от того, что мы получаем, — всегда существуют скрытые силы.


• Обычно слишком сложно и утомительно разбираться в том, что происходит, а часто это и не нужно: необходимо лишь знать — работает ли Ваша идея или нет, и изменять её так, чтобы она заработала, а затем поддерживать ситуацию до тех пор, пока идея не перестанет работать.


• Большинство удачных событий обусловлено действием небольшого числа высокопроизводительных сил; большинство неприятностей связано с действием небольшого числа высокодеструктивных сил.


• Бо́льшая часть действий, групповых или индивидуальных, являет собой пустую трату времени. Они не дают ничего реального для достижения желаемого результата.

О подготовке к интервью в Google

Get that job at Google

А неплохой у них отбор...
Выдержки:

Algorithm Complexity: you need to know Big-O. It's a must. If you struggle with basic big-O complexity analysis, then you are almost guaranteed not to get hired. It's, like, one chapter in the beginning of one theory of computation book, so just go read it. You can do it.

Sorting: know how to sort. Don't do bubble-sort. You should know the details of at least one n*log(n) sorting algorithm, preferably two (say, quicksort and merge sort). Merge sort can be highly useful in situations where quicksort is impractical, so take a look at it.

For God's sake, don't try sorting a linked list during the interview.

Hashtables: hashtables are arguably the single most important data structure known to mankind. You absolutely have to know how they work. Again, it's like one chapter in one data structures book, so just go read about them. You should be able to implement one using only arrays in your favorite language, in about the space of one interview.

Trees: you should know about trees. I'm tellin' ya: this is basic stuff, and it's embarrassing to bring it up, but some of you out there don't know basic tree construction, traversal and manipulation algorithms. You should be familiar with binary trees, n-ary trees, and trie-trees at the very very least. Trees are probably the best source of practice problems for your long-term warmup exercises.

You should be familiar with at least one flavor of balanced binary tree, whether it's a red/black tree, a splay tree or an AVL tree. You should actually know how it's implemented.

You should know about tree traversal algorithms: BFS and DFS, and know the difference between inorder, postorder and preorder.

You might not use trees much day-to-day, but if so, it's because you're avoiding tree problems. You won't need to do that anymore once you know how they work. Study up!

Graphs

Graphs are, like, really really important. More than you think. Even if you already think they're important, it's probably more than you think.

There are three basic ways to represent a graph in memory (objects and pointers, matrix, and adjacency list), and you should familiarize yourself with each representation and its pros and cons.

You should know the basic graph traversal algorithms: breadth-first search and depth-first search. You should know their computational complexity, their tradeoffs, and how to implement them in real code.

You should try to study up on fancier algorithms, such as Djikstra and A*, if you get a chance. They're really great for just about anything, from game programming to distributed computing to you name it. You should know them.

Whenever someone gives you a problem, think graphs. They are the most fundamental and flexible way of representing any kind of a relationship, so it's about a 50-50 shot that any interesting design problem has a graph involved in it. Make absolutely sure you can't think of a way to solve it using graphs before moving on to other solution types. This tip is important!

Project Euler, problem 107

Project Euler, problem 107 - переизобретая алгоритмы на графах...
Интересная задача, особенно для тех кто не знает изначальный алгоритм. Собственно для таковых состоять она будет в том чтобы (пере)изобрести нужный алгоритм.

Мой первый вариант был очень похож на Prim's algorithm, но я просто не поверил(и не смог доказать) что он ведет к верному результату.
Финальный вариант больше подходил на алгоритм Дейкстры.

А в целом данная задача называется задачей нахождения Minimum spanning tree и решается с помощью алгоритмов Prim's algorithm и Kruskal's algorithm. Первоначальным же алгоритмом для этого класса задач является Borůvka's algorithm. Что характерно - все три алгоритма принадлежат к классу "жадных" алгоритмов.

Просто так

Задачка -

имеется возрастающая последовательность из n разных чисел. Определить минимальное число сравнений для того чтобы убедиться что не существует двух пар чисел из этой последовательности с одинаковой суммой.
Например - в последовательности [1,2,3,4] такие пары [1,4] и [2,3]

Фукнциональное решение на питоне (мне не совсем нравится. но что придумал то придумал)

def functional_approach(length):

    data=filter(lambda x: x[0]<x[1],iselectmany(xrange(1,length+1),curry1(izipwith,xrange(1,length+1))))

    def count(pair,li):

        return len(filter(lambda x:x[0]> pair[0] and x[1]<pair[1],li))

    print reduce(lambda x,y:x+count(data[y],data[y+1:]),xrange(0,len(data)))

Императивное решение:

def iter_approach(length):

    data = []

    for a in xrange(1,length):

        for b in xrange(a+1,length+1):

            data.append((a,b));

    c = 0

    for l in xrange(0,len(data)-1):

        for n in xrange(l+1,len(data)):

            if data[l][0]<data[n][0] and data[l][1]>data[n][1]:

                c = c + 1

    print c

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

Впомогательные фукнции-генераторы izipwith и iselectmany

def izipwith(seq,n):

    for s in seq:

        yield (n,s)

def iselect_many(seq,func):

    for s in seq:

        for s1 in func(s):

            yield s1