так как фирм ограниченное (штучное) кол-во - достаточно соорудить мастер брелок который перебирает мастер ключи по очереди (по сути перебор паролей по словарю) - откроются все что прошиты в брелок (хотя работать будет медленнее чем родные ключи)
другой вопрос что могут додуматься НЕ делать одинаковые для всех домофонов серии мастер ключи. (Потому что обслуживающая контора в принципе может сама осуществлять сервис, и хранить базу уникальных ключей по адресам установки. И ДАЖЕ может передавать брелоку серийник домофона, из которого последний вычисляет по крипто алгоритму с закрытым ключом ключ для конкретного домофона.) - разобрать такой уже равноценно утечке закрытого ключа из конторы. Который может вообще не фигурировать в прошивках. (в мастер брелоке его можно выполнять в виде крипто чипа у которого ключ наружу не отдается. В прошивке домофона фигурирует только открытый) - но это довольно серьезная степень запарки на стадии разработки.
Хотя я уверен что какой то завод уже выпускает такие чипы как независимый компонент, ключ в который можно прошить однократно при инициализации.
В принципе можно взять огромное кол-во популярных дешманских микроконтроллеров, даже AVR'ы имеют режим прошивки с фьюзами которые запрещают дальнейшие способы перезаписи, а тем более чтение прошивки - в любой из таких можно положить единоразово релизнутую (и затем хранимую аки зеницу ока) прошивку с закрытым ключем, с которой брелок способен по сути проходить челлендж-алгоритм цифровой подписи. Благо в функциональности ключа вероятно прошивать абсолютно нечего, потому эти ключи может изготавливать единственный сертифицированный центр. А может и вообще единственный человек. (в таким образом прошим брелоке можно заложить функционал "мастер ключа" уже для него - который принимается единожды, для записи закрытого в ПЗУ и финализации защит - через сам 1-wire можно пачками инициировать такие ключи прописывая в них только закрытый ключ)
- устройства не обладающие таким способом защиты кстати уязвимы для скимминга (когда на хост крепиться фэйковая "морда" не мешающая втыканию ключа, но снифающая обмен данными) в случае с 1-wire интерфейсом такое устройство может быть чрезвычайно миниатюрным просто ободком поверх разъема i-button
забавно отметить, что подобный скиммер (с учетом того что скимеры на домофонах чрезвычайно не встречающийся анахренизм) могут долго висеть постоянно... и могут собирать данные о времени регистрации уже вас на точке... (потому что у ключей обычно есть id) в периодически забиераемый тем же i-button ключом... такие шпионские штучки
Кстати говоря напишите где по этому методу вы встречали теорию, если помните... Я этот метод открыл независимо, и практикую.
И он мне кажется настолько крут, что я чувствую необходимым по нему писать подробную статью на Хабр. Ощущение, будто я рискую общечеловеческим достоянием пока не отписал (ибо смертен) Однако такой материал находиться на стыке математики и программирования. А я в математике самоучка и терминологически подкован плохо. Знаю как работает, но как популярно объяснить испытываю трудности. Если существует какая-то математическая терминология на этот счет на нее очень было бы полезно сослаться.
Кстати говоря мало того что, метод требует только сложений, они в нем с т.з. параллелизма еще и все НЕзависимые!
что как бы говорит о том, что вычисления полинома N-ой степени на суперскалярной архитектуре, количество параллельных сумматоров в которой может вместить все коэффициенты (А их сейчас в среднем по 3 на ядро, при среднем количестве ядер = 4 это 12 штук) может вычислять полином степени на единицу меньшей чем их количество ЗА ОДИН ТАКТ!!!
И даже это еще не все... на самом деле независимость сложения позволяет продемонстрировать это в еще более дерзкой форме, т.к. по сути для этих вычислений важна скорее общая битовая размерность сумм. И если скрестить это с битхакерскими техниками группировки разрядов в одну переменную, то можно параллельности добиться на однопоточной машине и без супперскалярности, просто используя младшие биты результата. Следующий пример на JS вернет параболу (полином 2й степени) используя на точку только одно сложение ui32 числа со своими же старшими разрядами
let x=136061184;
new Uint8Array(31).fill().map(()=>x+=x>>13);
в принципе даже сдвига здесь можно избежать, если он будет на четное кол-во байт, тогда память с хранимым значением можно будет с другим отступом просто замапить в альтернативную переменную (даже на JS это уже можно сделать с TypedArray, не говоря про Си)
а еще на многих машинах есть SIMD инструкции - которые позволят аж 128битами оперировать нарезая их как надо на "виртуальные разряды"
умножение это операция порождающая связность битовых разрядов (в принципе имеющая матричную природу) - все упрощения умножения полиномов будут алгебраически иметь ту же природу что и методы быстрого умножения матриц. А потому построение вычислений на независимых операциях умножения это строго в противоположную сторону оптимизация. И короткий ответ нет нельзя.
Однако это не касается длинной арифметики - если вы вычисляете что-то где единственный операнд представляется в виде массива данных, то там есть методы реализации длинной арифметики, которые часть вычислений могут выполнять независимо, за счет чего ускоряться. - НО это по сути не относиться к алгоритму самого умножения полинома
если вы говорите про float вычисления, то при сокращении числа умножений средне ожидаемая ошибка будет тоже сокращаться. Так что скорее более точный получится. Количество же сложений не имеет значения, потому что ошибка на них (имеющаяся и в схеме Горнера) может в обоих случаях вычисляться алгоритмом компенсационного суммирования Кэхэна. ну и если надо абсолютно точно то вы обычно берете длинную арифметику - которая уже только ускорятся будет от использования более оптимизированных схемм
Помниться забавы ради развлекался изучал что можно "выжать" из второй степени без всяких разбиений - первая проблема собственно что парабола относительно совпадает с косинусом до 90 градусов если ее просто отмасштабировать получается полином `cos=x=>1-.4053*x*x`. Через формулы приведения можно бы получить то же и для синуса, но в такой формуле появляется перемена знака... и нужен был как бы назвать "инверсный квадрат" - при возведении в который всегда получается отрицательный знак... тогда бы получалось 2й степенью обойтись без кондишнов и для синуса. В итоге это развернулось что один из иксов в формулу берется с отбросом знака.
В принципе для максимально быстрого отброса знака почти честно можно ксорить все биты числа на его знаковый бит, для этого (вероятнее всего у вас не будет float который бы работал еще и с XOR) понадобиться пересчитать найденные константы в арифметику статической точки, что бы все считать в целых
погрешность может быть уменьшена ценой потери контрольных точек `sin=x=>(1.217-0.38529*Math.abs(x))*x` до 3.9% но обычно точность контрольных точек чрезвыйчайно ожидается множеством алгоритмов, которые без нее могут начать работать не правильно.
Поискать наиболее проблемные места поможет такой тест (выводящий последние 30 мест с наибольшей ошибкой) Параметром количества шагов можно "позумить" детализацию (таким образом можно как быстро отыскать в целом проблемные места, так и отдельные участки посмотреть точнее)
dErr=(f,g,x=0,to=Math.PI/2,steps=100)=>{
let step= (to-x)/steps, e, ers=[];
for(; x<=to; x+=step){
if((e=Math.abs(f(x)-g(x)))< ers[(ers.length=30)-1]?.e)continue;
ers.splice(ers.findIndex(o=>o===undefined|| e>o.e),0,{e, x})
}
return ers;
}
console.log(dErr(Math.sin,sin))
оказалось что в некоторых случаях 5% погрешности вполне визуально допустимы. Еще стоит вспомнить что столько степень полинома ресурсозатратна сколько количество членов и например формула синуса на основе коэффициентов Тэзлора 5го порядка уже довольно визуально точна но в ней нет 2го и 4го членов `sinTailor5=x=>x - x**3/6 + x**5/120` что то же самое что `x(1-xx(1/6+xx/120)`, где на возведениях в квадрат экономим заводя переменную xx. Важно так же отметить что эта формула является частичной суммой, потому не оптимальна, и ее как и формулу до 3го порядка `x=> x - x**3/6` можно значительно подтюнить масштабированием коэффициентов.
Так же не стоит забывать, если вы почему-то считаете много синусов, то если у вас получиться их хотя бы равномерно упорядочить, то полином может считаться феерически быстро дельта функциями. В этом случае дело в том, что значение sinTailor5(x+dx) отличается от sinTailor5(x) на полином меньшей на один степени (потому что см. степенная производная) Тот отличается от предыдущего на полином третьей, который отличается на полином 2ой... короче... итеративный счет полинома 5й степени это не больше 6 сложений - гарантировано.
Когда я говорю не больше я имею ввиду что может быть и меньше, но это уже отдельная битхакерская песня... В качестве задачи с двумя звездочками на досуге можете сунуть ЭТО в консоль броузера и подумать как и почему это оно выводит квадраты (учитывая что в цикле только есть умножение на константу):
let x=new Uint32Array(1).fill(531489<<8), c=8193/8192;
new Uint8Array(31).fill().map(()=>x[0]*=c);
log=async(...arg)=>new Promise(r=>{ //async log
console.log(...arg); setTimeout(r);
})
async function someCollisionOfUi32(iterable){
const map=new Uint32Array(65536); //256K
// поиск группы с кол-вом членов >65535 (минимум 1 повторился):
let i=0, collision= Math.floor(Math.random()*0x100000000);
console.log('predefined collision was:', collision);
for(x of iterable(collision, 123)){
if(!(++i&0x3FFFFFF))await log((i/0x100000000).toFixed(2));
if(++map[x>>>=16] > 65536){
map.fill(0);
// поиск числа из группы повторившегося более раза
for(y of iterable(collision, 123)){
if(!(++i&0x3FFFFFF))await log((i/0x100000000).toFixed(2));
if((y>>>16)==x&&map[y&65535]++)return y; //гарантированно случиться
}
break;
};
}
return -1; //дубли отсутствуют
}
function*TestSeq(mix, seed=Math.floor(Math.random()*0x100000000)){
let x=new Uint32Array(1);
x[0]=seed;
for(let n=0;n<0x100000000;n++){
x[0]=x[0]*69069 +1; // Ui32 modulo by overflow
yield x[0];
}
yield mix; yield mix;
return;
}
// console.log([...TestSeq(4)])
console.time("collise");
console.log('someCollisionOfUi32:',await someCollisionOfUi32(TestSeq));
console.timeEnd("collise"); //~219s
Попробовал решение 8й задачи на всех ui32 числах. С тестом как водиться провозился дольше чем с алгоритмом. В итоге: - тест на JS и работает из консоли браузера - лог асинхронный (что позволяет вкладке не виснуть намертво до конца выполнения) выводит процент готовности прохода в консоль (всего их два) - потребление памяти 256Кб - скорость обхода 2**k+2 чисел ~219s (3 с половиной минуты на ryzen 9) - тестируется LCG PRNG последовательность всех ui32 чисел + в конец ее добавляется дважды случайно взятое число (оно и будет давать коллизию)
Дополнения: - в принципе 2**32 чисел это всего то 2**29 = 536 870 912 байт индекса, что можно побитово замапить флагами четности и решить за один проход вдвое быстрее, но потратив 512Мбайт вместо 256Кбайт. Можно оценить разницу по памяти. Впрочем работая с ui64 надо именно так поступать, потому что битность кратно уменьшает кол-во проходов. Я потестил ui32 версию потому что хотелось строгий тест провести с наличием всех чисел. А для ui64 их в 2*32 раз больше... В принципе адаптировать из этого теперь элементарно. Но на полной последовательности просто забейте это дома считать... - на самом деле для хранения переполнения 16битным счетчикам не хватало бы 1го значения. Пробовал версию которая бьет диапазоны по 65535 чисел - тогда памяти требуется даже 128K + 8б, но из-за делений индексов и взятия остатков по модулю не степени 2ки - где-то вдвое падает производительность. Можно отдельные флаги переполнения ввести для групп потратив +8К и по скорости будет почти также. Но будет более запутанный код. - забавно сразу же прикладной фактор показал себя... пока тестил пришлось взять линейный конгруэнтный генератор, взял первый попавшийся из вики, и бах алг что то выбрасывает раньше, гляжу опять в вики в генераторе написано, что не все биты в нем используются (т.е. нет полной конгруэнтности, значит есть дубли) - и алг уже это показывал сразу. Причем даже с случайным сидом в основном отбрасывал на нескольких конкретных числах. Если бы нужно было проанализировать этот генератор, это была бы ценная информация для оценки куда копать
Задача 8 может решаться в один проход "подсчетом", отличающимся тем что считать нужно только однобитовый флаг присутствия (значит рабочая память будет M/8 байт) и тем, что при первой же необходимости прирастить счет значения которое уже равно 1 мы заканчиваем) Если из условия "Задача 8. В последовательности записано M+1 целое неотрицательное число" предполагать что сама последовательность влезает в память компьютера. (Хотя это может быть не так)
(Пишу потому что) Хотя иначе мы приходим все же к вашей же сложности, но с более практическим пониманием идеи диапазонов. Мы выделяем столько счетчиков "парности" сколько можем по памяти, а после считаем присутствие для значений, N старших бит которого указывают соответствующий групповой счетчик. (Эта классика и вызывает у меня стойкую ассоциацию с сортировкой подсчетом)
Оценка по памяти: 1Гб сможет адресовать 8_388_608 диапазонов по 23 старшим битам. Последующими проходами мы просто игнорируем все не интересующее за пределами выбранного диапазона (идентифицированного по старшим битам) и точно так же индексируем значения внутри него по следующим битам, повторяя пока биты не закончатся. Т.о. например за три прохода даже с 512Мб памяти мы уже сможем решать это для 64битных значений M.
Счетчиками парности я их назвал наводя на идею о том, что если завести не однобитовые а больше флаги, то можно искать таким образом и наибольшие/наименьшие значения встречающиеся более/менее чем N раз. Например с 4Гб памяти за 3 прохода можно найти наименьшее/большее 64битное число встречающееся более 2 или 3 раз. (что на больших разреженных числах выглядит довольно полезным инструментом выявления каких-то корреляций. Практическое приложение - анализ коллизий хэш функций/ или случайных генераторов на домашнем компе)
"Достигнуть предела" и поиметь XOR для большего числа состояний чем 2 можно опустившись глубже в терминологии. XOR это побитовая четность значений (ну или поразрядные суммы по модулю 2) Тут возникает даже 2 подхода к увеличению показателя. Можно все пересчитать в троичной системе, а можно двоичные разряды складывать в троичный накопитель. Но подумав еще немного станет понятно, что эффективнее подниматься сразу до 4-ичной системы. И так как нам не важен порядок разрядов (т.к. XOR его игнорирует по определению) можно все входящие значения "преобразовывать рассческой"
затем с пред коррекцией можно складывать по модулю 3 (по сути это троичный XOR)
addBitMod3=(sum, x){
let quaternit = x&0x5555 | (x&~0x5555)<<15;
let msk = ~3*(sum>>1 & quaternit) //4-чные разряды ожидающие сложения и уже >=2
return (sum&msk) //коррекция переполнения
+ (quaternit&msk); //сложение остальных
// после которого 4ичные разряды 0<=2 (что эквивалентно вычислениям в 3ичной)
}
Кстати говоря если вы параллельно с этим сделаете обычный 2-чный XOR по элементам, то из них обоих можно будет однозначно получить 6-чный XOR. И вообще пройдя так несколько-ичными XOR'ами вы получите XOR'ы всех их комбинаций (так что интереснее всего брать простые числа)
4-чная система конечно с другими коррекциями тоже считается, и даже пребывает в нормальной для компьютера форме. Т.е. в нее не надо переводить значения потому что 2чка ей кратна.
Upd: И конечно XOR далеко не только для экономии память на хаках... высокоуровневые программисты об этом узнают часто поздно. Он активно используется в алгоритмах избыточных данных с кодами коррекции. В прикладных нуждах к нему часто можно свести флаги хитро индексирующие БД и там это может заменять крайне тормознутые развернутые формы запросов.
Никто доподлинно не знает чем занимаются профессиональные математики, (слишком предельны абстракции) возможно даже сами они не всегда понимают... может балду гоняют... третью... Товарищ просто проверяет вдруг они плевать хотели на 150$k и эту проблему на самом деле ни кто давно не трогал...
Интересная задача, на сжатие диапазонов. На самом деле, с учетом отсутствием смысла хранить 0 (даже с учетом половин расстояния) сразу просится использовать значение 0 как 9й бит к следующему за ним байту. а если обобщать эту идею то использовать что-то вроде того как кодируется UTF (там в каждом приставном байте содержится пул для его дальнешейшего расширения дополнительными приставными) в частности очень эффективным оказывается то что только коды символов до 127 оказываются однобайтовыми, зато если старший бит 1 то оставшиеся 7 складываются со следующими в одно значение - таким образом получается резкий скачек на 15-ти битные значения. (в приложении к данной задаче это скорее оверхед) Но можно сделать гораздо интереснее числа >= 256 - 2**n интерперетировать как n бит должны присоединиться к следующему байту
для n=4 пример: Числа большие либо равные 256-2**4 = 240 // что в 2-чной b11110000 т.е. - с одной стороны мы совсем не много потеряли в доступном однобайтовом диапазоне 240/256 составляют 93.75% байтового диапазона - с другой стороны вторым байтом мы опционально получаем 12-ти битную индексацию вплоть до 4095 что составляет 4095/256 = 1600% однобайтного
n - выбирается эмпирически. еще n может быть динамическим в зависимости от текущего числа (оно будет строго расти, потому можно апроксимировать простым правилом сколько старших значений должны резервироваться под "расширяющие" биты) - с ростом n все сильнее будет срезаться однобайтовый диапазон. Но он всегда необходим для записи простых близнецов которые похоже попадаются бесконечно
в общем случае для всех последующих байт рекурсивно подходит та же конструкция расширения бит.
в свое время я реализовал алгебраическую систему с переменным основанием разряда и предикативным косвенным значением его максимума - это пожалуй апогей сжатия таким способом, но он ресурсоемок т.к. требует деления длинной арифметики пример без длинной арифметики тут: https://codepen.io/impfromliga/pen/xxggRoq - любители питона могут дешево интегрировать идею имя встроенную длинную арифметику (для объемных данных все равно придется числа дробить, иначе даже питон не справиться)
Вообще интересный вектор анализа простых чисел задает эта задача. Есть ли какая-то неравномерность вероятности появления конкретных диапазонов?
вспомнил тут вашу статью и то что озвученная выше идея псевдо-хаотического разброса давно реализована: https://codepen.io/impfromliga/pen/zYoVXZg - математика целочисленная, кондишнов нет (позаимствовано у Брезенхема, из реализации когда переполняющийся 9й бит математически сам едет куда надо) - на масках и сдвигах деление только на 2 - с отбросом из каналов последнего бита, реализовано вычисление всех каналов через uint32 типизированный массив единовременно
(получилось очень шустро и удается даже видео поток на JS дизерить, даже на мобиле)
ЧБ выглядит тоже достойно. (для алгоритма с одной линией по отсутствию паттернов лучше аналогов, при том что он быстрее даже самого быстрого из них "сиерры лайт" - на самом деле с него стартовала идея этого алгоритма) - в обоих скринах бралась гамма коррекция, сделанная через pow(x/255,1.5)*255 - функция усреднения цвета = среднее арифметическое
Но субъективно вижу чуть большее растекание - что логично, т.к. ошибка бросается пополам всего в 2 пиксела, и псевдо-хаотически может пройти больший путь пока ее влияние иссякнет (аналог некоторой составляющей блюр ядра)
Одноканальное ядро в базовом виде:
var errs= Array(w).fill(0);
for(var y=0; y<h; y++){
for(var e=0, x=0; x<w; x++){
var i= x+y*w;
var q=i<<2;
var cur= buf8[q] + e + errs[(i+(x%3)-1)%w];
errs[(i-1)%w]=e;
buf8[q]= buf8[q+1]= buf8[q+2]= (cur>255)*255;
cur&=255;
e=cur>>1;
}
y++;
for(var e=0, x=w; x--;){
var i= x+y*w;
var q=i<<2;
var cur= buf8[q] + e + errs[(i+((x+y)%3)-1)%w];
errs[(i+1)%w]=e;
buf8[q]= buf8[q+1]= buf8[q+2]= (cur>255)*255;
cur&=255;
e=cur>>1;
}
}
Ковырял Интловый Фильтр, в надежде приспособить его под Ланцош. (Который прекрасно заездит как детектор конкретной частоты, не в пример быстрее чем БПФурье для всего спектра - отличный трай для гитарного тюнера, на ущербных микроконтроллерах почти без ОЗУ - ему надо всего 3 переменных состояния!!!)
Внезапно оказалось что интловый фильтр и есть Ланцоша... просто его частный случай подгоняется под Гаус Блюр (вероятно коэфициентами при х - т.к. кроме амплитуды визуальных закономерностей от них больше не выявлено - либо их можно упростить, либо они возможно позволяют как то просто управлять альфа кривой. Хотя это не поясняется в оригинале.)
В целом мой фильтр размытия "Лапласа" дает максимально похожую картину распределения, за исключением пика на котором и теряется 3% точности, и теперь мне кажется что кулибины из Intel не особо старались в оптимайз, на самом деле просто юзнули какой то общий IIR фильтр Ланцоша... под блюр подгонкой пары коэффициентов.
В принципе если бы мой 97% точный блюр на Лапласе не был в 4ро быстрее на сдвигах и масках, чем их типа честный Гаус на SSE... то я бы мог тоже подгонные коэффициенты ввести. Плюс на флоат этот отвязывается от константного радиуса
- можно каскадировать для большего кол-ва коммутаций, включая какие-то подготовительные включения цепей (например цепи кулера охлаждения) или сервы открывающей кран перед запуском насоса...
забавно я не то что бы увлекаюсь ардуиной сильнее RAW схемотехники, но как весовое слово его стал почти всегда добавлять при гуглении чего то схемотехнического, даже если мне точно не нужна ардуина или вообще микроконтроллер (как и в этот раз). Работу свою для генерализации медиа они сделали )
есть стойкое предположение что годно просчитанная под элементную базу схема может работать на очень дрянной элементной базе надежнее чем решение баблом.
кстати говоря кое что есть. Но это тоже фокус. За точку опоры можно взять гиростатический эффект. Так над кольцевым магнитом некоторое время вполне сам висит раскрученный магнитный волчок. Увы временно. Но все же сам ))
Клиент в большинстве сетевых игр и в абсолютно всех серьезных сетевых шутерах делает экстраполяцию таймингов, иначе бы в действительности на практике играть можно было бы только с игроками в одной локальной подсети. С этим связан run хак, когда клиент имеется возможность безпаливно пропатчить.
Задержка осознанного восприятия образов у мозга в лучшем случае 80мс Ниже это почти наверняка стрельба по паттерну и уж точно не различение свой/чужой. Просто опытный игрок ожидает в конкретное время появления противника в конкретных местах, так время падает вдвое по принципу "ближайшие 3 секунды пали во все что движется" или это вообще стрельба на упреждение, когда из-за угла выходишь просто зная что там обычно враги - (тут вообще нет времени реакции а есть другое)
Тайминги экстраполяции у нас в мозгу тоже работают, потому самураи могут разрубать теннисные мячики пущенные в них машинкой (и даже более мелкие объекты) - физических скоростей глаза не достаточно для того что бы увидеть объект в месте нанесения хита, по сути видны только треки, место наилучшего удара предсказывается неосознанно. - это кстати следствие недостаточности порой и 60 fps для игр против и 30 норм для видео - (видео снимается физической камерой и там есть время выдержки и треки объектов) потому так же в играх разительного увеличивают "кажущуюся" плавность эффекты моушн-блюр, при фактическом может даже проседании fps (они симулируют треки быстро движущихся объектов - мозгу это помогает получать более полную информацию об их скорости, с учетом того что из единственного цифрового обычного срендеренного кадра скорость визуально получить неоткуда)
собственно это основное фундаментальное отличие глаза от монитора обо что большинство поверхностных споров "сколько кадров видит глаз" разбиваются
вообще если бы устройства вывода и вывода могли секьюрно сообщать свою аппаратную задержку движку игры, их можно было бы вносить в рассчет экстраполяции, может когда-нибудь индустрия к этому и прийдет
Вы просто не пробовали программировать демосцену =)
так как фирм ограниченное (штучное) кол-во - достаточно соорудить мастер брелок который перебирает мастер ключи по очереди (по сути перебор паролей по словарю)
- откроются все что прошиты в брелок (хотя работать будет медленнее чем родные ключи)
другой вопрос что могут додуматься НЕ делать одинаковые для всех домофонов серии мастер ключи. (Потому что обслуживающая контора в принципе может сама осуществлять сервис, и хранить базу уникальных ключей по адресам установки. И ДАЖЕ может передавать брелоку серийник домофона, из которого последний вычисляет по крипто алгоритму с закрытым ключом ключ для конкретного домофона.) - разобрать такой уже равноценно утечке закрытого ключа из конторы. Который может вообще не фигурировать в прошивках. (в мастер брелоке его можно выполнять в виде крипто чипа у которого ключ наружу не отдается. В прошивке домофона фигурирует только открытый)
- но это довольно серьезная степень запарки на стадии разработки.
Хотя я уверен что какой то завод уже выпускает такие чипы как независимый компонент, ключ в который можно прошить однократно при инициализации.
В принципе можно взять огромное кол-во популярных дешманских микроконтроллеров, даже AVR'ы имеют режим прошивки с фьюзами которые запрещают дальнейшие способы перезаписи, а тем более чтение прошивки - в любой из таких можно положить единоразово релизнутую (и затем хранимую аки зеницу ока) прошивку с закрытым ключем, с которой брелок способен по сути проходить челлендж-алгоритм цифровой подписи. Благо в функциональности ключа вероятно прошивать абсолютно нечего, потому эти ключи может изготавливать единственный сертифицированный центр. А может и вообще единственный человек. (в таким образом прошим брелоке можно заложить функционал "мастер ключа" уже для него - который принимается единожды, для записи закрытого в ПЗУ и финализации защит - через сам 1-wire можно пачками инициировать такие ключи прописывая в них только закрытый ключ)
- устройства не обладающие таким способом защиты кстати уязвимы для скимминга (когда на хост крепиться фэйковая "морда" не мешающая втыканию ключа, но снифающая обмен данными) в случае с 1-wire интерфейсом такое устройство может быть чрезвычайно миниатюрным просто ободком поверх разъема i-button
забавно отметить, что подобный скиммер (с учетом того что скимеры на домофонах чрезвычайно не встречающийся анахренизм) могут долго висеть постоянно... и могут собирать данные о времени регистрации уже вас на точке... (потому что у ключей обычно есть id) в периодически забиераемый тем же i-button ключом... такие шпионские штучки
Кстати говоря напишите где по этому методу вы встречали теорию, если помните...
Я этот метод открыл независимо, и практикую.
И он мне кажется настолько крут, что я чувствую необходимым по нему писать подробную статью на Хабр. Ощущение, будто я рискую общечеловеческим достоянием пока не отписал (ибо смертен)
Однако такой материал находиться на стыке математики и программирования. А я в математике самоучка и терминологически подкован плохо. Знаю как работает, но как популярно объяснить испытываю трудности. Если существует какая-то математическая терминология на этот счет на нее очень было бы полезно сослаться.
Кстати говоря мало того что, метод требует только сложений, они в нем с т.з. параллелизма еще и все НЕзависимые!
что как бы говорит о том, что вычисления полинома N-ой степени на суперскалярной архитектуре, количество параллельных сумматоров в которой может вместить все коэффициенты (А их сейчас в среднем по 3 на ядро, при среднем количестве ядер = 4 это 12 штук) может вычислять полином степени на единицу меньшей чем их количество ЗА ОДИН ТАКТ!!!
И даже это еще не все... на самом деле независимость сложения позволяет продемонстрировать это в еще более дерзкой форме, т.к. по сути для этих вычислений важна скорее общая битовая размерность сумм. И если скрестить это с битхакерскими техниками группировки разрядов в одну переменную, то можно параллельности добиться на однопоточной машине и без супперскалярности, просто используя младшие биты результата. Следующий пример на JS вернет параболу (полином 2й степени) используя на точку только одно сложение ui32 числа со своими же старшими разрядами
в принципе даже сдвига здесь можно избежать, если он будет на четное кол-во байт, тогда память с хранимым значением можно будет с другим отступом просто замапить в альтернативную переменную (даже на JS это уже можно сделать с TypedArray, не говоря про Си)
а еще на многих машинах есть SIMD инструкции - которые позволят аж 128битами оперировать нарезая их как надо на "виртуальные разряды"
умножение это операция порождающая связность битовых разрядов (в принципе имеющая матричную природу) - все упрощения умножения полиномов будут алгебраически иметь ту же природу что и методы быстрого умножения матриц. А потому построение вычислений на независимых операциях умножения это строго в противоположную сторону оптимизация. И короткий ответ нет нельзя.
Однако это не касается длинной арифметики - если вы вычисляете что-то где единственный операнд представляется в виде массива данных, то там есть методы реализации длинной арифметики, которые часть вычислений могут выполнять независимо, за счет чего ускоряться. - НО это по сути не относиться к алгоритму самого умножения полинома
если вы говорите про float вычисления, то при сокращении числа умножений средне ожидаемая ошибка будет тоже сокращаться. Так что скорее более точный получится. Количество же сложений не имеет значения, потому что ошибка на них (имеющаяся и в схеме Горнера) может в обоих случаях вычисляться алгоритмом компенсационного суммирования Кэхэна. ну и если надо абсолютно точно то вы обычно берете длинную арифметику - которая уже только ускорятся будет от использования более оптимизированных схемм
Помниться забавы ради развлекался изучал что можно "выжать" из второй степени без всяких разбиений - первая проблема собственно что парабола относительно совпадает с косинусом до 90 градусов если ее просто отмасштабировать получается полином `cos=x=>1-.4053*x*x`.
Через формулы приведения можно бы получить то же и для синуса, но в такой формуле появляется перемена знака... и нужен был как бы назвать "инверсный квадрат" - при возведении в который всегда получается отрицательный знак... тогда бы получалось 2й степенью обойтись без кондишнов и для синуса. В итоге это развернулось что один из иксов в формулу берется с отбросом знака.
В принципе для максимально быстрого отброса знака почти честно можно ксорить все биты числа на его знаковый бит, для этого (вероятнее всего у вас не будет float который бы работал еще и с XOR) понадобиться пересчитать найденные константы в арифметику статической точки, что бы все считать в целых
погрешность может быть уменьшена ценой потери контрольных точек `sin=x=>(1.217-0.38529*Math.abs(x))*x` до 3.9% но обычно точность контрольных точек чрезвыйчайно ожидается множеством алгоритмов, которые без нее могут начать работать не правильно.
Поискать наиболее проблемные места поможет такой тест (выводящий последние 30 мест с наибольшей ошибкой) Параметром количества шагов можно "позумить" детализацию (таким образом можно как быстро отыскать в целом проблемные места, так и отдельные участки посмотреть точнее)
оказалось что в некоторых случаях 5% погрешности вполне визуально допустимы.
Еще стоит вспомнить что столько степень полинома ресурсозатратна сколько количество членов и например формула синуса на основе коэффициентов Тэзлора 5го порядка уже довольно визуально точна но в ней нет 2го и 4го членов `sinTailor5=x=>x - x**3/6 + x**5/120` что то же самое что `x(1-xx(1/6+xx/120)`, где на возведениях в квадрат экономим заводя переменную xx. Важно так же отметить что эта формула является частичной суммой, потому не оптимальна, и ее как и формулу до 3го порядка `x=> x - x**3/6` можно значительно подтюнить масштабированием коэффициентов.
Так же не стоит забывать, если вы почему-то считаете много синусов, то если у вас получиться их хотя бы равномерно упорядочить, то полином может считаться феерически быстро дельта функциями. В этом случае дело в том, что значение sinTailor5(x+dx) отличается от sinTailor5(x) на полином меньшей на один степени (потому что см. степенная производная)
Тот отличается от предыдущего на полином третьей, который отличается на полином 2ой... короче... итеративный счет полинома 5й степени это не больше 6 сложений - гарантировано.
Когда я говорю не больше я имею ввиду что может быть и меньше, но это уже отдельная битхакерская песня... В качестве задачи с двумя звездочками на досуге можете сунуть ЭТО в консоль броузера и подумать как и почему это оно выводит квадраты (учитывая что в цикле только есть умножение на константу):
Попробовал решение 8й задачи на всех ui32 числах. С тестом как водиться провозился дольше чем с алгоритмом. В итоге:
- тест на JS и работает из консоли браузера
- лог асинхронный (что позволяет вкладке не виснуть намертво до конца выполнения) выводит процент готовности прохода в консоль (всего их два)
- потребление памяти 256Кб
- скорость обхода 2**k+2 чисел ~219s (3 с половиной минуты на ryzen 9)
- тестируется LCG PRNG последовательность всех ui32 чисел + в конец ее добавляется дважды случайно взятое число (оно и будет давать коллизию)
Дополнения:
- в принципе 2**32 чисел это всего то 2**29 = 536 870 912 байт индекса, что можно побитово замапить флагами четности и решить за один проход вдвое быстрее, но потратив 512Мбайт вместо 256Кбайт. Можно оценить разницу по памяти. Впрочем работая с ui64 надо именно так поступать, потому что битность кратно уменьшает кол-во проходов. Я потестил ui32 версию потому что хотелось строгий тест провести с наличием всех чисел. А для ui64 их в 2*32 раз больше... В принципе адаптировать из этого теперь элементарно. Но на полной последовательности просто забейте это дома считать...
- на самом деле для хранения переполнения 16битным счетчикам не хватало бы 1го значения. Пробовал версию которая бьет диапазоны по 65535 чисел - тогда памяти требуется даже 128K + 8б, но из-за делений индексов и взятия остатков по модулю не степени 2ки - где-то вдвое падает производительность. Можно отдельные флаги переполнения ввести для групп потратив +8К и по скорости будет почти также. Но будет более запутанный код.
- забавно сразу же прикладной фактор показал себя... пока тестил пришлось взять линейный конгруэнтный генератор, взял первый попавшийся из вики, и бах алг что то выбрасывает раньше, гляжу опять в вики в генераторе написано, что не все биты в нем используются (т.е. нет полной конгруэнтности, значит есть дубли) - и алг уже это показывал сразу. Причем даже с случайным сидом в основном отбрасывал на нескольких конкретных числах. Если бы нужно было проанализировать этот генератор, это была бы ценная информация для оценки куда копать
Задача 8 может решаться в один проход "подсчетом", отличающимся тем что считать нужно только однобитовый флаг присутствия (значит рабочая память будет M/8 байт) и тем, что при первой же необходимости прирастить счет значения которое уже равно 1 мы заканчиваем)
Если из условия "Задача 8. В последовательности записано M+1 целое неотрицательное число" предполагать что сама последовательность влезает в память компьютера. (Хотя это может быть не так)
(Пишу потому что) Хотя иначе мы приходим все же к вашей же сложности, но с более практическим пониманием идеи диапазонов. Мы выделяем столько счетчиков "парности" сколько можем по памяти, а после считаем присутствие для значений, N старших бит которого указывают соответствующий групповой счетчик. (Эта классика и вызывает у меня стойкую ассоциацию с сортировкой подсчетом)
Оценка по памяти: 1Гб сможет адресовать 8_388_608 диапазонов по 23 старшим битам. Последующими проходами мы просто игнорируем все не интересующее за пределами выбранного диапазона (идентифицированного по старшим битам) и точно так же индексируем значения внутри него по следующим битам, повторяя пока биты не закончатся. Т.о. например за три прохода даже с 512Мб памяти мы уже сможем решать это для 64битных значений M.
Счетчиками парности я их назвал наводя на идею о том, что если завести не однобитовые а больше флаги, то можно искать таким образом и наибольшие/наименьшие значения встречающиеся более/менее чем N раз. Например с 4Гб памяти за 3 прохода можно найти наименьшее/большее 64битное число встречающееся более 2 или 3 раз. (что на больших разреженных числах выглядит довольно полезным инструментом выявления каких-то корреляций. Практическое приложение - анализ коллизий хэш функций/ или случайных генераторов на домашнем компе)
"Достигнуть предела" и поиметь XOR для большего числа состояний чем 2 можно опустившись глубже в терминологии. XOR это побитовая четность значений (ну или поразрядные суммы по модулю 2) Тут возникает даже 2 подхода к увеличению показателя. Можно все пересчитать в троичной системе, а можно двоичные разряды складывать в троичный накопитель. Но подумав еще немного станет понятно, что эффективнее подниматься сразу до 4-ичной системы. И так как нам не важен порядок разрядов (т.к. XOR его игнорирует по определению) можно все входящие значения "преобразовывать рассческой"
затем с пред коррекцией можно складывать по модулю 3 (по сути это троичный XOR)
Кстати говоря если вы параллельно с этим сделаете обычный 2-чный XOR по элементам, то из них обоих можно будет однозначно получить 6-чный XOR. И вообще пройдя так несколько-ичными XOR'ами вы получите XOR'ы всех их комбинаций (так что интереснее всего брать простые числа)
4-чная система конечно с другими коррекциями тоже считается, и даже пребывает в нормальной для компьютера форме. Т.е. в нее не надо переводить значения потому что 2чка ей кратна.
Upd: И конечно XOR далеко не только для экономии память на хаках... высокоуровневые программисты об этом узнают часто поздно. Он активно используется в алгоритмах избыточных данных с кодами коррекции. В прикладных нуждах к нему часто можно свести флаги хитро индексирующие БД и там это может заменять крайне тормознутые развернутые формы запросов.
Никто доподлинно не знает чем занимаются профессиональные математики, (слишком предельны абстракции) возможно даже сами они не всегда понимают... может балду гоняют... третью...
Товарищ просто проверяет вдруг они плевать хотели на 150$k и эту проблему на самом деле ни кто давно не трогал...
Интересная задача, на сжатие диапазонов. На самом деле, с учетом отсутствием смысла хранить 0 (даже с учетом половин расстояния) сразу просится использовать значение 0 как 9й бит к следующему за ним байту. а если обобщать эту идею то использовать что-то вроде того как кодируется UTF (там в каждом приставном байте содержится пул для его дальнешейшего расширения дополнительными приставными)
в частности очень эффективным оказывается то что только коды символов до 127 оказываются однобайтовыми, зато если старший бит 1 то оставшиеся 7 складываются со следующими в одно значение - таким образом получается резкий скачек на 15-ти битные значения. (в приложении к данной задаче это скорее оверхед) Но можно сделать гораздо интереснее числа >= 256 - 2**n интерперетировать как n бит должны присоединиться к следующему байту
для n=4 пример: Числа большие либо равные 256-2**4 = 240 // что в 2-чной b11110000 т.е.
- с одной стороны мы совсем не много потеряли в доступном однобайтовом диапазоне 240/256 составляют 93.75% байтового диапазона
- с другой стороны вторым байтом мы опционально получаем 12-ти битную индексацию вплоть до 4095 что составляет 4095/256 = 1600% однобайтного
n - выбирается эмпирически. еще n может быть динамическим в зависимости от текущего числа (оно будет строго расти, потому можно апроксимировать простым правилом сколько старших значений должны резервироваться под "расширяющие" биты)
- с ростом n все сильнее будет срезаться однобайтовый диапазон. Но он всегда необходим для записи простых близнецов которые похоже попадаются бесконечно
в общем случае для всех последующих байт рекурсивно подходит та же конструкция расширения бит.
в свое время я реализовал алгебраическую систему с переменным основанием разряда и предикативным косвенным значением его максимума - это пожалуй апогей сжатия таким способом, но он ресурсоемок т.к. требует деления длинной арифметики
пример без длинной арифметики тут: https://codepen.io/impfromliga/pen/xxggRoq
- любители питона могут дешево интегрировать идею имя встроенную длинную арифметику (для объемных данных все равно придется числа дробить, иначе даже питон не справиться)
Вообще интересный вектор анализа простых чисел задает эта задача.
Есть ли какая-то неравномерность вероятности появления конкретных диапазонов?
вспомнил тут вашу статью и то что озвученная выше идея псевдо-хаотического разброса давно реализована: https://codepen.io/impfromliga/pen/zYoVXZg
- математика целочисленная, кондишнов нет (позаимствовано у Брезенхема, из реализации когда переполняющийся 9й бит математически сам едет куда надо)
- на масках и сдвигах деление только на 2
- с отбросом из каналов последнего бита, реализовано вычисление всех каналов через uint32 типизированный массив единовременно
(получилось очень шустро и удается даже видео поток на JS дизерить, даже на мобиле)
ЧБ выглядит тоже достойно. (для алгоритма с одной линией по отсутствию паттернов лучше аналогов, при том что он быстрее даже самого быстрого из них "сиерры лайт" - на самом деле с него стартовала идея этого алгоритма)
- в обоих скринах бралась гамма коррекция, сделанная через pow(x/255,1.5)*255
- функция усреднения цвета = среднее арифметическое
Но субъективно вижу чуть большее растекание
- что логично, т.к. ошибка бросается пополам всего в 2 пиксела, и псевдо-хаотически может пройти больший путь пока ее влияние иссякнет (аналог некоторой составляющей блюр ядра)
Одноканальное ядро в базовом виде:
Ковырял Интловый Фильтр, в надежде приспособить его под Ланцош.
(Который прекрасно заездит как детектор конкретной частоты, не в пример быстрее чем БПФурье для всего спектра - отличный трай для гитарного тюнера, на ущербных микроконтроллерах почти без ОЗУ - ему надо всего 3 переменных состояния!!!)
Внезапно оказалось что интловый фильтр и есть Ланцоша... просто его частный случай подгоняется под Гаус Блюр (вероятно коэфициентами при х - т.к. кроме амплитуды визуальных закономерностей от них больше не выявлено - либо их можно упростить, либо они возможно позволяют как то просто управлять альфа кривой. Хотя это не поясняется в оригинале.)
В целом мой фильтр размытия "Лапласа" дает максимально похожую картину распределения, за исключением пика на котором и теряется 3% точности, и теперь мне кажется что кулибины из Intel не особо старались в оптимайз, на самом деле просто юзнули какой то общий IIR фильтр Ланцоша... под блюр подгонкой пары коэффициентов.
В принципе если бы мой 97% точный блюр на Лапласе не был в 4ро быстрее на сдвигах и масках, чем их типа честный Гаус на SSE... то я бы мог тоже подгонные коэффициенты ввести. Плюс на флоат этот отвязывается от константного радиуса
Ну или если я перепишу на SSE то вздеру ихний по скорости раз в 5...
трай https://codepen.io/impfromliga/pen/OJoeeRb
Будучи еще програмером, должен заметить интересно углядывается схемный паттерн LIFO (последним включился - первым выключиться), если посмотреть на коммутирующую часть как на мост: https://falstad.com/circuit/circuitjs.html?ctz=CQAgjCAMB0l3BWcMBMcUHYMGZIA4UA2ATmIxAUgpABZsKBTAWjDACgATEbbQkFBHxR48-fPxAcGAMwCGAVwA2AF078RY0ShpUBQyTIUq2AY269+g9aNw0oUWPAhMYkYijDaMxGsUgpiEl8HOHYzbV0rYRtIOypXJ25YQLxIMAxfbBRsBDBIJAT2ACdzIR1rcHd7PLg2EujKlH5yiOr4NgB3CrQtDTAqyE7wQipbYd0MJsGu1r1m3XLp0ss+HjL4tmlluZowISss8GgC2BRN+ZXxy8OwY5Czrt2hSdo97lioIb3Rj4axpae7zsfw+gwA5hUxn8LBsAEoVfpNBpgGh2CBNGr8O4oO7xY5sIA
- можно каскадировать для большего кол-ва коммутаций, включая какие-то подготовительные включения цепей (например цепи кулера охлаждения) или сервы открывающей кран перед запуском насоса...
забавно я не то что бы увлекаюсь ардуиной сильнее RAW схемотехники, но как весовое слово его стал почти всегда добавлять при гуглении чего то схемотехнического, даже если мне точно не нужна ардуина или вообще микроконтроллер (как и в этот раз). Работу свою для генерализации медиа они сделали )
есть стойкое предположение что годно просчитанная под элементную базу схема может работать на очень дрянной элементной базе надежнее чем решение баблом.
Так когда то и на лампах в космос летали...
кстати говоря кое что есть. Но это тоже фокус. За точку опоры можно взять гиростатический эффект. Так над кольцевым магнитом некоторое время вполне сам висит раскрученный магнитный волчок. Увы временно. Но все же сам ))
к сожалению отрицательной массы пока в природе не найдено, а у магнита монополя. Так что тут даже абстрактно расная "архитектура" явлений
Клиент в большинстве сетевых игр и в абсолютно всех серьезных сетевых шутерах делает экстраполяцию таймингов, иначе бы в действительности на практике играть можно было бы только с игроками в одной локальной подсети. С этим связан run хак, когда клиент имеется возможность безпаливно пропатчить.
Задержка осознанного восприятия образов у мозга в лучшем случае 80мс Ниже это почти наверняка стрельба по паттерну и уж точно не различение свой/чужой. Просто опытный игрок ожидает в конкретное время появления противника в конкретных местах, так время падает вдвое по принципу "ближайшие 3 секунды пали во все что движется" или это вообще стрельба на упреждение, когда из-за угла выходишь просто зная что там обычно враги - (тут вообще нет времени реакции а есть другое)
Тайминги экстраполяции у нас в мозгу тоже работают, потому самураи могут разрубать теннисные мячики пущенные в них машинкой (и даже более мелкие объекты) - физических скоростей глаза не достаточно для того что бы увидеть объект в месте нанесения хита, по сути видны только треки, место наилучшего удара предсказывается неосознанно. - это кстати следствие недостаточности порой и 60 fps для игр против и 30 норм для видео - (видео снимается физической камерой и там есть время выдержки и треки объектов) потому так же в играх разительного увеличивают "кажущуюся" плавность эффекты моушн-блюр, при фактическом может даже проседании fps (они симулируют треки быстро движущихся объектов - мозгу это помогает получать более полную информацию об их скорости, с учетом того что из единственного цифрового обычного срендеренного кадра скорость визуально получить неоткуда)
собственно это основное фундаментальное отличие глаза от монитора обо что большинство поверхностных споров "сколько кадров видит глаз" разбиваются
вообще если бы устройства вывода и вывода могли секьюрно сообщать свою аппаратную задержку движку игры, их можно было бы вносить в рассчет экстраполяции, может когда-нибудь индустрия к этому и прийдет
даже не сразу понял как это плюсы, и где семиколоны... надеюсь этот одаренный делает это линтером...