unsigned long поделить на 10 и на 100, ну как нить совсем не стандартно... Опции

[singlskv]

Собственно сабжект
умножение на 429496730 и на 42949673 не предлагать,
не катит из-за нехватки регистров на нормальную реализацию... и память тю-тю...

[rezident]

Циклическим вычитанием десятков и сотен.
На всякий случай поясняю.
Нужно найти значение X/10.
Пусть X/10=Y
X-X/10*10=0 тождество верное, не так ли?
Тогда X-Y*10=0
Вычитаем в цикле число 10 из значения X до тех пор, пока разность не будет меньше или равно нулю десяти. Считаем количество вычитаний. Значение счетчика вычитаний это Y.
Возвращаясь назад Y=X/10, что и требовалось получить.

Update. Исправил алгоритмическую ошибку в описании. Вычитать нужно пока остаток разности больше основания (10, 100 ...), а не нуля.

Сообщение отредактировал rezident - Apr 26 2011, 12:04

[Tiro]

Лучше через вычитания деление выполнять не последовательным вычитанием делителя, а вычитанием убывающих степеней делителя.

Например, y=x/10^c (где с = 1, 2, 3, ..)
Представим x=x9*10^9+x8*10^8+..x1*10+x0, тогда y=y9*10^(9-c)+y8*10^(8-1)+..y1*10^(1-c)+y0*10^(-c)
Естественно, все, что меньше единицы в частном нам не нужно, то есть вычисления с y0 откидываем для 10, y0 и y1 откидываем для 100. И т.д.
Собственно, алгоритм будет лишен делений и умножений, будут использоваться только вычитания и сложения.

Делим на 10:
while (x-10^9 > 0) y+=10^8 // ищем y9
while (x-10^8 > 0) y+=10^7 // ищем y8
..
while (x-10 > 0) y+=1 // ищем y1
Готово.

З.Ы. Основанием степени не обязательно должно быть 10 )))
З.З.Ы В тяжелых случаях можно делить приблизительно, умножая на дробь со знаменателем в виде 2^n, близкую к 1/10 (например 13/128)

[_dem]

BCD ?

[hd44780]

А на чем пишем? На С, на асме?

Еще один способ, может пригодится.... Не деление в прямом смысле слова, но результат дает.

Ковертируем делимое в строку: 2949673 -> "2949673". Наверняка такая функция уже есть готовая..
Для деления на 10 достаточно "откусить" от строки один знак справа, получим "294967".
На 100 - откусываем 2 знака - "29496".
Конвертируем полученную строку в число - тоже стандартная и не слишком затратная процедура.
Для оптимизации откусывание можно объединить с конвертированием. Оно ведь всегда справа начинается.

Родственные алгоритмы применяются в кассовых аппаратах, т.к. там никто никогда плавающую точку и прочие "долгоиграющие" алгоритмы не реализовывает. И все основано на подобных "хитростях".
По сути - двигаем десятичную точку вправо или влево.

Сообщение отредактировал hd44780 - Apr 26 2011, 07:01

[Палыч]

Ковертируем делимое в строку: 2949673 -> "2949673". Наверняка такая функция уже есть готовая..

Обычно, такие функции требуют значительных ресурсов... Лучше тогда - BCD, как предложил _dem

[=GM=]

не катит из-за нехватки регистров на нормальную реализацию... и память тю-тю

Сколько регистров есть в наличии? Если делитель состоит из одного байта, то должно хватить трёх регистров. Если к тому же делитель константа, то хватит двух регистров.

[singlskv]

Сколько регистров есть в наличии? Если делитель состоит из одного байта, то должно хватить трёх регистров. Если к тому же делитель константа, то хватит двух регистров.

для деления unsigned long на 10 или 100 ?

суть здесь вот в чем есть стандартное деление на С которое
получает на вход 2 четырех байтовых числа и возвращает назад 4x байтовое
внутри функции деления используется еще 5 рабочих регистров
все бы хорошо, но эта функция работает не очень быстро,
ну примерно тактов 600

мне же нужно поделить только на 2 однобайтовые константы 10 и 100
стандартный в таких случаях путь домножения на 2^N / 10 не очень подходит
т.к. это предполагает умножение 2х четырех байтовых с получением восмибайтового и взятием от него старшей части
но IAR такое умножение выносит в библиотечную функцию как умножение 8байт на 8байт
и вот тут никаких регистров уже не хватает

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

и еще что бы это было на С ...

[hd44780]

и еще что бы это было на С ...

По-моему ты хочешь невозможного.
Компилятор С использует свои готовые функции для этого. Причем у каждого компилятора свои.
И он не позволит тебе их менять.
Если они тебя не устраивают, пиши свои на асме(!) и вызывай их как обычные функции.
Но будет ли это эффективнее и оптимальнее родных - фиг знает.

Но надо сперва найти какой-то алгоритм самого деления. А эти алгортимы, если мне память не изменяет, стандартны.
Например, - http://www.distedu.ru/mirror/_inform/dmivi...inform/div.html
Дальше вопрос уже в реализации этих алгоритмов.

Но ты делишь на 10 и 100, а это не степени двойки. Значит, довольствоваться общим алгоритмом.

Сообщение отредактировал hd44780 - Apr 26 2011, 11:54

[ukpyr]

хм, почешу-ка репу...

n = n1 * 65536 + n2; // представляем как 2 16-битных
n/10 = (n1 * 65536)/10 + (n2 / 10) = (n1 * 32768)/5 + (n2 >> 1)/5 = (n1 / 5) << 15 + (n2 >> 1)/5

деление на 5 16-битного целого можно сделать так: (((U32)data * 0x3333) + 0x3333) >> 16

[singlskv]

хм, почешу-ка репу...

n = n1 * 65536 + n2; // представляем как 2 16-битных
n/10 = (n1 * 65536)/10 + (n2 / 10) = (n1 * 32768)/5 + (n2 >> 1)/5 = (n1 / 5) << 15 + (n2 >> 1)/5

деление на 5 16-битного целого можно сделать так: (((U32)data * 0x3333) + 0x3333) >> 16

У меня тоже вокруг такого варианта мысли крутятся, но здесь есть ошибка
остаток от деления n1/5 сдвинутый на 15 разрядов нужно приплюсовывать к (n2>>1) и только потом делить на 5

[=GM=]

для деления unsigned long на 10 или 100?

Если надо делить на любую константу меньшую 256, то достаточно двух регистров, если писать на ассемблере. Скорее всего, можно и на си, просто не знаю, насколько экономно иар распоряжается регистрами.

[singlskv]

n = n1 * 65536 + n2; // представляем как 2 16-битных
n/10 = (n1 * 65536)/10 + (n2 / 10) = (n1 * 32768)/5 + (n2 >> 1)/5 = (n1 / 5) << 15 + (n2 >> 1)/5

деление на 5 16-битного целого можно сделать так: (((U32)data * 0x3333) + 0x3333) >> 16

Спасибо за гениальную идею поделить сначала на 2 а уже потом на 5,
а то у меня никак разрядности не хватало.
Если нигде не ошибся то код для деления на 10 такой:

Код

              DWORD N = ...; // делимое
              DWORD result;
              N >>= 1;
              result = (((N >> 16) + 1) * 0x3333) & 0xFFFF0000;
              result |= ((N - result * 5 + 1) * 0x3333) >> 16;

итого примерно 100 тактов против 600 у обычного деления.

Теперь нужно /100 , хотя конечно можно 2 раза поделить на 5...

[ukpyr]

желательно протестировать весь диапазон long int, мало ли что...

протестировал - ваш алгоритм дает кучу ошибок, начиная с 131080 (вместо 13108 получается 13107).
там после умножения на 0x3333 обязательно нужна коррекция - прибавить 0x3333

Сообщение отредактировал ukpyr - Apr 26 2011, 14:41

[singlskv]

желательно протестировать весь диапазон long int, мало ли что...

протестировал - ваш алгоритм дает кучу ошибок, начиная с 131080 (вместо 13108 получается 13107).
там после умножения на 0x3333 обязательно нужна коррекция - прибавить 0x3333

коррекция на 0x3333 уже есть в коде
но ошибки действительно есть т.к. после добавления остатка от деления старшей части
у нас диапазон становится 0 - 0x50000

сейчас будем допиливать...

Вроде так корректно:

Код

              DWORD N = ...; // делимое
              DWORD result;
              N >>= 1;
              result = (((N >> 16) + 1) * 0x3333) & 0xFFFF0000;
              N = N - result * 5 + 1;
              N += N >> 16; // коррекция для диапазона 0x10000 - 0x50000
              result |= (N  * 0x3333) >> 16;