[singlskv 0]

угу. За одну. 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]

не, за одну никак

А как за две?

Минимальный период по парам (y._;x.0) получается 16, т.е. воспроизвести x.0 можно по комбинации 4 битов. Карта Карно x.0=K(y.0,.., y.3) получается однозначная, но совсем невкусная.

[Сергей Борщ 134]

не, за одну никак

Да, это я погорячился.

 

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

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]

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

Я понял в чем ошибка в алгоритме Oldring

Отсюда b есть k-й бит 2y - с(с+1)

нужно маску на Y накладывать

2*(y mod 2^(k-1)) - c(c+1)

 

Если не заленюсь позже набрасаю на ЦЕ.

[singlskv 0]

А как за две?

Минимальный период по парам (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]

а ведь

X * (X+1) / 2

это формула суммы арифметической прогрессии ( ряд от 0 до n с шагом 1 )

S = (a1 + an)*n/2 = ( 0 + X ) * (X+1)/2

т.е это младшие биты суммы всех чисел от 0 до X

может это поможет?

[singlskv 0]

а ведь

X * (X+1) / 2

это формула суммы арифметической прогрессии ( ряд от 0 до n с шагом 1 )

S = (a1 + an)*n/2 = ( 0 + X ) * (X+1)/2

т.е это младшие биты суммы всех чисел от 0 до X

может это поможет?

это уже было в посте №7 причем от автора топика,

вопрос только в самом быстром решении...

[Oldring 0]

угу. За одну. 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]

Протестировал до N = 2^16

Нет там ошибок.

Я говорил только о маске по 2^k-1, хм..., а возможно она правда и не нужна...

Младший бит X можно перебирать, вычисляя все биты дважды, а можно начать с нулевого младшего бита и в конце вычислить X = 2^N - 1 - X, что вообще-то равно побитовой инверсии X, если старший бит Y оказался неправильным.

Дважды это медленно, в посте N20 я и предложил посчитать от любого начального а потом инверсию...

Думаю, что легко организовать побитовую итерацию без умножений. Цикл сводится к проверке

младшего бита, двум N-битовым сдвигам (по одному биту вправо и влево), N-битовому вычитанию и N-битовому ИЛИ.

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

умножения или маленькая разрядность данных.

[Oldring 0]

Я говорил только о маске по 2^k-1, хм..., а возможно она правда и не нужна...

 

Она не только не нужна, но может быть и вредна, так как будет левый заем из рассматриваемого бита.

 

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

умножения или маленькая разрядность данных.

 

Или для HDL, или для процов, где умножение занимает несколько тактов ;)

Если заниматься микрооптимизацией - любой вариант может оказаться лучше.

На VLIW процессорах думаю цикл можно за два такта на бит делать. Как за один - любопытная головоломка ;)

 

Кстати, еще вариант - сразу бит по 8-16 таблично вычислять, наверное возможно...

Если обращение к памяти достаточно быстрое.