singlskv 0 3 апреля, 2009 Опубликовано 3 апреля, 2009 · Жалоба угу. За одну. x0 = y & 1;не, за одну никак x1:0 y1:0 00 00 01 01 10 11 11 10 00 10 01 11 10 01 11 00 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
xemul 0 3 апреля, 2009 Опубликовано 3 апреля, 2009 · Жалоба не, за одну никак А как за две? Минимальный период по парам (y._;x.0) получается 16, т.е. воспроизвести x.0 можно по комбинации 4 битов. Карта Карно x.0=K(y.0,.., y.3) получается однозначная, но совсем невкусная. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Сергей Борщ 134 3 апреля, 2009 Опубликовано 3 апреля, 2009 · Жалоба не, за одну никакДа, это я погорячился. Не, ну рекурсия это, конечно, от бога. Но после разворачивания рекурсии из того ответа весь алгоритм вырождается в uint32_t decode2(uint32_t y, uint_fast8_t k) { if(y < 2) return y; uint32_t Result = y & 1; for(uint32_t Mask = (1<<1) | (1<<0); Mask < 1ULL << k; Mask = (Mask << 1) | (1 << 0) ) { uint32_t n = ((Result * (Result + 1)) >> 1) & Mask; if( n != (y & Mask) ) Result ^= Mask; } return Result; } Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
singlskv 0 3 апреля, 2009 Опубликовано 3 апреля, 2009 · Жалоба Но после разворачивания рекурсии из того ответа весь алгоритм вырождается в Я понял в чем ошибка в алгоритме Oldring Отсюда b есть k-й бит 2y - с(с+1) нужно маску на Y накладывать 2*(y mod 2^(k-1)) - c(c+1) Если не заленюсь позже набрасаю на ЦЕ. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
singlskv 0 3 апреля, 2009 Опубликовано 3 апреля, 2009 · Жалоба А как за две? Минимальный период по парам (y._;x.0) получается 16, т.е. воспроизвести x.0 можно по комбинации 4 битов. Карта Карно x.0=K(y.0,.., y.3) получается однозначная, но совсем невкусная. Нет, воспроизвести и по 16 не получится, последний бит в X определяется по всем битам Y. Но это совсем даже не страшно, первый бит можно выбрать любым. После получения всех битов X просто проверяем и корректируем: if (x*(x+1)/2 mod 2^k != Y) X=!X; ЗЫ. А похоже можно вобще без умножений обойтись... Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
KRS 1 3 апреля, 2009 Опубликовано 3 апреля, 2009 · Жалоба а ведь X * (X+1) / 2 это формула суммы арифметической прогрессии ( ряд от 0 до n с шагом 1 ) S = (a1 + an)*n/2 = ( 0 + X ) * (X+1)/2 т.е это младшие биты суммы всех чисел от 0 до X может это поможет? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
singlskv 0 3 апреля, 2009 Опубликовано 3 апреля, 2009 · Жалоба а ведь X * (X+1) / 2 это формула суммы арифметической прогрессии ( ряд от 0 до n с шагом 1 ) S = (a1 + an)*n/2 = ( 0 + X ) * (X+1)/2 т.е это младшие биты суммы всех чисел от 0 до X может это поможет? это уже было в посте №7 причем от автора топика, вопрос только в самом быстром решении... Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Oldring 0 9 апреля, 2009 Опубликовано 9 апреля, 2009 · Жалоба угу. За одну. x0 = y & 1; Нет. 5*6/2 = 15 6*7/2 = 21 Я понял в чем ошибка в алгоритме Oldring Протестировал до N = 2^16 Нет там ошибок. Младший бит X можно перебирать, вычисляя все биты дважды, а можно начать с нулевого младшего бита и в конце вычислить X = 2^N - 1 - X, что вообще-то равно побитовой инверсии X, если старший бит Y оказался неправильным. Думаю, что легко организовать побитовую итерацию без умножений. Цикл сводится к проверке младшего бита, двум N-битовым сдвигам (по одному биту вправо и влево), N-битовому вычитанию и N-битовому ИЛИ. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
singlskv 0 9 апреля, 2009 Опубликовано 9 апреля, 2009 · Жалоба Протестировал до N = 2^16 Нет там ошибок. Я говорил только о маске по 2^k-1, хм..., а возможно она правда и не нужна... Младший бит X можно перебирать, вычисляя все биты дважды, а можно начать с нулевого младшего бита и в конце вычислить X = 2^N - 1 - X, что вообще-то равно побитовой инверсии X, если старший бит Y оказался неправильным.Дважды это медленно, в посте N20 я и предложил посчитать от любого начального а потом инверсию... Думаю, что легко организовать побитовую итерацию без умножений. Цикл сводится к проверке младшего бита, двум N-битовым сдвигам (по одному биту вправо и влево), N-битовому вычитанию и N-битовому ИЛИ. что-то подобное и я хотел соорудить, но оказалось что это имеет смысл тока для процов где нет быстрого умножения или маленькая разрядность данных. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Oldring 0 10 апреля, 2009 Опубликовано 10 апреля, 2009 · Жалоба Я говорил только о маске по 2^k-1, хм..., а возможно она правда и не нужна... Она не только не нужна, но может быть и вредна, так как будет левый заем из рассматриваемого бита. что-то подобное и я хотел соорудить, но оказалось что это имеет смысл тока для процов где нет быстрого умножения или маленькая разрядность данных. Или для HDL, или для процов, где умножение занимает несколько тактов ;) Если заниматься микрооптимизацией - любой вариант может оказаться лучше. На VLIW процессорах думаю цикл можно за два такта на бит делать. Как за один - любопытная головоломка ;) Кстати, еще вариант - сразу бит по 8-16 таблично вычислять, наверное возможно... Если обращение к памяти достаточно быстрое. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться