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;

[=GM=]

Чёт не всё понимаю. Вроде бы поначалу борьба шла за малое количество используемых регистров. А сейчас за што бодаетесь?

[singlskv]

да, теперь все четко, вот код теста на VC:

Код

int _tmain(int argc, _TCHAR* argv[])
{
  for (unsigned int i = 0; i < 0xFFFFFFFF; i++)
  {
    unsigned int N = i >> 1;
    unsigned int result;
    result = (((N >> 16) + 1) * 0x3333) & 0xFFFF0000;
    N = N - result * 5 + 1;
    N += N >> 16;
    result |= (N * 0x3333) >> 16;
    if (result != (i / 10))
    {
      printf("\nError: i = %X  i / 10 = %X result = %X\n",i , i / 10, result);
      break;
    }
    if ((i & 0xFFFF) == 0) printf("\r i = %X", i);
  }
    return 0;
}

Чёт не всё понимаю. Вроде бы поначалу борьба шла за малое количество используемых регистров. А сейчас за што бодаетесь?

Скорость при разумном количестве используемых регистров.
То есть по регистрам не хуже чем стандартное деление,
а по скорости намного выше.


теперь осталось деление на 100

для 100 разрядности все равно не хватает
то есть понятно что можно поделить на 4 потом на 5 и еще на 5
но это всего в 2,5раза лучше стандартного деления

есть идеи ?

[rezident]

есть идеи ?

Два раза последовательно поделить на 10?

[singlskv]

Два раза последовательно поделить на 10?

ну это я уже озвучил
делим на 4
потом на 5
потом еще на 5

итого 2,5 раза выигрыш
я же хочу получить как минимум раз в 5

вот ukpyr для деления на 10 подсказал гениальную идею сначала поделить на 2,
я так зациклился на просто делении на 10 с помощью умножения на 2^n /10
что этот очевидный факт(поделить сначала на 2) просто упустил из виду
и там в итоге разрядности всех умножений (WORD * DWORD) хватило для реализации

вот для деления на 100 нужна какая-нить похожая фишка,
т.е. каким-нить простым действом душим до 24бит делимого
ну а потом дело техники...


да, еще поясню,
для реализации подобных алгоритмов на AVR у нас есть по максимуму
умножение DWORD на WORD с получением результата в DWORD(младшая DWORD часть результата)
ну и в крайнем случае умножение DWORD * DWORD с получением результата в DWORD(младшая DWORD часть результата)

как-то так...

[singlskv]

По-моему ты хочешь невозможного.

Я надеюсь что теперь чуть более понятно,
что я хочу == я это получаю...
ну не сразу, иногда и думать приходицо

[Tiro]

Теперь чуть-чуть понятно. Вам сюда

[singlskv]

на 100 делить так:

Код

  for (unsigned int i = 0; i < 0xFFFFFFFF; i++)
  {
    unsigned int N = i >> 2;
    unsigned int result;
    unsigned short tmp;

    result = ((((N >> 16) + 1) * 0xA3D7) >> 4) & 0xFFFF0000;
    N -= result * 25U;
    tmp = ((((N >> 8) + 1) * 0xA3D7) >> 12) & 0xFF00;
    N = N - tmp * 25U + 1;
    result |= tmp;
    result |= (N * 0xA3D7) >> 20;

    if (result != (i / 100))
    {
      printf("\nError: i = %X  i / 100 = %X result = %X\n",i , i / 100, result);
      break;
    }
    if ((i & 0xFFFF) == 0) printf("\r i = %X", i);
  }

это тест для VC

для IAR увы все плохо...
IAR совсем не умеет "правильно"
двигать на 4 разряда
ну и на 20 разрядов он двигает так же...
учитывая что в AVR есть команда обмена ниблами...