Помогите с алгоритмом!, проверка элементов массива на кратность 2^k Опции

[Gabe]

Помогите с алгоритмом, пожалуйста!
Нужно организовать проверку элементов массива на кратность 2^k, где k=1...4 unsure.gif

Делаю на ассемблере

Сообщение отредактировал Gabe - May 27 2009, 13:31

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

Нужно организовать проверку элементов массива на кратность 2^k, где k=1...4

проверить на равенство нулю k младших битов. маски 0b00001111, 0b00000111, 0b00000011, 0b00000001 можно хранить во флеше и извлекать командой LPM.

[Gabe]

Огромное спасибо!!!
Осталось только в документации мультикора разобраться с маской...

[Gabe]

DO 8, endfor
MOVE (A0)+, R2 /* загружаем элемент массива a */
MOVE 0, R0
MOVE 0, R6
MOVE 3, R4 /* пусть к=3 */
DO R4, endfor1
BTSTL R0,R2 /* проверяем биты элемента */
INCL.eq R6,R6 /* если бит=0, то R6++ */
endfor1:
INC R0,R0 /* берём номер следующего бита*/
CMPL 2,R6 /* все ли три бита равны 0?*/
endfor:
MOVE.eq R2,(A1)+ /* если все, то переписываем элемент в b*/
STOP

Почему-то не работает вот этот инкремент: INCL.eq R6,R6 /* если бит=0, то R6++ */

[Rst7]

Молодой человек, зачем Вы вообще в ассемблер сунулись? Какую-такую супероптимальную программу Вы сможете написать? Надо бы для начала вопрос сформулировать, а перед формулировкой самому крепко подумать. И вот почему:

Условию, что число v кратно 2 и 4 и 8 и 16 равноценно условие, что v кратно 16 и проверяется так

Код

if ((v&0x0F)==0)
{
  //Число кратно 2 и 4 и 8 и 16
}

Если же в условии не "и", а "или", то это равноценно проверке на четность. Т.е.

Код

if ((v&0x01)==0)
{
  //Число кратно 2 или 4 или 8 или 16
}

На ассемблер нужного вам камня сами переведете?

[Gabe]

мне необходимо её написать на ассемблере, так как задача учебная...
скажем k=3, тогда надо проверять на кратность 8, что я в коде и делаю, побитово проверяя загруженное число
проблема в том, что признак бита почему-то не используется следующей командой

Сообщение отредактировал Gabe - May 27 2009, 16:34

[Rst7]

мне необходимо её написать на ассемблере, так как задача учебная...

Это вторично.

скажем k=3, тогда надо проверять на кратность 8, что я в коде и делаю

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

По коду.

2^k=1<<k. Это понятно? Если не понятно, то 1<<k обозначает 1 сдвинутая влево на k бит.

Как из 1<<k изготовить маску? Правильно, (1<<k)-1.

Как проверить? Да просто сделать v&((1<<k)-1) и сравнить с 0. Точнее, после AND флаг Z будет установлен или сброшен.

Ищите в мануале на процессор, как сделать сдвиг влево по значению регистра, как вычесть 1, и как сделать AND.

[Gabe]

не ругайтесь, пожалуйста, я только начинающий, поэтому и ничего не написал.
вы правильно догадались насчёт условия задачи. а камень - это 1892ВМ3T (MC-12 от ЭЛВИС).
Rst7, большое Вам спасибо за помощь, буду делать

всё работает
всем огромное спасибо за помощь!

кстати, возникает тогда такой вопрос: в случае кратности числу 2^k маска формируется таким образом (1<<k)-1. А если стоит задача просто найти элементы, кратные k? Какой алгоритм поиска стоит применить именно в такой ситуации?

[Gabe]

С элементами, кратными 2,4,8 понятно. Как найти числа, кратные 3 и 7?
не могу найти соответствующие признаки...

[Rst7]

Проще всего будет банально разделить и проверить остаток. В камне наверняка есть комманда деления.

[Gabe]

Банально разделить можно только в RISC-ядре, там есть соответствующая команда DIV, а в DSP-ядре (в котором надо сделать) такой команды и даже похожей на неё нет.
В инете есть ссылка на статью некоего Сулейманова Р.Р. http://www.zabspu.ru/artix/aview.php?aid=257 , но вот скачать её нигде не удаётся...

Подсказали идею просто вычитать из числа 3 (или 7), пока оно не станет равно 0 (кратно) или меньше нуля (не кратно). Мясо, конечно, при больших числах...

Сообщение отредактировал Gabe - May 28 2009, 05:04

[Палыч]

Подсказали идею просто вычитать из числа 3 (или 7), пока оно не станет равно 0 (кратно) или меньше нуля (не кратно). Мясо, конечно, при больших числах...

Возможно, Вам подойдут идеи из книги Генри Уоррен "Арифметические трюки для программистов". В книге есть глава "Целочисленное деление", в которой приведены алгоритмы определения частного и остатка при делении на 3 и 7. Книга "гуляет" в интернете (сам когда-то её скачал).

[Rst7]

Напишите деление в столбик самостоятельно. Тем более, что частное не интересует, только остаток.

в которой приведены алгоритмы определения частного и остатка при делении на 3 и 7

Путем умножения на 1/х. Это не годится в случае произвольного x, а что-то мне подсказывает, что следующей стадией будет именно это

[Палыч]

Подсказали идею просто вычитать из числа 3 (или 7), пока оно не станет равно 0 (кратно) или меньше нуля (не кратно). Мясо, конечно, при больших числах...

При больших числах можно вычитать вначале большие числа кратные 3 (или 7). Например: 30, или 3333, или 9999, или 21615...

[Gabe]

Rst7, новых итераций не будет
Палыч, спасибо, будем изучать...

Вот попробовал реализовать идею с вычитанием... Алгоритм на бумаге вполне работает, а в MC2 Studio Jump'ы не дают нормально работать циклам.
 DSP.rar ( 347.92 килобайт ) Кол-во скачиваний: 80

[SKov]

С элементами, кратными 2,4,8 понятно. Как найти числа, кратные 3 и 7?
не могу найти соответствующие признаки...

А чего там находить? Просто немного подумать...
Ну вот, например, в детстве когда-то писал функцию для получения остатка от деления на 3.

int Rest_3(int k)
{k=(k&63)+(k>>6);
k=(k&15)+(k>>4);
k=(k&3)+(k>>2);
k=(k&3)+(k>>2);
k=(k&3)+(k>>2);
if(k==3)return(0); else return(k);
}

Это работало вроде бы для 13-битового слова.
А если для произвольной разрядности числа, то, видимо, можно так записать тело функции,
хоть это будет и не оптимально по числу операций:

while (k>3) k=(k&3)+(k>>2);
if(k==3)return(0); else return(k);

Для остатка от деления на 7 тоже легко.
Если, конечно, подумать.
Сами догадаетесь?

[Gabe]

кажется, для 7 будет:
while (k>7) k=(k&7)+(k>>3);
if(k==7)return(0); else return(k);

Сообщение отредактировал Gabe - May 28 2009, 16:38

[SKov]

кажется, для 7 будет:
while (k>7) k=(k&7)+(k>>3);
if(k==7)return(0); else return(k);

Да, похоже. Надо бы поискать числа вида 2**n-1 , делящиеся на 7.
Тогда для многобитовых чисел первые шаги можно сделать более эффективно.
Как это было сделано в моем первом примере в первых строчках.

[Палыч]

А чего там находить? Просто немного подумать...

Забавно получается. Можно обобщить...
Проверка делимости (получение остатка от деления) числа К на M= 2^N - 1

Код

while (K > M) K= (K & M) + (K >> N);
if(K == M) return 0;
else return K;

P.S. Можно и дальше обобщить, но, наверное будет не так забавно
Проверка делимости (получение остатка от деления) числа К на M= 2^N - L

Код

while (K > M) K= (K & M) + L * (K >> N);
if(K == M) return 0;
else return K;

P.P.S. Ай-ай! Соврал!

Код

while (K > M) K= (K & ((1 << N) - 1)) + L * (K >> N);
if(K == M) return 0;
else return K;

[SKov]

P.S. Можно и дальше обобщить, но, наверное будет не так забавно

Код

while (K > M) K= (K & ((1 << N) - 1)) + L * (K >> N);
if(K == M) return 0;
else return K;

Да, обычно так никто не делает. Умножение убивает идею.
Попробуйте сделать вычислитель остатка для числа 5. Без умножения или его имитации.
А я пока поищу в архиве )

Сообщение отредактировал SKov - May 29 2009, 08:30

[Rst7]

Вспомнил - http://graphics.stanford.edu/~seander/bith...ModulusDivision

Вообще, рекомендую ознакомиться со всем документом - неплохая подборка чудных идей. Некоторые - за гранью моего понимания

[SKov]

Вспомнил - http://graphics.stanford.edu/~seander/bith...ModulusDivision

Вообще, рекомендую ознакомиться со всем документом - неплохая подборка чудных идей. Некоторые - за гранью моего понимания

Да, но вычислителя остатка при делении на 5 там нет.

[Rst7]

Да, но вычислителя остатка при делении на 5 там нет.

Вот черт. Действительно... Хотя - это не вопрос. Умножаем вход на 3 и делим на 15

[Палыч]

Да, обычно так никто не делает. Умножение убивает идею. Попробуйте сделать вычислитель остатка для числа 5.

Ну, в своём посте я честно указал, что уж для любого случая получается, мягко говоря - некрасиво. Но, при L = степень двойки - "очень даже и нечего"!

Без умножения или его имитации.

Почему же - "без"? Почему имитацию умножения не применить? L= 3= 2 + 1 Оба слогаемых - степени двойки, получаем

Код

while (K > 5) K= (K & 7) + (K >> 2) + (K >> 3);
if(K == 5) return 0;
else return K;

P.S. Вот - чёрт! Опять поспешил... Правильно будет так:

Код

while (K > 5) K= (K & 7) + ((K >> 2) & (~1)) + (K >> 3);
if(K == 5) return 0;
else return K;

или так

Код

while (K > 5) { Temp= (K & (~7)) >> 2;  K= (K & 7) + Temp + (Temp >> 1); }
if(K == 5) return 0;
else return K;

[SKov]

Вот черт. Действительно... Хотя - это не вопрос. Умножаем вход на 3 и делим на 15

Все прально, только умножать не надо
А делить можно и на 255..

int Rest_5(int k)
{
k=(k&255)+(k>>8);
k=(k&15)+(k>>4);
k=(k&15)+(k>>4);
if(k>=10)k=k-10;
if(k>=5)k=k-5;
return(k);
}
Это я писал для 13-битового числа.
В общем виде можно поставить while в одном-двух местах
Правда, смысл первых строчек уже не помню...
Вот! Вспомнил наконец!
Общая идея, которой я руководствовался в детстве при написании этих программ, заключается в том,
что из числа можно вычесть любое число, кратное делителю, и при этом остаток от деления не изменится.

[Палыч]

Правда, смысл первых строчек уже не помню...
Вот! Вспомнил наконец! Общая идея, которой я руководствовался в детстве при написании этих программ, заключается в том, что из числа можно вычесть любое число, кратное делителю, и при этом остаток от деления не изменится.

Смысл первых строчек немного в другом...

Для остатка от деления справедливо следующее
(А + В) % С = (А % С + В % С) % С
(А * В) % С = (А * (В % С)) % С

Число k можно представить как k= A*256 + B. Легко увидеть, что А= k >> 8; B= k & 255;
тогда искомый остаток от деления на 5 (назовём его R)
R= k % 5 = (A*256 + В) % 5 = ((A*256) % 5 + В % 5) % 5
Остаток от деления 256 на 5 равен 1 (это важно, т.к. результат умножения числа на единицу - есть само число, то есть, можно избавиться от умножения), тогда
(А*256) % 5 = (А * (256 % 5)) % 5 = (А * 1) % 5 = А % 5
Итак R= (A % 5 + В % 5) % 5 = (А + В) % 5, т.е. искомый остаток равен остатку от деления на 5 уже меньшего числа.
Из этих преобразований появилась строка в функции k=(k&255)+(k>>8);

Аналогично со строкой k=(k&15)+(k>>4); Все рассуждения - похожие, но число k представляется уже как k= А*16 + В

[SKov]

Смысл первых строчек немного в другом...

Для остатка от деления справедливо следующее
(А + В) % С = (А % С + В % С) % С
(А * В) % С = (А * (В % С)) % С

Число k можно представить как k= A*256 + B. Легко увидеть, что А= k >> 8; B= k & 255;
тогда искомый остаток от деления на 5 (назовём его R)
R= k % 5 = (A*256 + В) % 5 = ((A*256) % 5 + В % 5) % 5
Остаток от деления 256 на 5 равен 1 (это важно, т.к. результат умножения числа на единицу - есть само число, то есть, можно избавиться от умножения), тогда
(А*256) % 5 = (А * (256 % 5)) % 5 = (А * 1) % 5 = А % 5
Итак R= (A % 5 + В % 5) % 5 = (А + В) % 5, т.е. искомый остаток равен остатку от деления на 5 уже меньшего числа.
Из этих преобразований появилась строка в функции k=(k&255)+(k>>8);

Аналогично со строкой k=(k&15)+(k>>4); Все рассуждения - похожие, но число k представляется уже как k= А*16 + В

Ну вы тут и накрутили на ровном месте
Все намного проще:
R= k % 5 = (A*255 + В) % 5 = B%5
В первой строчке делается первый шаг поиска остатка от деления на 255.
В результате получаем некое B, которое значительно меньше исходного числа. И т.д.
Идея в том, что можно сначала искать модуль для бОльшего делителя, а затем работать с маленьким остатком дальше.
Главное условие в том, чтобы этот бОльший делитель был кратным маленькому делителю, для которого нас интересует конечный результат.
Нам подходят числа 15 и 255 в качестве бОльших делителей потому что
а) Для них легко искать остаток от деления
б) Они делятся на 5 нацело.
Ч.т.д.

[Палыч]

Ну вы тут и накрутили на ровном месте
Все намного проще:
R= k % 5 = (A*255 + В) % 5 = B%5

Ну, тогда уж так:
R= k % 5= (А*256 + В) % 5= (А*255 + А + В) % 5= ((А*255)%5 + А + В) % 5= (А + В) % 5, поскольку (А*255) % 5= 0

[SKov]

Ну, тогда уж так:
R= k % 5= (А*256 + В) % 5= (А*255 + А + В) % 5= ((А*255)%5 + А + В) % 5= (А + В) % 5, поскольку (А*255) % 5= 0

Ну, осталось только замену переменных сделать A+B=b и получится ровно то,
что у меня записано, только заметно короче.

[Палыч]

Ну, осталось только замену переменных сделать A+B=b и получится ровно то, что у меня записано, только заметно короче.

Согласен. Только помните, что спорим мы в разделе для начинающих, и не каждый дружен с математикой настолько, чтобы представить двоичное число в виде k= A*255+b, ведь 255 - это не степень двойки

[SKov]

Согласен. Только помните, что спорим мы в разделе для начинающих, и не каждый дружен с математикой настолько, чтобы представить двоичное число в виде k= A*255+b, ведь 255 - это не степень двойки

А причем здесь двоичное число и способ его представления?
Все что мы писали в наших постах справедливо для десятичных чисел,
вполне доступных для понимания даже начинающих.
И в моих функциях используются исключительно десятичные числа.
Или я не понял замечания?

[Палыч]

А причем здесь двоичное число и способ его представления?

Просто я хотел сказать, что между вашей формулой

k= A*255+b

и оператором

k=(k&255)+(k>>8);

который эквивалентен формуле k= k%256 + k /256, связь - не очевидна

[SKov]

Просто я хотел сказать, что между вашей формулой

и оператором

который эквивалентен формуле k= k%256 + k /256, связь - не очевидна

Теперь понял.
Да, тут фактически два вопроса.
Первый - переход от модуля 5 к бОльшим модулям. И здесь действительно нет разницы, какие числа мы рассмотриваем.
Второй - быстрое вычисление модуля для чисел вида 2**n-1. И вот здесь уже надо понимать,
как это выглядит в двоичном виде, иначе непонято, как работают функции.
Согласен.

[singlskv]

Теперь понял.
Да, тут фактически два вопроса.
Первый - переход от модуля 5 к бОльшим модулям. И здесь действительно нет разницы, какие числа мы рассмотриваем.
Второй - быстрое вычисление модуля для чисел вида 2**n-1. И вот здесь уже надо понимать,
как это выглядит в двоичном виде, иначе непонято, как работают функции.
Согласен.

Ну Вы и обсуждать...
Нужно всего лишь было отметить что 2^(4*k) всегда заканчивается на 6, а 6==(5 + 1) ...