Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Помогите придумать алгоритм деления!
Форум разработчиков электроники ELECTRONIX.ru > Сайт и форум > В помощь начинающему
marcinio
Задание примерно такое:
1<n<10000, 1<x<10000, n,x - целое число
надо узнать значения 1/n и x/n, n будет инкрементироваться каждую 0,001с, х выщитает программа
Как мне етого добиться с Atmega8535? 05.gif
rezident
x/n получается простым умножением на x результата деления 1/n smile.gif А делить можно "столбиком".
uriy
Может быть получится быстрее если вместо деления использовать сдвиг в случае когда n равно степени двойки
marcinio
да ладно - столбиком? biggrin.gif
это какой алгоритм!!! скоко времени надо!

Цитата
Может быть получится быстрее если вместо деления использовать сдвиг в случае когда n равно степени двойки


и скоко таких вариантов? 2;4;8;16;32;64;128;256;512;1024;2048;.. очень уж "много", если вместе 10000 вараинтов biggrin.gif Хоть идея неплохая!

Может есть какой нибудь другой вариант или линки? crying.gif
Как компьютер делит?

КСТАТИ - работаю с АВР СТУДИО
Николай Z
Цитата(marcinio @ Dec 16 2007, 13:32) *
Может есть какой нибудь другой вариант или линки? crying.gif
Как компьютер делит?

КСТАТИ - работаю с АВР СТУДИО


Cовершенно неважно с чем Вы работаете.
Нужный Вам линк вот этот: http://masterpc.alfaspace.net/books/downloads/knut_part2/
Кнут - Искусство программирования... Нужные Вам алгоритмы - в 4-й главе, после подзаголовка "Арифметика целых чисел" и далее.

Я думаю вряд ли Вы где-то найдете более полное описание.
syoma
Вот здесь http://electronix.ru/forum/index.php?showtopic=34696 я спрашивал и выбрал алгоритм Ньютона. Работает быстро и легко реализуется. Я думаю Вам подойдет. Единственное, что требуется умножение.
marcinio
Вот я посмотрел такой алгоритм (кстати - столбик smile.gif ) НО я никак не могу его понять:
1 в каких тогда случаях остаток - делитель будет >0 ???? если уж остаток в начале 0, тогда при любых сдвигах он же всёравно будет 0, а тогда остаток - делитель всегда будет ниже 0...
2 я посмотрел книгу Кнута - понял что на данный момент у меня нет столько времени, чтобы это всё прочитать и понять smile.gif потому - что нам даёт сдвиг?

Алгоритм подпрограмм деления целых беззнаковых чисел (Рис. 3) можно представить в виде последовательности следующих шагов:
1 Очистить остаток и перенос
2 Загрузить в счетчик цикла число 9
3 Делимое сдвинуть влево с использованием переноса.
4 Уменьшить на 1 счетчик цикла
5 Если счетчик цикла равен 0, то выйти из подпрограммы
6 Остаток сдвинуть влево с использованием переноса
7 Вычесть делитель из остатка
8 Если остаток отрицательный, прибавить обратно делитель, сбросить перенос и идти к шагу 3.
9 Установить перенос и идти к шагу 3.

R15 "drem8u" - остаток
R16 "dd8u"-делимое "dres8u" - результат
R17 "dv8u"-делитель
R18 "dcnt8u"- счетчик цикла
Нажмите для просмотра прикрепленного файла
Николай Z
Цитата(marcinio @ Dec 16 2007, 16:36) *
2 я посмотрел книгу Кнута - понял что на данный момент у меня нет столько времени, чтобы это всё прочитать и понять smile.gif потому - что нам даёт сдвиг?

Там все и не надо читать. Там только нужно посмотреть програмку умножения и/или деления и истратить немного времени, чтобы разобраться в командах т.н. "MIX" и ничего больше.
Qwertty
Тут уже целочисленная арифметика не подходит.
С целочисленной 1/n будет единицей, если n=1, и 0 во всех остальных случаях. Хорошо еще что n не может равняться 0 smile.gif Аналогично и с x/n - если n>x то результат нулевой. Так что Вас ждет плавучка, да еще на ассемблере sad.gif
defunct
Цитата
Как мне етого добиться с Atmega8535?

банально взять любой C компилятор и написать ровно то, что требуется:

Код
float result = x / n;
Gogan
Цитата(marcinio @ Dec 15 2007, 23:50) *
Задание примерно такое:
1<n<10000, 1<x<10000, n,x - целое число
надо узнать значения 1/n и x/n, n будет инкрементироваться каждую 0,001с, х выщитает программа
Как мне етого добиться с Atmega8535? 05.gif

Для начала нужно решить, сколько знаков после запятой хочется получить. Например 4, тогда делить нужно 10000/n, результат будет от 1 до 10000, думаю дальше понятно что с ним делать.
Используем двубайтное число (unsigned int).
А готовый асемблеровский код можно легко получить если посмотреть откопиленный код с помощью CodeVison. Вот что у меня получилось
(код на C:
unsigned int a,b;
...
a=432;
b=10000/a; )
Код
main:

;......

; a=432 (a хранится в регистрах R4,R5)
    LDI  R30,LOW(432)
    LDI  R31,HIGH(432)
    MOVW R4,R30

;b=10000/a (b хранится в регистрах R6,R7)
    MOVW R30,R4
    LDI  R26,LOW(10000)
    LDI  R27,HIGH(10000)
    RCALL __DIVW21U
    MOVW R6,R30

; ......

rjmp main


__DIVW21U:
    CLR  R0
    CLR  R1
    LDI  R25,16
__DIVW21U1:
    LSL  R26
    ROL  R27
    ROL  R0
    ROL  R1
    SUB  R0,R30
    SBC  R1,R31
    BRCC __DIVW21U2
    ADD  R0,R30
    ADC  R1,R31
    RJMP __DIVW21U3
__DIVW21U2:
    SBR  R26,1
__DIVW21U3:
    DEC  R25
    BRNE __DIVW21U1
    MOVW R30,R26
    MOVW R26,R0
    RET
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Invision Power Board © 2001-2025 Invision Power Services, Inc.