Форум программистов, компьютерный форум, киберфорум
Наши страницы
Микроконтроллеры Atmega AVR
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.83/138: Рейтинг темы: голосов - 138, средняя оценка - 4.83
putmom
0 / 0 / 0
Регистрация: 05.02.2012
Сообщений: 35
1

Деление на 10.

09.01.2013, 10:03. Просмотров 25139. Ответов 67
Метки нет (Все метки)

Нашел тут статейку по методам деления на 10 (http://we.iosyitistromyss.ru/Soft/pr...ye-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.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.01.2013, 10:03
Ответы с готовыми решениями:

Задача про деление яблок (целочисленное деление)
Ребят,помогите с задачкой,как написать input.txt и output.txt? Помогите решить задачу. C++....

Умножение, деление и деление с остатком
Рассмотрим эти операции на примере. static void Main() { int i = 100, j = 15; double a =...

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

Деление
Всем привет! Нужна помошь по математике :wacko: Нужно делить дробные числа. Максимальное число...

Деление
data SEGMENT a DW 20 b DW 6 c DW ? data ENDS code SEGMENT assume cs:code,ds:data...

67
THI BIOST
0 / 0 / 0
Регистрация: 23.01.2010
Сообщений: 1,142
14.01.2013, 12:22 61
Цитата Сообщение от Johmmy0007
Мы тут касаемся точных алгоритмов, а они часто не нужны на практике абсолютно, как в случае с велосипедом.
Например снимаем показания с АЦП - там уже есть погрешности, так стоит ли ломать голову, проще добавить ещё одну, но упростить алгоритм.

например, можно заменить деление умножением, поскольку аппаратный умножитель имеется.
надо поделить на 10? тупо умножаем на дробь, обратную данной, т.е. 1/10
1/10 это примерно 6554/65536
в знаменателе - число, на которое легко делить сдвигом (степень двойки)
так можно делить на любые числа, не забивая себе голово заумными алгоритмами, про погрешность я уже сказал, будет - но в разумных пределах и ничего страшного
То что я написал выше - точный алгоритм при соблюдении указанных ограничений и очень быстрый. А так как Вы предлагаете - делать нельзя. В крайнем случае - только для младшего разряда.
0
Johmmy0007
1 / 1 / 0
Регистрация: 30.08.2011
Сообщений: 9,944
14.01.2013, 12:26 62
В связи с чем это - нельзя? Запрещено Конституцией что ли? очень даже можно по причинам, которые я указал выше.

Я указал общий принцип неточного, но часто достаточного приемлимого алгоритма деления на любые числа. А кому можно, а кому нельзя пусть каждый выбирает сам в зависимости от ситуации
0
THI BIOST
0 / 0 / 0
Регистрация: 23.01.2010
Сообщений: 1,142
14.01.2013, 12:33 63
Потому, что так можно (при последовательном делении) только для младшего разряда, который на глаз, а вот старшие могут быть сильно покалеченными.

Вот ещё: деление беззнаковых 16 бит на 10 с остатком - точный алгоритм на всём диапазоне:

Q = D/10

Q - результат
D - остаток

Код
#define cDIV_10  0xCCCD      // multiplicative inverse of 10

Div16_10:
ldi     rDIV_M0, low(cDIV_10)
ldi     rDIV_M1, high(cDIV_10)

// mul 16x16 => 32 discarding 16 lsbs
clr     rDIV_R0

mul     rDIV_M1, rDIV_D1
movw    rDIV_Q0, r0

mul     rDIV_M0, rDIV_D0
mov     rDIV_R1, r1

mul     rDIV_M1, rDIV_D0
add     rDIV_R1, r0
adc     rDIV_Q0, r1
adc     rDIV_Q1, rDIV_R0

mul     rDIV_M0, rDIV_D1
add     rDIV_R1, r0
adc     rDIV_Q0, r1
adc     rDIV_Q1, rDIV_R0

// quotient >>= 3
lsr     rDIV_Q1
ror     rDIV_Q0
lsr     rDIV_Q1
ror     rDIV_Q0
lsr     rDIV_Q1
ror     rDIV_Q0

// multiple quotient back (*10)
ldi     rDIV_M0, 10
mul     rDIV_Q0, rDIV_M0
movw    rDIV_R0, r0
mul     rDIV_Q1, rDIV_M0
add     rDIV_R1, r0

// calculate reminder (now in dividend)
sub     rDIV_D0, rDIV_R0
sbc     rDIV_D1, rDIV_R1
ret
0
Johmmy0007
1 / 1 / 0
Регистрация: 30.08.2011
Сообщений: 9,944
14.01.2013, 12:39 64
причём тут последовательное деление?
Я написал как сразу поделить одно число на другое и получить приемлимый результат
надо мне, к примеру поделить 356 на 10

(356*6554) shr 16 = 35 - очень быстро, кого-то не устроит, а кого- то вполне
0
putmom
0 / 0 / 0
Регистрация: 05.02.2012
Сообщений: 35
14.01.2013, 13:07 65
Цитата Сообщение от Johmmy0007
причём тут последовательное деление?
Я написал как сразу поделить одно число на другое и получить приемлимый результат
надо мне, к примеру поделить 356 на 10

(356*6554) shr 16 = 35 - очень быстро, кого-то не устроит, а кого- то вполне
Хороший способ, но в меге-8 результат умножения не должен превышать 65535, в Вашем случае он гораздо больше.
Может быть как то можно обойти это ограничение ? т.е. средствами команды MUL умножать числа более 256 * 256 ?
0
THI BIOST
0 / 0 / 0
Регистрация: 23.01.2010
Сообщений: 1,142
14.01.2013, 13:26 66
Цитата Сообщение от putmom
Хороший способ, но в меге-8 результат умножения не должен превышать 65535, в Вашем случае он гораздо больше.
Может быть как то можно обойти это ограничение ? т.е. средствами команды MUL умножать числа более 256 * 256 ?
Я код выше написал, только он не приблизительный.
0
Johmmy0007
1 / 1 / 0
Регистрация: 30.08.2011
Сообщений: 9,944
14.01.2013, 13:29 67
to putmom
умножение многоразрядных чисел
http://controllersystems.com/books/prak ... hisel.html

>>в Вашем случае он гораздо больше.

я ж просто пример привёл,
просто чем больше числа в числителе и знаменателе, тем точнее результат (можно точнее подобрать соотношение числителя и знаменателя)

а где-то и меньшие числа подойдут
например
можно умножить и на 26/256

356*26 shr 8=36
и на 13/128
356*13 shr 7=36

единственное - остаток не получишь, но он часто и не нужен,
главное чтоб вы сами понимали, что выигрываете и что проигрываете

в вашем случае, может метод THI BIOST и лучше, но и то что я пишу - на заметку возьмите, пригодится, точность далеко не всегда нужна - мы ж в реальной жизни живём, иногда скорость и объём памяти куда важнее
0
putmom
0 / 0 / 0
Регистрация: 05.02.2012
Сообщений: 35
14.01.2013, 13:49 68
Всем спасибо, разбираюсь.
0
14.01.2013, 13:49
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.01.2013, 13:49

Деление на 0
Все говорят на 0 делить нельзя,но я поделил,в чем тут подвох #include &lt;iostream&gt; using...

Деление на 5
Дано число в шестнадцатеричной системе счисления. Число может быть очень большое. Требуется...

деление
подскажите. допустим в переменной типа string находится число 8192. требуется разделить это число...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
68
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru