Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Деление с остатком
Форум разработчиков электроники ELECTRONIX.ru > Микроконтроллеры (MCs) > MSP430
d7d1cd
Привет всем. У меня снова вопрос по написанию программы для MSP430 на ассемблере.

Для выполнения определенных задач мне необходимо 32-х разрядное число умножить на 8-ми разрядное, результат разделить на 100, получить результат, а так же остаток от деления. Для умножения я использую аппаратный умножитель. А вот с делением проблема.

Пока единственным решением деления на 100 с остатком и вижу многократное вычитание делителя (100) из делимого (32-х разрядное число) до тех пор, пока результат не станет меньше 100. Сколько раз сделаю вычитание, то и будет частным, а оставшееся в результате вычитаний число - остаток.

Однако данный алгоритм деления долгий. Подскажите, может можно быстрее выполнить деление на 100 с остатком?

kovigor
Цитата(d7d1cd @ Jun 25 2013, 21:44) *
Подскажите, может можно быстрее выполнить деление на 100 с остатком?

Так ли уж необходимо делить на 100 ? Если это для индикации, то просто сместите запятую влево на два разряда. А если без деления никак, то у Atmel есть апп. ноут:

http://www.atmel.com/Images/doc0936.pdf
http://zalil.ru/34605572

Кстати, а почему бы такие вещи на Си не написать ? Зачем вы используете ассемблер ?
rezident
Цитата(d7d1cd @ Jun 25 2013, 23:44) *
Для выполнения определенных задач мне необходимо 32-х разрядное число умножить на 8-ми разрядное, результат разделить на 100, получить результат, а так же остаток от деления.
Определитесь более конкретно с диапазонами чисел и требуемой точностью результата деления. Если умножить любое большое 32-х разрядное число на 8-ми разрядное, то получится переполнение 32-х разрядной сетки. Значит нужно считать в 64-х разрядных числах?
Есть способ быстрого деления на константы с использованием умножения на "магические" числа и последующего деления с помощью операций сдвига. Но для подбора "магического" числа нужны критерии оглашенные выше. Пока могу только намекнуть.
Математическое преобразование X/100 = X * 1/100 является тождественным
А X * 1/100 ≈ X * 655/65536 = (X * 655) >> 16 - приближенным с заданной точностью (около -0,054%). В нем присутствует одно умножение и сдвиг на 16 бит вправо, либо в качестве результата деления можно просто взять старшее 16-и разрядное слово из 32-х разрядного числа.
rx3apf
Цитата(d7d1cd @ Jun 25 2013, 22:44) *
Однако данный алгоритм деления долгий. Подскажите, может можно быстрее выполнить деление на 100 с остатком?

А когда-то даже в школе учили делить "в столбик" wink.gif

Есть делимое, делитель, выделим регистры под остаток (в данном случае нужно 8 битов, так что один регистр, и тот наполовину), обнулим их. Сдвигаем влево делимое (младший бит обнуляем), старшие биты уползают в остаток. И пробуем из этого остатка вычесть делитель. Получилось ? Запишем в младший бит делимого (там же набирается частное) "1". Не получилось - оставляем 0. И так 32 раза. Частное будет там, где было делимое, остаток там, куда сдвигали.
d7d1cd
Цитата(kovigor @ Jun 26 2013, 00:00) *
Так ли уж необходимо делить на 100 ? Если это для индикации, то просто сместите запятую влево на два разряда. А если без деления никак, то у Atmel есть апп. ноут:

http://www.atmel.com/Images/doc0936.pdf
http://zalil.ru/34605572

Кстати, а почему бы такие вещи на Си не написать ? Зачем вы используете ассемблер ?

Да, именно необходим результат (целая часть и остаток) от деления на 100. Это не для индикации. Причину выбора ассемблера, если Вам интересно, могу написать в ЛС.

Цитата(rezident @ Jun 26 2013, 01:00) *
Определитесь более конкретно с диапазонами чисел и требуемой точностью результата деления. Если умножить любое большое 32-х разрядное число на 8-ми разрядное, то получится переполнение 32-х разрядной сетки. Значит нужно считать в 64-х разрядных числах?
Есть способ быстрого деления на константы с использованием умножения на "магические" числа и последующего деления с помощью операций сдвига. Но для подбора "магического" числа нужны критерии оглашенные выше. Пока могу только намекнуть.
Математическое преобразование X/100 = X * 1/100 является тождественным
А X * 1/100 ≈ X * 655/65536 = (X * 655) >> 16 - приближенным с заданной точностью (около -0,054%). В нем присутствует одно умножение и сдвиг на 16 бит вправо, либо в качестве результата деления можно просто взять старшее 16-и разрядное слово из 32-х разрядного числа.

Достоверно известно, что результат умножения не будет превышать 32-х разрядов, так как исходное 32-х разрядное число на самом деле будет занимать не более 24-х разрядов. Запас разрядов нужен для хранения результата умножения.
Деление способом умножения на "магическое" число я рассматривал, но в этом случае будет потеря какой-то части результата, а мне необходимо учитывать все. Остаток от деления - идеальный вариант для моей задачи.

Цитата(rx3apf @ Jun 26 2013, 01:36) *
А когда-то даже в школе учили делить "в столбик" wink.gif

Есть делимое, делитель, выделим регистры под остаток (в данном случае нужно 8 битов, так что один регистр, и тот наполовину), обнулим их. Сдвигаем влево делимое (младший бит обнуляем), старшие биты уползают в остаток. И пробуем из этого остатка вычесть делитель. Получилось ? Запишем в младший бит делимого (там же набирается частное) "1". Не получилось - оставляем 0. И так 32 раза. Частное будет там, где было делимое, остаток там, куда сдвигали.

Я проходил в школе деление столбиком wink.gif Однако применить это знание в моей задаче не додумался.
Когда Вы пишете "пробуем из этого остатка вычесть делитель", то вы имеете ввиду, что вычитание "получается" если результат не отрицательный? И еще: если вычитание "получилось", то результат вычитания должен быть записан в регистр для остатка?
rx3apf
Цитата(d7d1cd @ Jun 26 2013, 10:13) *
Когда Вы пишете "пробуем из этого остатка вычесть делитель", то вы имеете ввиду, что вычитание "получается" если результат не отрицательный?

Совершенно верно.
Цитата
И еще: если вычитание "получилось", то результат вычитания должен быть записан в регистр для остатка?

Да.
d7d1cd
rx3apf, спасибо за "школьный" алгоритм. Все работает как надо!
d7d1cd
Подскажите, а возможно ли быстро выполнить деление 16 разрядного числа на 3? Не используя принцип деления столбиком. Умножение на 3 сделать легко: Х*3 = Х*2+Х. А деление - это операция обратная умножению. Но я не могу додуматься. И возможно ли это?
_pv
при наличии аппаратного умножения делать его сдвигами будет только медленнее.
деления на константы можно заменять на умножения и сдвиги x/3 = x * 21845 / 65536 = (x * 21845) >> 16

◠◡◠
вот быстрое деление на 10:
Код
u8  divmod10_u32_rem;
u32 divmod10_u32(u32 n) {
  u32 quot = n >> 1;
  quot  += quot >> 1;
  quot  += quot >> 4;
  quot  += quot >> 8;
  quot  += quot >> 16;
  u32 qq = quot & ~7ul;
  quot >>= 3;
  divmod10_u32_rem = n - ((quot << 1) + qq);
  if (divmod10_u32_rem > 9) {
    divmod10_u32_rem -= 10;
    quot++;
  }
  return quot;
}


на 100 - поделить два раза по 10.
_pv
унможить два 32х разрядных числа (на 2^32/10 = 429496730) и взять старшие 32 разряда (поделить на 2^32) будет всё равно быстрее, тем более что в новых 5 и 6 серии умножитель 32х разрядный.
Harvester
Цитата(d7d1cd @ Oct 29 2013, 21:35) *
Подскажите, а возможно ли быстро выполнить деление 16 разрядного числа на 3? Не используя принцип деления столбиком. Умножение на 3 сделать легко: Х*3 = Х*2+Х. А деление - это операция обратная умножению. Но я не могу додуматься. И возможно ли это?

x/3 = x/2 - x/4 + x/8 - x/16 + x/32 - x/64 + ...
◠◡◠
Цитата
Подскажите, а возможно ли быстро выполнить деление 16 разрядного числа на 3?
Код
U16 div_by3_U16_soft(U16 data_in) {
    U32 U32_01, result;
    result = U32_01 = data_in;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    result += 0x5555; //correction
    return(result >> 16);
}

U16 div_by3_U16_hmul(U16 data_in) {
    return((((U32)data_in * 0x5555) + 0x5555) >> 16);
}
d7d1cd
Цитата(◠◡◠ @ Oct 31 2013, 11:50) *
Код
U16 div_by3_U16_soft(U16 data_in) {
    U32 U32_01, result;
    result = U32_01 = data_in;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    U32_01 <<= 2; result += U32_01;
    result += 0x5555; //correction
    return(result >> 16);
}

U16 div_by3_U16_hmul(U16 data_in) {
    return((((U32)data_in * 0x5555) + 0x5555) >> 16);
}

Ну вообще то на С можно и просто написать result = data_in / 3;
Я же пишу на асме. Краткость и быстрота кода - вот цель!
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Invision Power Board © 2001-2025 Invision Power Services, Inc.