Задачка про парные числа

А в случае 16384-битных слов? Всё равно 32 счётчика?
Правда, я не уверен, что решение с x^3 вообще работает.

Задачка про парные числа

Ваше решение разве не зависит от размера слова?

Зависит — примерно как 3*N бит. А решение со счётчиками — примерно N^2 бит. Конечно, ограничения задачи становятся слегка другими, но O(N)<O(N^2).

Сортировка очереди без использования дополнительных ресурсов

Без счётчиков, но с дополнительным пустым элементом в очереди:

queue.Push(new Item());
for(;;){
    for(;;){
        temp=queue.Pop();
        if(queue.Get()==Item.Empty) goto _1;
        if(queue.Get()<=temp) break;
        queue.Push(temp);
    }
    for(;;){
        if(queue.Get()==Item.Empty){
            queue.Push(temp);   
            queue.Push(queue.Pop());
            break;
        }
        if(queue.Get()<temp) queue.Push(queue.Pop());
        else{
            queue.Push(temp);
            temp=queue.Pop();
        }
    }    
}
_1:
queue.Pop();

Сортировка очереди без использования дополнительных ресурсов

Получается, что так. Либо можно что-нибудь посчитать, либо запомнить (или переставить) элементы в очереди — но не одновременно.
С другой стороны, ничто не запрещает нам добавить новый пустой элемент в очередь и использовать его для сортировки пузырьком?

Сортировка очереди без использования дополнительных ресурсов

Есть разница между использованием О(1) и использованием ровно одной переменной. Мы, например, не можем переложить начало очереди в конец, не испортив какого-нибудь счётчика (если он зачем-то нужен).

Задачка про парные числа

Давайте, чтобы не было разночтений — памяти у вас четыре килобайта.

Задачка про парные числа

https://habrahabr.ru/post/243819/, задача 5?

Американские математики обнаружили ранее неизвестное свойство простых чисел

Для чисел порядка 10^100 вероятности переходов получаются в диапазоне 24.0% — 26.0%.
24.1677 25.4576 25.5158 24.8589
24.9094 24.2796 25.2975 25.5136
25.0930 25.2572 24.1206 25.5292
25.6679 25.0855 25.0776 24.1690
Для небольших делителей брал настоящие делимости, для больших — по вероятности.

Зачем программисту знать алгоритмы

то так важно ли, что после переписывания его со знанием алгоритмов и структур данных, оно станет работать полсекунды или нет?

И бозон Хиггса будет ловиться не 2 года, а 2000 лет? Да они сами безо всякой конкуренции захотят и с алгоритмистами, и с программистами сотрудничать в лучшем виде.

Зачем программисту знать алгоритмы

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

Американские математики обнаружили ранее неизвестное свойство простых чисел

Похоже, что чтобы получить при всех переходах 24-26%, надо дойти до 10^400...

Американские математики обнаружили ранее неизвестное свойство простых чисел

Если проанализировать числа в окрестности 2^40, получим карту переходов
25.0019: 19.8492 28.6524 28.5576 22.9407
25.0064: 24.5381 19.4783 27.4282 28.5554
24.9994: 25.3014 26.5211 19.5236 28.6539
24.9923: 30.3210 25.3753 24.4870 19.8167

Если же взять числа в окрестности 2^57, получится
25.0134: 21.0642 27.7100 27.5466 23.6792
25.0067: 24.9007 20.9652 26.6990 27.4351
24.9824: 25.2773 26.0573 20.9125 27.7530
24.9975: 28.8142 25.2948 24.7668 21.1242

Диапазон вероятностей переходов уменьшился с 10.8% до 7.9%. Возможно, рассматривая ещё более далёкие числа, можно ужаться и в 1%, и ещё меньше.

Американские математики обнаружили ранее неизвестное свойство простых чисел

До 100 млн:
1: 1440298
3: 1440473
7: 1440495
9: 1440185
Распределение выглядит очень равномерным (но на X^2 не проверял).

Большой опрос по алгоритмам

Собственно, почему бы и нет? Если сравнение намного медленнее, чем проход по списку (например, сравнение алгебраических чисел или работа в интервальной арифметике), то бинарный поиск вполне оправдан.

Американские математики обнаружили ранее неизвестное свойство простых чисел

До 10^8:
1: 17.6996%, 30.3928%, 31.0334%, 20.8742%
3: 23.6386%, 16.6670%, 28.6851%, 31.0093%
7: 25.5825%, 27.3242%, 16.6752%, 30.4181%
9: 33.0755%, 25.6244%, 23.6160%, 17.6841%

Большой опрос по алгоритмам

Все модификации быстрой сортировки похожи друг на друга и имеют сходное время.

Интроспективная сортировка считается такой модификацией?

А нужно ли знать программисту алгоритмы?

Интересно знать, кому (или для чего) должен знать алгоритмы человек, который называет себя программистом?

И как же должен называться специалист, от которого требуется имитация отжига; Монте-Карло… далее по списку? Вы уже установили, что это не программист. Тогда кто же?

Вычисление значения многочлена. Все ли тривиально в этом вопросе?

Судя по сигнатуре, EC-40. Хотя могла быть и СМ-1420. Спирт использовался для протирки поверхностей накопителя на магнитных дисках и головок самого накопителя.

Обзор примитивов синхронизации — спинлоки и тайны ядра процессора

Любопытно, что в версиях процессоров TI C64xx команды синхронизации LL/SC были, а в TI C66xx исчезли. Насколько я понял, их роль выполняют DMA, shared memory, ещё что-то… но от атомарных команд решили отказаться.

Обзор примитивов синхронизации — спинлоки и тайны ядра процессора

например, если LL и SC лежат в памяти слишком далеко

В смысле исполняемые инструкции? Ячейка одна и та же.

Рассмотрим два сценария.
`

0, #1, #2 выполнили LL

#1 выполнило SC (удачно)
#2 выполнило SC (неудачно)
#3, #4 выполнили LL (с той же ячейкой)
#0 выполнило SC (???)
#3 выполнило SC (???)

0, #1, #2 выполнили LL

#1 выполнило SC (удачно)
#2 выполнило SC (неудачно)
#3, #4 выполнили LL (с той же ячейкой)
#3 выполнило SC (???)
#0 выполнило SC (???)

`
Сценарии различаются двумя последними строчками.
Считается, что инициирована новая последовательность? Может ли #0 выполнить SC? Может ли #3 не выполнить SC?