Easyelectronics.ru

Электроника для всех
Текущее время: 23 янв 2021, 00:08

Часовой пояс: UTC + 5 часов



JLCPCB – Прототипы печатных плат за $2/5шт. два слоя. $5/5шт. четыре слоя
Крупнейший производитель печатных плат и прототипов. Более 600000 клиентов и свыше 10000 заказов в день!
Получите скидку на почтовую отправку при первом заказе в JLCPCB!

Начать новую тему Ответить на тему  [ Сообщений: 70 ]  На страницу 1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 09:50 
Заглядывает иногда

Зарегистрирован: 09 фев 2012, 23:51
Сообщения: 35
Нашел тут статейку по методам деления на 10 (http://we.easyelectronics.ru/Soft/preobrazuem-v-stroku-chast-1-celye-chisla.html).
Заинтересовал метод сдвигами и сложениями.
Цитирую:
Цитата:
Код:
struct divmod10_t
{
    uint32_t quot;
    uint8_t rem;
};
inline static divmod10_t divmodu10(uint32_t n)
{
    divmod10_t res;
// умножаем на 0.8
    res.quot = n >> 1;
    res.quot += res.quot >> 1;
    res.quot += res.quot >> 4;
    res.quot += res.quot >> 8;
    res.quot += res.quot >> 16;
    uint32_t qq = res.quot;
// делим на 8
    res.quot >>= 3;
// вычисляем остаток
    res.rem = uint8_t(n - ((res.quot << 1) + (qq & ~7ul)));
// корректируем остаток и частное
    if(res.rem > 9)
    {
        res.rem -= 10;
        res.quot++;
    }
    return res;
}

Выглядит страшно и непонятно, но на самом деле всё просто. Сначала умножаем исходное число на 0.8 или 0.1100 1100 1100 1100 1100 1100 1100 1100 в двоичном представлении. Очень удобно, что дробь периодическая и удалось обойтись всего пятью сдвигами и четырьмя сложениями. Далее делим то, что получилось на 8, сдвигая на 3 разряда вправо. Получается исходное число делённое на 10 с точностью до единицы из-за ошибок округления.

Сижу и не понимаю, как всё таки на 0.8 умножать ? Какие то сдвиги вижу в коде, но Си не понимаю =(
Разжуйте пожалуйста как на ассемблере умножить на 0.8.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 10:15 
Старожил

Зарегистрирован: 04 окт 2012, 00:23
Сообщения: 2745
Откуда: Москва
Плиз


Вложения:
AVR200.zip [163.39 Кб]
Скачиваний: 229
Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 10:29 
Заглядывает иногда

Зарегистрирован: 09 фев 2012, 23:51
Сообщения: 35
ILYAUL писал(а):
Плиз

Спасибо, но тут не сдвигами деление на 10.
Такие процедуры для 8-ми битных переменных я делал.
Мне нужно быстрое деление на 10, как в примере в моём первом посте, но на ассемблере.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 10:56 
Старожил
Аватара пользователя

Зарегистрирован: 23 сен 2010, 13:27
Сообщения: 2382
Откуда: Тамбовская обл.
Есть процедура разложения 16-битного числа в десятичные цифры, там как раз делениями на 10 и выделением остатка. Надо?
Правда циклом.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 10:58 
Старожил

Зарегистрирован: 06 фев 2011, 15:16
Сообщения: 618
Откуда: Челябинск
putman писал(а):
Нашел тут статейку по методам деления на 10 (http://we.easyelectronics.ru/Soft/preobrazuem-v-stroku-chast-1-celye-chisla.html).
Заинтересовал метод сдвигами и сложениями.
Цитирую:
Цитата:
Код:
struct divmod10_t
{
    uint32_t quot;
    uint8_t rem;
};
inline static divmod10_t divmodu10(uint32_t n)
{
    divmod10_t res;
// умножаем на 0.8
    res.quot = n >> 1;
    res.quot += res.quot >> 1;
    res.quot += res.quot >> 4;
    res.quot += res.quot >> 8;
    res.quot += res.quot >> 16;
    uint32_t qq = res.quot;
// делим на 8
    res.quot >>= 3;
// вычисляем остаток
    res.rem = uint8_t(n - ((res.quot << 1) + (qq & ~7ul)));
// корректируем остаток и частное
    if(res.rem > 9)
    {
        res.rem -= 10;
        res.quot++;
    }
    return res;
}

Выглядит страшно и непонятно, но на самом деле всё просто. Сначала умножаем исходное число на 0.8 или 0.1100 1100 1100 1100 1100 1100 1100 1100 в двоичном представлении. Очень удобно, что дробь периодическая и удалось обойтись всего пятью сдвигами и четырьмя сложениями. Далее делим то, что получилось на 8, сдвигая на 3 разряда вправо. Получается исходное число делённое на 10 с точностью до единицы из-за ошибок округления.

Сижу и не понимаю, как всё таки на 0.8 умножать ? Какие то сдвиги вижу в коде, но Си не понимаю =(
Разжуйте пожалуйста как на ассемблере умножить на 0.8.

Код:
    res.quot = n >> 1;      //0.5x
    res.quot += res.quot >> 1;    //0.75x
    res.quot += res.quot >> 4;    //0.796875x
    res.quot += res.quot >> 8;    //0.7999877929685x
    res.quot += res.quot >> 16;   //0.79999999813735485076904296875x
Или нет?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 11:00 
Старожил

Зарегистрирован: 04 окт 2012, 00:23
Сообщения: 2745
Откуда: Москва
10=0xA=2^3+2= Всё осталось только воспользоваться сдвигами- догадаетесь как это сделать надеюсь сами.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 11:04 
Заглядывает иногда

Зарегистрирован: 09 фев 2012, 23:51
Сообщения: 35
Bill писал(а):
Код:
    res.quot = n >> 1;      //0.5x
    res.quot += res.quot >> 1;    //0.75x
    res.quot += res.quot >> 4;    //0.796875x
    res.quot += res.quot >> 8;    //0.7999877929685x
    res.quot += res.quot >> 16;   //0.79999999813735485076904296875x
Или нет?

Я же выше писал, что Си не понимаю, мне пожалуйста тоже самое на ассемблере.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 11:05 
Заглядывает иногда

Зарегистрирован: 09 фев 2012, 23:51
Сообщения: 35
ploop писал(а):
Есть процедура разложения 16-битного числа в десятичные цифры, там как раз делениями на 10 и выделением остатка. Надо?
Правда циклом.

Циклом я и сам написал, но долго работает, надо сдвигами.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 11:06 
Заглядывает иногда

Зарегистрирован: 09 фев 2012, 23:51
Сообщения: 35
ILYAUL писал(а):
10=0xA=2^3+2= Всё осталось только воспользоваться сдвигами- догадаетесь как это сделать надеюсь сами.

Так то оно так, это я понял, но как это реализовать в коде не понимаю, учусь еще, да и туповат маленько.
3 раза сдвинуть вправо это понятно, но как 2 получить ?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 11:11 
Старожил

Зарегистрирован: 04 окт 2012, 00:23
Сообщения: 2745
Откуда: Москва
lsr и ror = деление на 2
lsl & rol = умножение на 2
add & adc - сложение
Осталось раставить
subi xз,-2 прибавить


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 11:23 
Заглядывает иногда

Зарегистрирован: 09 фев 2012, 23:51
Сообщения: 35
ILYAUL писал(а):
lsr и ror = деление на 2
lsl & rol = умножение на 2
add & adc - сложение
Осталось раставить
subi xз,-2 прибавить

Давайте попробуем как Вы говорите.
Допустим у нас число 210 (0b11010010)
делим его на 8
Код:
ldi  temp, 210
lsr  temp
lsr  temp
lsr  temp
subi temp, -2

в результате получаем 28, на самом деле надо 2 вычитать т.к. делим, но тогда получим 24, что далеко от верного результата 21.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 11:28 
Старожил
Аватара пользователя

Зарегистрирован: 23 сен 2010, 13:27
Сообщения: 2382
Откуда: Тамбовская обл.
Верный - 26, получится тремя сдвигами. Это если на 8 :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 11:29 
Старожил

Зарегистрирован: 04 окт 2012, 00:23
Сообщения: 2745
Откуда: Москва
Код:
lsr  temp
lsr  temp
lsr  temp
Не правильно - читаем о каждой из приведённых мной команд и исправляем


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 11:32 
Старожил
Аватара пользователя

Зарегистрирован: 03 сен 2011, 21:13
Сообщения: 13139
Откуда: г.Мариинск, Кемеровская обл. , мать Россия
putman писал(а):
ILYAUL писал(а):
Плиз

Спасибо, но тут не сдвигами деление на 10.
Такие процедуры для 8-ми битных переменных я делал.
Мне нужно быстрое деление на 10, как в примере в моём первом посте, но на ассемблере.

часто тупо в цикле вычитатают из числа 10, подсчитывая количество циклов, пока результат вычитания не станет меньше 0

_________________
Лишний повод не бриться: Если у меня растёт борода, значит, это зачем-то нужно? О, Господи, неужели я - философ?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 11:47 
Старожил
Аватара пользователя

Зарегистрирован: 23 сен 2010, 13:27
Сообщения: 2382
Откуда: Тамбовская обл.
Да и сомневаюсь я, что сдвигами выйдет быстрее.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 11:52 
Заглядывает иногда

Зарегистрирован: 09 фев 2012, 23:51
Сообщения: 35
ILYAUL писал(а):
Код:
lsr  temp
lsr  temp
lsr  temp
Не правильно - читаем о каждой из приведённых мной команд и исправляем

Я же намекнул, туповат я и учусь еще. Не пойму как надо исправлять, напишите лучше сами =)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 11:52 
Старожил
Аватара пользователя

Зарегистрирован: 23 сен 2010, 13:27
Сообщения: 2382
Откуда: Тамбовская обл.
http://www.microchip.ru/phorum/read.php ... 77&t=14577
И да, скольки разрядное число делить-то?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 11:53 
Заглядывает иногда

Зарегистрирован: 09 фев 2012, 23:51
Сообщения: 35
Johnny0007 писал(а):
putman писал(а):
ILYAUL писал(а):
Плиз

Спасибо, но тут не сдвигами деление на 10.
Такие процедуры для 8-ми битных переменных я делал.
Мне нужно быстрое деление на 10, как в примере в моём первом посте, но на ассемблере.

часто тупо в цикле вычитатают из числа 10, подсчитывая количество циклов, пока результат вычитания не станет меньше 0

Такая процедура у меня есть, я её даже не искал нигде, она очевидна, и сразу её написал.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 11:55 
Старожил
Аватара пользователя

Зарегистрирован: 29 май 2010, 18:46
Сообщения: 4189
Откуда: Киев
Johnny0007 писал(а):
часто тупо в цикле вычитатают из числа 10, подсчитывая количество циклов, пока результат вычитания не станет меньше 0
+1
Я даже удивлен, что кого-то серьезно заинтересовало иначе делать :)
Так же и большое число преобразовать в 10-чное, только сначала пробуем отнимать самую большую степень десятки (например, 1000), потом, если отнимать нечего - 100, а после отнимания 10 получим последнюю цифру результата.

2 putman: есди у тебя цель потрахаться с программированием - тогда да, можешь разбираться дальше. А все же метод отнимания дает результат - и поробуй его обругать, если хочешь. Ну, ТИПА, сравнить 2 метода. А мы посмотрим.

А, вижу ты не понял с многоразрядным. Ну, читай мой пост


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 11:56 
Старожил

Зарегистрирован: 04 окт 2012, 00:23
Сообщения: 2745
Откуда: Москва
putman писал(а):
ILYAUL писал(а):
Код:
lsr  temp
lsr  temp
lsr  temp
Не правильно - читаем о каждой из приведённых мной команд и исправляем

Я же намекнул, туповат я и учусь еще. Не пойму как надо исправлять, напишите лучше сами =)

Нет уж , если сами не найдёте решение, Вам не надо заниматся MC - там математика на каждом шаге


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 11:58 
Старожил

Зарегистрирован: 06 фев 2011, 15:16
Сообщения: 618
Откуда: Челябинск
putman писал(а):
Bill писал(а):
Код:
    res.quot = n >> 1;      //0.5x
    res.quot += res.quot >> 1;    //0.75x
    res.quot += res.quot >> 4;    //0.796875x
    res.quot += res.quot >> 8;    //0.7999877929685x
    res.quot += res.quot >> 16;   //0.79999999813735485076904296875x
Или нет?

Я же выше писал, что Си не понимаю, мне пожалуйста тоже самое на ассемблере.

Код:
; n <- r16, r17, r18, r19
  lsr     r19        ; n = n >> 1
  ror    r18            ;
  ror    r17            ;
  ror    r16            ;
  movw r17:r16, r21:r20  ; res.quot = n
  movw r19:r18, r23:r22        ;
  lsr     r23        ; res.quot >> 4
  ror    r22            ;
  ror    r21            ;
  ror    r20            ;
  lsr     r23            ;
  ror    r22            ;
  ror    r21            ;
  ror    r20            ;
  add   r20, r16  ; res.quot += res.quot >> 4
  adc   r21. r17     ;
  adc   r22, r18     ;
  adc   r23, r19     ;
......


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 12:13 
Старожил
Аватара пользователя

Зарегистрирован: 23 сен 2010, 13:27
Сообщения: 2382
Откуда: Тамбовская обл.
Цитата:
есди у тебя цель потрахаться с программированием - тогда да, можешь разбираться дальше. А все же метод отнимания дает результат - и поробуй его обругать, если хочешь. Ну, ТИПА, сравнить 2 метода. А мы посмотрим.

Да что там сравнивать, если числа 16-, 24- и более битные, никакими сдвигами короче не получится. Ну выиграется несколько тактов, зато на полкило флеша код раздуется. А в цикле каких-то несколько строк, читабельно и наглядно.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 10 янв 2013, 12:31 
Заглядывает иногда

Зарегистрирован: 09 фев 2012, 23:51
Сообщения: 35
ILYAUL писал(а):
Нет уж , если сами не найдёте решение, Вам не надо заниматся MC - там математика на каждом шаге

Ну спасибо, бросить, какие ещё предложения ?
Просто сами не знаете.
Вот тут понял, по ссылке ploop.

Цитата:
Число сдвигаеш вправо три раза.
Сохраняеш результат как временный.(результат деления на 8 и осталось отнять еще
две части для полного счастья)
Сдвигаеш еще два раза вправо.(результат деления восьми на 4 - получим 2 части)
Полученное число вычитаем из временно сохраненного и получаем результат деления
на 10 без остатка.
------------------------------------
Круглого деления простым сдвигом не получешь, т. к. 10 содержит простое 5,
которое не является степенью двойки.
------------------------------------
Для 8-битного числа 1/10 = 1/8 - 1/32 + 1/128 + остаток.

Спасибо всем, разобрался.
Действительно оно того не стоит, вычитанием 10-ки проще и нагляднее получается.
Оставляю значит как есть процедуру в своей программе.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 11 янв 2013, 22:30 
Старожил
Аватара пользователя

Зарегистрирован: 16 окт 2011, 11:19
Сообщения: 853
Откуда: Харьков
putman писал(а):
Действительно оно того не стоит, вычитанием 10-ки проще и нагляднее получается.
Оставляю значит как есть процедуру в своей программе.

«Цыганский шахматист считает партию проигранной, если потерял двух коней»

Я бы не стал так быстро сдаваться. Безусловно, за скорость придется платить, но мне кажется, уважаемые Гуру несколько сгущают краски. Загадочный алгоритм, с которым не разобрался ТС действительно достаточно быстрый, реализация на асме у меня получилась всего менее, чем в три раза длинней классического деления из апноты AVR200. «Классика» 32/32=32+32(остаток) занимает примерно 32 КОПа и выполняется где то за 850 тактов. Пример ТСа получился у меня длинной 87 КОПов и выполняется за 80/87 такта в зависимости от необходимости коррекции результата, на минуточку в !10! раз быстрей.
Show


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Деление на 10.
СообщениеДобавлено: 12 янв 2013, 04:29 
Старожил

Зарегистрирован: 22 мар 2010, 22:54
Сообщения: 3995
ploop писал(а):
Ну выиграется несколько тактов, зато на полкило флеша код раздуется.

когда-то в очень далеком детстве я делал плеер музыки с винта, на котором был фат. на асме з80. надо было вычислять номер сектора по номеру кластера, кол-ву секторов в кластере и все такое. и чтобы долго не мутить, сделал точно такие же делилки и умножалки с циклами. заработало все отлично, но вот когда винт забил музыкой подзавязку, дальние треки он стал вычислять НЕРЕАЛЬНО ДОЛГО. так что не везде такой метод подходит.

и даже универсальная быстрая делилка (а не на конкретную константу) полкило флеша точно не займет.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 70 ]  На страницу 1, 2, 3  След.


Часовой пояс: UTC + 5 часов


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB