Собственно сабжект
умножение на 429496730 и на 42949673 не предлагать,
не катит из-за нехватки регистров на нормальную реализацию... и память тю-тю...
Полная версия этой страницы: unsigned long поделить на 10 и на 100
Циклическим вычитанием десятков и сотен.
На всякий случай поясняю.
Нужно найти значение X/10.
Пусть X/10=Y
X-X/10*10=0 тождество верное, не так ли?
Тогда X-Y*10=0
Вычитаем в цикле число 10 из значения X до тех пор, пока разность не будет меньшеили равно нулю десяти. Считаем количество вычитаний. Значение счетчика вычитаний это Y.
Возвращаясь назад Y=X/10, что и требовалось получить.
Update. Исправил алгоритмическую ошибку в описании. Вычитать нужно пока остаток разности больше основания (10, 100 ...), а не нуля.
На всякий случай поясняю.
Нужно найти значение X/10.
Пусть X/10=Y
X-X/10*10=0 тождество верное, не так ли?
Тогда X-Y*10=0
Вычитаем в цикле число 10 из значения X до тех пор, пока разность не будет меньше
Возвращаясь назад Y=X/10, что и требовалось получить.
Update. Исправил алгоритмическую ошибку в описании. Вычитать нужно пока остаток разности больше основания (10, 100 ...), а не нуля.
Лучше через вычитания деление выполнять не последовательным вычитанием делителя, а вычитанием убывающих степеней делителя.
Например, 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)
Например, 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)
BCD ?
А на чем пишем? На С, на асме?
Еще один способ, может пригодится.... Не деление в прямом смысле слова, но результат дает.
Ковертируем делимое в строку: 2949673 -> "2949673". Наверняка такая функция уже есть готовая..
Для деления на 10 достаточно "откусить" от строки один знак справа, получим "294967".
На 100 - откусываем 2 знака - "29496".
Конвертируем полученную строку в число - тоже стандартная и не слишком затратная процедура.
Для оптимизации откусывание можно объединить с конвертированием. Оно ведь всегда справа начинается.
Родственные алгоритмы применяются в кассовых аппаратах, т.к. там никто никогда плавающую точку и прочие "долгоиграющие" алгоритмы не реализовывает. И все основано на подобных "хитростях".
По сути - двигаем десятичную точку вправо или влево.
Еще один способ, может пригодится.... Не деление в прямом смысле слова, но результат дает.
Ковертируем делимое в строку: 2949673 -> "2949673". Наверняка такая функция уже есть готовая..
Для деления на 10 достаточно "откусить" от строки один знак справа, получим "294967".
На 100 - откусываем 2 знака - "29496".
Конвертируем полученную строку в число - тоже стандартная и не слишком затратная процедура.
Для оптимизации откусывание можно объединить с конвертированием. Оно ведь всегда справа начинается.
Родственные алгоритмы применяются в кассовых аппаратах, т.к. там никто никогда плавающую точку и прочие "долгоиграющие" алгоритмы не реализовывает. И все основано на подобных "хитростях".
По сути - двигаем десятичную точку вправо или влево.
Цитата(hd44780 @ Apr 26 2011, 10:55) 
Ковертируем делимое в строку: 2949673 -> "2949673". Наверняка такая функция уже есть готовая..
Обычно, такие функции требуют значительных ресурсов... Лучше тогда - BCD, как предложил _demЦитата(singlskv @ Apr 25 2011, 21:14)
не катит из-за нехватки регистров на нормальную реализацию... и память тю-тю
Сколько регистров есть в наличии? Если делитель состоит из одного байта, то должно хватить трёх регистров. Если к тому же делитель константа, то хватит двух регистров.
Цитата(=GM= @ Apr 26 2011, 12:53)
Сколько регистров есть в наличии? Если делитель состоит из одного байта, то должно хватить трёх регистров. Если к тому же делитель константа, то хватит двух регистров.
для деления unsigned long на 10 или 100 ?
суть здесь вот в чем есть стандартное деление на С которое
получает на вход 2 четырех байтовых числа и возвращает назад 4x байтовое
внутри функции деления используется еще 5 рабочих регистров
все бы хорошо, но эта функция работает не очень быстро,
ну примерно тактов 600
мне же нужно поделить только на 2 однобайтовые константы 10 и 100
стандартный в таких случаях путь домножения на 2^N / 10 не очень подходит
т.к. это предполагает умножение 2х четырех байтовых с получением восмибайтового и взятием от него старшей части
но IAR такое умножение выносит в библиотечную функцию как умножение 8байт на 8байт
и вот тут никаких регистров уже не хватает
собственно и хочется каких-нить идей как это сделать используя не больше регистров
чем использует стандартное деление и при этом что бы работало быстрее чем стандартное деление
и не использовать память
и еще что бы это было на С ...
Цитата(singlskv @ Apr 26 2011, 14:14)
и еще что бы это было на С ...
По-моему ты хочешь невозможного.
Компилятор С использует свои готовые функции для этого. Причем у каждого компилятора свои.
И он не позволит тебе их менять.
Если они тебя не устраивают, пиши свои на асме(!) и вызывай их как обычные функции.
Но будет ли это эффективнее и оптимальнее родных - фиг знает.
Но надо сперва найти какой-то алгоритм самого деления. А эти алгортимы, если мне память не изменяет, стандартны.
Например, - http://www.distedu.ru/mirror/_inform/dmivi...inform/div.html
Дальше вопрос уже в реализации этих алгоритмов.
Но ты делишь на 10 и 100, а это не степени двойки. Значит, довольствоваться общим алгоритмом.
хм, почешу-ка репу...
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
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
Цитата(ukpyr @ Apr 26 2011, 16:07)
хм, почешу-ка репу...
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
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
Цитата(singlskv @ Apr 26 2011, 10:14)
для деления unsigned long на 10 или 100?
Если надо делить на любую константу меньшую 256, то достаточно двух регистров, если писать на ассемблере. Скорее всего, можно и на си, просто не знаю, насколько экономно иар распоряжается регистрами.
Цитата(ukpyr @ Apr 26 2011, 16:07)
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
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;
DWORD result;
N >>= 1;
result = (((N >> 16) + 1) * 0x3333) & 0xFFFF0000;
result |= ((N - result * 5 + 1) * 0x3333) >> 16;
итого примерно 100 тактов против 600 у обычного деления.
Теперь нужно /100 , хотя конечно можно 2 раза поделить на 5...
желательно протестировать весь диапазон long int, мало ли что...
протестировал - ваш алгоритм дает кучу ошибок, начиная с 131080 (вместо 13108 получается 13107).
там после умножения на 0x3333 обязательно нужна коррекция - прибавить 0x3333
протестировал - ваш алгоритм дает кучу ошибок, начиная с 131080 (вместо 13108 получается 13107).
там после умножения на 0x3333 обязательно нужна коррекция - прибавить 0x3333
Цитата(ukpyr @ Apr 26 2011, 18:28)
желательно протестировать весь диапазон long int, мало ли что...
протестировал - ваш алгоритм дает кучу ошибок, начиная с 131080 (вместо 13108 получается 13107).
там после умножения на 0x3333 обязательно нужна коррекция - прибавить 0x3333
протестировал - ваш алгоритм дает кучу ошибок, начиная с 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;
DWORD result;
N >>= 1;
result = (((N >> 16) + 1) * 0x3333) & 0xFFFF0000;
N = N - result * 5 + 1;
N += N >> 16; // коррекция для диапазона 0x10000 - 0x50000
result |= (N * 0x3333) >> 16;
Чёт не всё понимаю. Вроде бы поначалу борьба шла за малое количество используемых регистров. А сейчас за што бодаетесь?
да, теперь все четко, вот код теста на VC:
Скорость при разумном количестве используемых регистров.
То есть по регистрам не хуже чем стандартное деление,
а по скорости намного выше.
теперь осталось деление на 100
для 100 разрядности все равно не хватает
то есть понятно что можно поделить на 4 потом на 5 и еще на 5
но это всего в 2,5раза лучше стандартного деления
есть идеи ?
Код
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;
}
{
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;
}
Цитата(=GM= @ Apr 26 2011, 19:37)
Чёт не всё понимаю. Вроде бы поначалу борьба шла за малое количество используемых регистров. А сейчас за што бодаетесь?
Скорость при разумном количестве используемых регистров.
То есть по регистрам не хуже чем стандартное деление,
а по скорости намного выше.
теперь осталось деление на 100
для 100 разрядности все равно не хватает
то есть понятно что можно поделить на 4 потом на 5 и еще на 5
но это всего в 2,5раза лучше стандартного деления
есть идеи ?
Цитата(singlskv @ Apr 26 2011, 21:51)
есть идеи ?
Два раза последовательно поделить на 10? 
Цитата(rezident @ Apr 26 2011, 20:08)
Два раза последовательно поделить на 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 часть результата)
как-то так...
Цитата(hd44780 @ Apr 26 2011, 15:49)
По-моему ты хочешь невозможного.
Я надеюсь что теперь чуть более понятно,что я хочу == я это получаю...
ну не сразу, иногда и думать приходицо
Теперь чуть-чуть понятно. Вам сюда
на 100 делить так:
это тест для VC
для IAR увы
все плохо...
IAR совсем не умеет "правильно"
двигать на 4 разряда
ну и на 20 разрядов он двигает так же...
учитывая что в AVR есть команда обмена ниблами...
Код
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);
}
{
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 есть команда обмена ниблами...
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.