| |
 Найти обратное преобразование, y = (x * (x+1) / 2) mod N |
|
|
|
|
 Apr 3 2009, 09:12
|
дятел
Группа: Свой
Сообщений: 1 681
Регистрация: 13-05-06
Из: Питер
Пользователь №: 17 065
|
Цитата(Сергей Борщ @ Apr 3 2009, 09:31)  угу. За одну. x0 = y & 1; не, за одну никак Код x1:0 y1:0
00 00
01 01
10 11
11 10
00 10
01 11
10 01
11 00
|
|
|
|
|
|
|
|
Apr 3 2009, 11:31
|
Гуру
Группа: Модераторы
Сообщений: 8 455
Регистрация: 15-05-06
Из: Рига, Латвия
Пользователь №: 17 095
|
Цитата(singlskv @ Apr 3 2009, 12:12) не, за одну никак Да, это я погорячился. Не, ну рекурсия это, конечно, от бога. Но после разворачивания рекурсии из того ответа весь алгоритм вырождается в Код 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;
}
--------------------
На любой вопрос даю любой ответ"Write code that is guaranteed to work, not code that doesn’t seem to break" ( C++ FAQ)
|
|
|
|
|
|
|
|
Apr 3 2009, 12:31
|
дятел
Группа: Свой
Сообщений: 1 681
Регистрация: 13-05-06
Из: Питер
Пользователь №: 17 065
|
Цитата(Сергей Борщ @ Apr 3 2009, 15:31) Но после разворачивания рекурсии из того ответа весь алгоритм вырождается в Я понял в чем ошибка в алгоритме OldringЦитата Отсюда b есть k-й бит 2y - с(с+1) нужно маску на Y накладывать 2*(y mod 2^(k-1)) - c(c+1) Если не заленюсь позже набрасаю на ЦЕ.
|
|
|
|
|
|
|
|
Apr 3 2009, 14:20
|
дятел
Группа: Свой
Сообщений: 1 681
Регистрация: 13-05-06
Из: Питер
Пользователь №: 17 065
|
Цитата(xemul @ Apr 3 2009, 15:12) А как за две?
Минимальный период по парам (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; ЗЫ. А похоже можно вобще без умножений обойтись...
|
|
|
|
|
|
|
|
Apr 9 2009, 08:00
|
Гуру
Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874
|
Цитата(Сергей Борщ @ Apr 3 2009, 09:31) угу. За одну. x0 = y & 1; Нет. 5*6/2 = 15 6*7/2 = 21 Цитата(singlskv @ Apr 3 2009, 16:31) Я понял в чем ошибка в алгоритме Oldring Протестировал до N = 2^16 Нет там ошибок. Младший бит X можно перебирать, вычисляя все биты дважды, а можно начать с нулевого младшего бита и в конце вычислить X = 2^N - 1 - X, что вообще-то равно побитовой инверсии X, если старший бит Y оказался неправильным. Думаю, что легко организовать побитовую итерацию без умножений. Цикл сводится к проверке младшего бита, двум N-битовым сдвигам (по одному биту вправо и влево), N-битовому вычитанию и N-битовому ИЛИ.
--------------------
Пишите в личку.
|
|
|
|
|
|
|
|
Apr 9 2009, 18:52
|
дятел
Группа: Свой
Сообщений: 1 681
Регистрация: 13-05-06
Из: Питер
Пользователь №: 17 065
|
Цитата(Oldring @ Apr 9 2009, 12:00) Протестировал до N = 2^16
Нет там ошибок. Я говорил только о маске по 2^k-1, хм..., а возможно она правда и не нужна... Цитата Младший бит X можно перебирать, вычисляя все биты дважды, а можно начать с нулевого младшего бита и в конце вычислить X = 2^N - 1 - X, что вообще-то равно побитовой инверсии X, если старший бит Y оказался неправильным. Дважды это медленно, в посте N20 я и предложил посчитать от любого начального а потом инверсию... Цитата Думаю, что легко организовать побитовую итерацию без умножений. Цикл сводится к проверке
младшего бита, двум N-битовым сдвигам (по одному биту вправо и влево), N-битовому вычитанию и N-битовому ИЛИ. что-то подобное и я хотел соорудить, но оказалось что это имеет смысл тока для процов где нет быстрого умножения или маленькая разрядность данных.
|
|
|
|
|
|
|
|
Apr 10 2009, 08:16
|
Гуру
Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874
|
Цитата(singlskv @ Apr 9 2009, 22:52) Я говорил только о маске по 2^k-1, хм..., а возможно она правда и не нужна... Она не только не нужна, но может быть и вредна, так как будет левый заем из рассматриваемого бита. Цитата(singlskv @ Apr 9 2009, 22:52) что-то подобное и я хотел соорудить, но оказалось что это имеет смысл тока для процов где нет быстрого
умножения или маленькая разрядность данных. Или для HDL, или для процов, где умножение занимает несколько тактов  Если заниматься микрооптимизацией - любой вариант может оказаться лучше. На VLIW процессорах думаю цикл можно за два такта на бит делать. Как за один - любопытная головоломка Кстати, еще вариант - сразу бит по 8-16 таблично вычислять, наверное возможно... Если обращение к памяти достаточно быстрое.
--------------------
Пишите в личку.
|
|
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|
