Технический форум по робототехнике.
blindman » 18 мар 2010, 07:25
Есть процессор, работающий с 16-разрядными двоичными числами без знака. Операция R(x) меняет порядок следования битов в числе x на обратный: R(1000000000000000
2) = 0000000000000001
2, R(1010000000000000
2) = 0000000000000101
2, R(0101000000000001
2) = 1000000000001010
2, и т.д. Очевидно, что R(R(x)) = x.
Дано некое число a. Необходим эффективный алоритм, позволяющий для произвольного x сравнить а с R(x). Сравнение будет выполняться в цикле. Перед входом в цикл можно произвести какие-то преобразования над a, но в теле цикла должен быть минимальный объем вычислений. Процессор позволяет вычислить R(x) за 1 команду. Алгоритм
- Код: Выделить всё • Развернуть
цикл
получить x
найти R(x)
сравнить R(x) с a
использовать-результат-сравнения
конеццикла
считается недостаточно эффективным. Идеальный алгоритм:
- Код: Выделить всё • Развернуть
как-то-преобразовать а в b
цикл
получить x
выполнить какую-то-быструю-операцию(x,b) <--- CMP, AND, OR, XOR, фиг его знает
использовать-результат-предыдущей-операции
конеццикла
Собственно задача - придумать как "как-то-преобразовать а в b" и какую использовать "какую-то-быструю-операцию" ?
blindman » 18 мар 2010, 08:13
Задачу я решил, если кому интересно - подумайте, предлагайте варианты. Потом я свой напишу
blindman » 18 мар 2010, 08:15
Опа... поторопился... похоже мое решение неверное
=DeaD= » 18 мар 2010, 08:18
Сравнить то в каком смысле?
хоть не "!=" ? я так понимаю нужна операция "<"?
Michael_K » 18 мар 2010, 08:19
задача какая-то... некорректная, имхо.
во-первых, непонятно, что значит "сравнить",
во-вторых, "придумать какую-то быструю операцию" - это что?
Ну вот классная операция:
"сравнить, поделить, и подпрыгнуть" - исполняется за одну шестую такта.
blindman » 18 мар 2010, 08:20
меньше/больше или равно
blindman » 18 мар 2010, 08:22
Michael_K писал(а):"придумать какую-то быструю операцию" - это что?
операция, которая выполнится за 1 команду процессора. Конкретнее - Parallax Propeller.
blindman » 18 мар 2010, 08:24
Казнить нельзя помиловать
Сравнить - значит определить "меньше" или "больше или равно"
Michael_K » 18 мар 2010, 08:30
Если задача практическая, то может быть проще анроллить первый цикл по два действия скажем,
не сэкономите на "выдуманной операции", зато сэкономите на цикле...
blindman » 18 мар 2010, 08:34
Количество итераций неопределено, важно минимальное время выполнения итерации цикла (интервал между сравнениями)
Michael_K » 18 мар 2010, 08:41
не... два такта в один упихать... наверное не получится
=DeaD= » 18 мар 2010, 08:59
Решения нет, очевидно результат искомой операции зависит сначала от младшего бита (x), потом от второго и т.п.
Очевидно такой атомарной операции случайно подходящей быть не может. Хотя конечно система команд Propeller'а мне незнакома
blindman » 18 мар 2010, 09:41
Поотрывать бы руки тем кто располагает ноги в чипах произвольным образом
Ну неужели трудно додуматься - в процессоре нумеровать по часовой стрелке, в АЦП - против
Michael_K » 18 мар 2010, 10:11
blindman писал(а):Поотрывать бы руки тем кто располагает ноги в чипах произвольным образом
Ну неужели трудно додуматься - в процессоре нумеровать по часовой стрелке, в АЦП - против
А вы их на разные стороны платы ставьте...
Вообще, посыл странный
=DeaD= » 18 мар 2010, 10:22
Разные стороны платы - это двухсторонний монтаж в дальнейшем, а это лишние деньги и гемор.
