реклама на сайте
подробности

 
 
2 страниц V   1 2 >  
Reply to this topicStart new topic
> Найти обратное преобразование, y = (x * (x+1) / 2) mod N
Сергей Борщ
сообщение Mar 31 2009, 13:47
Сообщение #1


Гуру
******

Группа: Модераторы
Сообщений: 8 455
Регистрация: 15-05-06
Из: Рига, Латвия
Пользователь №: 17 095



Столкнулся с интересным алгоритмом. y = (x * (x+1) / 2 ) mod N (N - степень двойки) дает взаимно однозначное преобразование x[0...N-1] в y[0...N-1]. Собственно задача: имея y найти х. Табличный метод не предлагать - у меня x имеет 24 бита.
На всякий случай привожу таблицу для N = 2^8:
Код
y(x):
00 01 03 06 0A 0F 15 1C 24 2D 37 42 4E 5B 69 78
88 99 AB BE D2 E7 FD 14 2C 45 5F 7A 96 B3 D1 F0
10 31 53 76 9A BF E5 0C 34 5D 87 B2 DE 0B 39 68
98 C9 FB 2E 62 97 CD 04 3C 75 AF EA 26 63 A1 E0
20 61 A3 E6 2A 6F B5 FC 44 8D D7 22 6E BB 09 58
A8 F9 4B 9E F2 47 9D F4 4C A5 FF 5A B6 13 71 D0
30 91 F3 56 BA 1F 85 EC 54 BD 27 92 FE 6B D9 48
B8 29 9B 0E 82 F7 6D E4 5C D5 4F CA 46 C3 41 C0
40 C1 43 C6 4A CF 55 DC 64 ED 77 02 8E 1B A9 38
C8 59 EB 7E 12 A7 3D D4 6C 05 9F 3A D6 73 11 B0
50 F1 93 36 DA 7F 25 CC 74 1D C7 72 1E CB 79 28
D8 89 3B EE A2 57 0D C4 7C 35 EF AA 66 23 E1 A0
60 21 E3 A6 6A 2F F5 BC 84 4D 17 E2 AE 7B 49 18
E8 B9 8B 5E 32 07 DD B4 8C 65 3F 1A F6 D3 B1 90
70 51 33 16 FA DF C5 AC 94 7D 67 52 3E 2B 19 08
F8 E9 DB CE C2 B7 AD A4 9C 95 8F 8A 86 83 81 80

x(y):
00 01 8B 02 37 99 03 D5 EF 4E 04 2D 27 B6 73 05
20 9E 94 5D 17 06 E3 CA CF EE DB 8D 07 A9 AC 65
40 C1 4B BD 08 A6 3C 6A AF 71 44 ED 18 09 33 C5
60 21 D4 E2 28 B9 A3 0A 8F 2E 9B B2 38 96 EC DA
80 7E 0B 82 48 19 7C 55 6F CE 84 52 58 C9 0C 7A
A0 E1 EB 22 68 86 63 B5 4F 91 5B 0D 78 29 D3 1A
C0 41 34 3D 88 D9 BC EA 2F 0E C4 6D 98 76 4C 45
E0 5E AB 9D A8 39 23 8A 0F AE 1B CD B8 E9 93 A5
FF FE 74 FD C8 66 FC 2A 10 B1 FB D2 D8 49 8C FA
DF 61 6B A2 E8 F9 1C 35 30 11 24 72 F8 56 53 9A
BF 3E B4 42 F7 59 C3 95 50 8E BB 12 E7 F6 CC 3A
9F DE 2B 1D D7 46 5C F5 70 D1 64 4D C7 69 13 25
7F 81 F4 7D B7 E6 83 AA 90 31 7B AD A7 36 F3 85
5F 1E 14 DD 97 79 9C 4A B0 6E A4 F2 87 D6 2C E5
3F BE CB C2 77 26 43 15 D0 F1 3B 92 67 89 B3 BA
1F A1 54 62 57 C6 DC 75 F0 51 E4 32 47 16 6C 5A
Возможно, это какое-то общеизвестное преобразование, но моих знаний не хватает.

P.S. добавил таблицу x(y)

Сообщение отредактировал Сергей Борщ - Mar 31 2009, 19:03


--------------------
На любой вопрос даю любой ответ
"Write code that is guaranteed to work, not code that doesn’t seem to break" (C++ FAQ)
Go to the top of the page
 
+Quote Post
Oldring
сообщение Mar 31 2009, 14:18
Сообщение #2


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



2y = x(x+1) mod 2N

пусть на к-м шаге известны k-1 младших бит x

Тогда

x = a * 2^(k+1) + b * 2^k + c, где a = неизвестное целое, b - неизвестный бит, c - известное целое меньшее 2^k

x(x+1) = d*2^(k+1) + b*2^k + c(c+1)

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

Пожалуй примерно так.

PS Кроме случая k == 0 где всего два варианта младшнго значения бита


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
Сергей Борщ
сообщение Apr 1 2009, 20:11
Сообщение #3


Гуру
******

Группа: Модераторы
Сообщений: 8 455
Регистрация: 15-05-06
Из: Рига, Латвия
Пользователь №: 17 095



Цитата(Oldring @ Mar 31 2009, 17:18) *
x = a * 2^(k+1) + b * 2^k + c, где a = неизвестное целое, b - неизвестный бит, c - известное целое меньшее 2^k

x(x+1) = d*2^(k+1) + b*2^k + c(c+1)
Чего-то я никак не могу понять связи между этими уравнениями. Я правильно понимаю, что с - это k-1 младших бит x? Не могли бы вы изложить это более подробно, для особо одаренных? Если можно, то на примере любого числа для N=2^4:
Код
0000 0001 0011 0110
1010 1111 0101 1100
0100 1101 0111 0010
1110 1011 1001 1000


--------------------
На любой вопрос даю любой ответ
"Write code that is guaranteed to work, not code that doesn’t seem to break" (C++ FAQ)
Go to the top of the page
 
+Quote Post
Nemo2000
сообщение Apr 2 2009, 07:06
Сообщение #4


Частый гость
**

Группа: Свой
Сообщений: 79
Регистрация: 8-04-05
Из: Санк-Петербург
Пользователь №: 3 972



вроде получается так:

2*y = x*(x+1) mod 2*N = x*(x+1)mod 2^(k+1), N = 2^k

В общем случае это означает, что:

2*y = x*(x+1) - ЦелаяЧасть[ (x*(x+1))/(2^(k+1)) ] * 2^(k+1);

Обозначим ЦелаяЧасть[ (x*(x+1))/(2^(k+1)) ] = n , n = 0, 1, 2 ...

2*y = x*(x+1) - n*2^(k+1);

x^2 + x - 2*(n*2^k + y);

x = [-1 + sqrt(1 + 8*(n*2^k + y)) ] / 2 (второй корень, где -1 - sqrt() отбрасываем, т.к. интересуют x > 0)

т.о. нахождение х следующее:
1. Ищем такое минимальное n, при котором корень будет целым числом.
2. Считаем х.

Пример N = 2^4 = 16, n_max = 7

x = 0, 1, 2, 3, 4 , 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
y = 0, 1, 3, 6, 10, 15, 5, 12, 4, 13, 7, 2, 14, 11, 9, 8

Итак, y = 10,
1) n = 0, x = [-1 + sqrt(1 + 8*(0*16 + 10)) ] / 2 = [-1 + 9] / 2 = 4

y = 13
1) n = 0, x = [-1 + sqrt(1 + 8*(0*16 + 13)) ] / 2 = [-1 + sqrt(105) ] / 2; sqrt(105) - не целое
2) n =1, x = [-1 + sqrt(1 + 8*(1*16 + 13)) ] / 2 = [-1 + sqrt(233) ] / 2; sqrt(233) - не целое
3) n =2, x = [-1 + sqrt(1 + 8*(2*16 + 13)) ] / 2 = [-1 + sqrt(361) ] / 2 = [-1 + 19]/2 = 9;

y = 8
1) n = 0, x = [-1 + sqrt(1 + 8*(0*16 + 8)) ] / 2 = [-1 + sqrt(65) ] / 2; sqrt(65) - не целое
2) n =1, x = [-1 + sqrt(1 + 8*(1*16 + 8)) ] / 2 = [-1 + sqrt(193) ] / 2; sqrt(193) - не целое
3) n =2, x = [-1 + sqrt(1 + 8*(2*16 + 8)) ] / 2 = [-1 + sqrt(321) ] / 2; sqrt(321) - не целое
4) n =3, x = [-1 + sqrt(1 + 8*(3*16 + 8)) ] / 2 = [-1 + sqrt(449) ] / 2; sqrt(449) - не целое
5) n =4, x = [-1 + sqrt(1 + 8*(4*16 + 8)) ] / 2 = [-1 + sqrt(577) ] / 2; sqrt(577) - не целое
6) n =5, x = [-1 + sqrt(1 + 8*(5*16 + 8)) ] / 2 = [-1 + sqrt(705) ] / 2; sqrt(705) - не целое
7) n =6, x = [-1 + sqrt(1 + 8*(6*16 + 8)) ] / 2 = [-1 + sqrt(833) ] / 2; sqrt(833) - не целое
8) n =7, x = [-1 + sqrt(1 + 8*(7*16 + 8)) ] / 2 = [-1 + sqrt(961) ] / 2 = [-1 + 31]/2 = 15
Go to the top of the page
 
+Quote Post
MrYuran
сообщение Apr 2 2009, 07:17
Сообщение #5


Беспросветный оптимист
******

Группа: Свой
Сообщений: 4 640
Регистрация: 26-12-07
Из: Н.Новгород
Пользователь №: 33 646



Щас сумничаю..
Чето мне подсказывает про поля Галуа
Ссылу дал от балды, лучше в учебниках поискать


--------------------
Программирование делится на системное и бессистемное. ©Моё :)
— а для кого-то БГ — это Bill Gilbert =)
Go to the top of the page
 
+Quote Post
petrov
сообщение Apr 2 2009, 07:48
Сообщение #6


Гуру
******

Группа: Свой
Сообщений: 2 220
Регистрация: 21-10-04
Из: Balakhna
Пользователь №: 937



Цитата(MrYuran @ Apr 2 2009, 10:17) *
Щас сумничаю..


Аналогично :)

Читать про квадратичные вычеты, китайскую теорему об остатках и т. п.
Go to the top of the page
 
+Quote Post
Сергей Борщ
сообщение Apr 2 2009, 09:56
Сообщение #7


Гуру
******

Группа: Модераторы
Сообщений: 8 455
Регистрация: 15-05-06
Из: Рига, Латвия
Пользователь №: 17 095



Цитата(MrYuran @ Apr 2 2009, 10:17) *
Чето мне подсказывает про поля Галуа
Угу. Насколько я ничего не понимаю, это поле Галуа с определяющим полиномом X^2+X+1. X - к-кортеж (N=2^k). Фактически это задача нахождения индекса элемента в поле. 

Цитата(Nemo2000 @ Apr 2 2009, 10:06) *
1. Ищем такое минимальное n, при котором корень будет целым числом.
Алгоритм в целом правильный. Но для x=2^24-1 придется искать корень 2^24-1 число раз. Перебором будет проще и быстрее.

ReAl на сахаре попытался решить уравнение x = [-1 + sqrt(1 + 8*(n*2^k + y)) ] / 2 аналитически. Очевидно, что подкоренное выражение должно быть квадратом. Поскольку присутствует деление на 2 и -1, то квадратом нечетного числа, или числом вида (2m + 1)^2. Подстановка под корень этого выражения дает тождество x=m. Попытка решения уравнения 1+8(n*2^k + y) = (2m+1)^2 приводит к исходному уравнению:

1+8(n*2^k + y) = 4m^2+4m+1
8(n*2^k + y) = 4m^2+4m
2(n*2^k + y) = m^2+m
2(n*2^k + y) = m(m+1)
n*2^k + y = m(m+1)/2
Круг замкнулся.

Вчера мне пришел в голову более простой алгоритм: элементы этого поля представляют собой суммы членов арифметической прогрессии. Т.е. x[n] = (x[n-1]+x) mod 2^k. То есть вычитая из y по модулю 2^k числа x = 1,2,3... до получения 0 мы находим х за максимум 2^k - 1 вычитаний. Ну или восстанавливая последовательность x суммированием последовательности 1,2,3... по модулю 2^k до совпадения результата с y, что то же яйцо, только в профиль.

Но должен же быть какой-то алгоритм побитового восстановления, вроде деления полиномов!


--------------------
На любой вопрос даю любой ответ
"Write code that is guaranteed to work, not code that doesn’t seem to break" (C++ FAQ)
Go to the top of the page
 
+Quote Post
mikeT
сообщение Apr 2 2009, 11:26
Сообщение #8


Участник
*

Группа: Участник
Сообщений: 73
Регистрация: 6-02-08
Из: Новосибирск
Пользователь №: 34 789



Я бросил вашу задачку на форум мехмата НГУ (Новосибирск), а именно в раздел " Алгебра, логика, теория чисел и теория алгоритмов"

http://www.nsu.ru/phpBB/viewtopic.php?t=19...a7a4057847d2d69
там одно решение предложили, но я не проверял - гляньте

+ еще дал задачку ряду друзей с мех-матовским образованием, но у них специализация не та несколько. в общем пока решения быстрого нет smile.gif

для себя я прикинул две "проекции" - как мне видится сама эта задача (чисто для понимания)
1) компьютерно-низкоуровневый: при выполнении операций x*(x+1)/2 на 24-битном модуле происходит wrap-around и результат записывается "как есть" - это тот самый y.
2) графический - строим график функции x(x+1)/2, где x - целые в заданном диапазоне. до 2^24 все "как обычно", а дальше мы из ответа начинаем вычитать 2^24 стоолько раз сколько надо чтобы остаток не превышал 2^24. Получится "страшная" пила какая-то. При первом взгляде в Матлабе я подумал, что какая нах тут однозначность, но оказалось что так и есть.

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

по идее там решается квадратное уравнение, но нужно подобрать параметр под корнем (в дискриминанте), так 1) чтобы корень извлекался 2) чтобы это число было нечетное (т.к. общее решение должно быть целое, а там стоит 1/2)
Go to the top of the page
 
+Quote Post
Сергей Борщ
сообщение Apr 2 2009, 12:18
Сообщение #9


Гуру
******

Группа: Модераторы
Сообщений: 8 455
Регистрация: 15-05-06
Из: Рига, Латвия
Пользователь №: 17 095



Цитата(mikeT @ Apr 2 2009, 14:26) *
Я бросил вашу задачку на форум мехмата НГУ (Новосибирск), а именно в раздел " Алгебра, логика, теория чисел и теория алгоритмов"

http://www.nsu.ru/phpBB/viewtopic.php?t=19...a7a4057847d2d69
там одно решение предложили, но я не проверял - гляньте
Приведенный там алгоритм работает! Спасибо! в нем получается в худшем случае всего k - 1 умножений (N=2^k).


--------------------
На любой вопрос даю любой ответ
"Write code that is guaranteed to work, not code that doesn’t seem to break" (C++ FAQ)
Go to the top of the page
 
+Quote Post
singlskv
сообщение Apr 2 2009, 12:40
Сообщение #10


дятел
*****

Группа: Свой
Сообщений: 1 681
Регистрация: 13-05-06
Из: Питер
Пользователь №: 17 065



Цитата(Сергей Борщ @ Apr 2 2009, 16:18) *
Приведенный там алгоритм работает! Спасибо! в нем получается всего k умножений (N=2^k).

На самом деле Вам Oldring в первом же ответе дал правильный алгоритм

Цитата
x = a * 2^(k+1) + b * 2^k + c, где a = неизвестное целое, b - неизвестный бит, c - известное целое меньшее 2^k

x(x+1) = d*2^(k+1) + b*2^k + c(c+1)

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

Цитата
Чего-то я никак не могу понять связи между этими уравнениями. Я правильно понимаю, что с - это k-1 младших бит x?
с это k-1 уже найденых бит

x(x+1) = (a * 2^(k+1) + b * 2^k + c)(a * 2^(k+1) + b * 2^k + c +1)=.....=
= d*2^(k+1) + b*2^k + c(c+1)
где d это сумма коэф. для степеней 2^(k+1) и она нас не интересует тк мы ищем k бит
Go to the top of the page
 
+Quote Post
Rst7
сообщение Apr 2 2009, 12:45
Сообщение #11


Йа моск ;)
******

Группа: Модераторы
Сообщений: 4 345
Регистрация: 7-07-05
Из: Kharkiv-city
Пользователь №: 6 610



Цитата
Столкнулся с интересным алгоритмом.


Позвольте спросить, а где такой алгоритм живет? Ноги откуда растут?


--------------------
"Практика выше (теоретического) познания, ибо она имеет не только достоинство всеобщности, но и непосредственной действительности." - В.И. Ленин
Go to the top of the page
 
+Quote Post
Сергей Борщ
сообщение Apr 2 2009, 13:04
Сообщение #12


Гуру
******

Группа: Модераторы
Сообщений: 8 455
Регистрация: 15-05-06
Из: Рига, Латвия
Пользователь №: 17 095



Цитата(Rst7 @ Apr 2 2009, 15:45) *
Позвольте спросить, а где такой алгоритм живет? Ноги откуда растут?
В канале связи. Видимо шифрование.


--------------------
На любой вопрос даю любой ответ
"Write code that is guaranteed to work, not code that doesn’t seem to break" (C++ FAQ)
Go to the top of the page
 
+Quote Post
mikeT
сообщение Apr 2 2009, 13:34
Сообщение #13


Участник
*

Группа: Участник
Сообщений: 73
Регистрация: 6-02-08
Из: Новосибирск
Пользователь №: 34 789



Цитата(Сергей Борщ @ Apr 2 2009, 20:04) *
В канале связи. Видимо шифрование.



Я так и подумал rolleyes.gif Хотя я полный чайник в этих вопросах, но алгоритм показался как раз "по теме" rolleyes.gif
Я попросил еще человека с того форума НГУ ответить - на чем базируется решение. Просто "голова умная" у человека (по видимому, всяко не без этого rolleyes.gif ) или еще какие-то "методы" есть из соответствующего раздела

P.S. Самому разбираться - интересно, но времени нет. Книжки по теории чисел и по абстрактной алгебре есть и много, но все пока никак времени нет

Сообщение отредактировал mikeT - Apr 2 2009, 13:36
Go to the top of the page
 
+Quote Post
singlskv
сообщение Apr 2 2009, 20:08
Сообщение #14


дятел
*****

Группа: Свой
Сообщений: 1 681
Регистрация: 13-05-06
Из: Питер
Пользователь №: 17 065



Цитата(singlskv @ Apr 2 2009, 16:40) *
На самом деле Вам Oldring в первом же ответе дал правильный алгоритм

Не, наврал...
неправильный алгоритм у Oldring...
но очень похож на правду, там где-то апшыбка

кстати младший бит x определяется однозначно из значения 'y' за пару операций.
Go to the top of the page
 
+Quote Post
Сергей Борщ
сообщение Apr 3 2009, 05:31
Сообщение #15


Гуру
******

Группа: Модераторы
Сообщений: 8 455
Регистрация: 15-05-06
Из: Рига, Латвия
Пользователь №: 17 095



Цитата(singlskv @ Apr 2 2009, 23:08) *
кстати младший бит x определяется однозначно из значения 'y' за пару операций.
угу. За одну. x0 = y & 1;


--------------------
На любой вопрос даю любой ответ
"Write code that is guaranteed to work, not code that doesn’t seem to break" (C++ FAQ)
Go to the top of the page
 
+Quote Post
singlskv
сообщение Apr 3 2009, 09:12
Сообщение #16


дятел
*****

Группа: Свой
Сообщений: 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
Go to the top of the page
 
+Quote Post
xemul
сообщение Apr 3 2009, 11:12
Сообщение #17



*****

Группа: Свой
Сообщений: 1 928
Регистрация: 11-07-06
Пользователь №: 18 731



Цитата(singlskv @ Apr 3 2009, 13:12) *
не, за одну никак

А как за две?
Минимальный период по парам (y._;x.0) получается 16, т.е. воспроизвести x.0 можно по комбинации 4 битов. Карта Карно x.0=K(y.0,.., y.3) получается однозначная, но совсем невкусная.
Go to the top of the page
 
+Quote Post
Сергей Борщ
сообщение Apr 3 2009, 11:31
Сообщение #18


Гуру
******

Группа: Модераторы
Сообщений: 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)
Go to the top of the page
 
+Quote Post
singlskv
сообщение Apr 3 2009, 12:31
Сообщение #19


дятел
*****

Группа: Свой
Сообщений: 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)

Если не заленюсь позже набрасаю на ЦЕ.
Go to the top of the page
 
+Quote Post
singlskv
сообщение Apr 3 2009, 14:20
Сообщение #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;

ЗЫ. А похоже можно вобще без умножений обойтись...
Go to the top of the page
 
+Quote Post
KRS
сообщение Apr 3 2009, 16:40
Сообщение #21


Профессионал
*****

Группа: Модераторы
Сообщений: 1 951
Регистрация: 27-08-04
Из: Санкт-Петербург
Пользователь №: 555



а ведь
X * (X+1) / 2
это формула суммы арифметической прогрессии ( ряд от 0 до n с шагом 1 )
S = (a1 + an)*n/2 = ( 0 + X ) * (X+1)/2
т.е это младшие биты суммы всех чисел от 0 до X
может это поможет?
Go to the top of the page
 
+Quote Post
singlskv
сообщение Apr 3 2009, 18:05
Сообщение #22


дятел
*****

Группа: Свой
Сообщений: 1 681
Регистрация: 13-05-06
Из: Питер
Пользователь №: 17 065



Цитата(KRS @ Apr 3 2009, 20:40) *
а ведь
X * (X+1) / 2
это формула суммы арифметической прогрессии ( ряд от 0 до n с шагом 1 )
S = (a1 + an)*n/2 = ( 0 + X ) * (X+1)/2
т.е это младшие биты суммы всех чисел от 0 до X
может это поможет?

это уже было в посте №7 причем от автора топика,
вопрос только в самом быстром решении...
Go to the top of the page
 
+Quote Post
Oldring
сообщение Apr 9 2009, 08:00
Сообщение #23


Гуру
******

Группа: Свой
Сообщений: 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-битовому ИЛИ.


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post
singlskv
сообщение Apr 9 2009, 18:52
Сообщение #24


дятел
*****

Группа: Свой
Сообщений: 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-битовому ИЛИ.
что-то подобное и я хотел соорудить, но оказалось что это имеет смысл тока для процов где нет быстрого
умножения или маленькая разрядность данных.
Go to the top of the page
 
+Quote Post
Oldring
сообщение Apr 10 2009, 08:16
Сообщение #25


Гуру
******

Группа: Свой
Сообщений: 3 041
Регистрация: 10-01-05
Из: Москва
Пользователь №: 1 874



Цитата(singlskv @ Apr 9 2009, 22:52) *
Я говорил только о маске по 2^k-1, хм..., а возможно она правда и не нужна...


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

Цитата(singlskv @ Apr 9 2009, 22:52) *
что-то подобное и я хотел соорудить, но оказалось что это имеет смысл тока для процов где нет быстрого
умножения или маленькая разрядность данных.


Или для HDL, или для процов, где умножение занимает несколько тактов wink.gif
Если заниматься микрооптимизацией - любой вариант может оказаться лучше.
На VLIW процессорах думаю цикл можно за два такта на бит делать. Как за один - любопытная головоломка wink.gif

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


--------------------
Пишите в личку.
Go to the top of the page
 
+Quote Post

2 страниц V   1 2 >
Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 22nd July 2025 - 14:28
Рейтинг@Mail.ru


Страница сгенерированна за 0.0162 секунд с 7
ELECTRONIX ©2004-2016