Russian Qt Forum

Программирование => С/C++ => Тема начата: kuzulis от Февраль 17, 2011, 16:18



Название: [РЕШЕНО]Простой алгоритм деления целого на 1000.
Отправлено: kuzulis от Февраль 17, 2011, 16:18
Доброго времени суток.

Имею некую 6-ти байтную переменную (массив), в которой лежит значение времени в миллисекундах, прошедшего от 1970 года.
Значения в массиве хранятся так: байт с индексом 0 - самый старший, байт с индексом 5 - самый младший.

Нужно перевести это значение с секунды, т.е. поделить на 1000.

Но проблема в том, что компилятор (Borland C 3x) поддерживает целый тип максимум 4 байта!

Прочитал гуголь - но там все алгоритмы уж больно общие и сложноваты для первого вхождения (в основном для сверх больших чисел для криптографии).
Может быть, можно как-то поиметь частный случай? (Т.к. делить нужно только на одно конкретное число).
Я "всё" уже перепробовал, мыслей больше нет (чтобы было и просто и быстро).

Может кто внесет новых мыслишек как можно это реализовать? ;)
 


Название: Re: Простой алгоритм деления целого на 1000.
Отправлено: SimpleSunny от Февраль 17, 2011, 16:45
В целый тип (4 байта), без дополнительных оговорок, все равно не получится.
Сейчас 6 байт (48 разрядов), целочисленно поделить на 1000 (~1024) сдвинуть вправо на 10 разрядов.
Итого значащих будет 38 разряда, а 4 байта (32 разряда).


Название: Re: Простой алгоритм деления целого на 1000.
Отправлено: kuzulis от Февраль 17, 2011, 17:12
В целый тип (4 байта), без дополнительных оговорок, все равно не получится.
Сейчас 6 байт (48 разрядов), целочисленно поделить на 1000 (~1024) сдвинуть вправо на 10 разрядов.
Итого значащих будет 38 разряда, а 4 байта (32 разряда).
Да, это понятно. До 4х байт (0xFFFFFFFF) секунды с 1970 года будут еще набираться порядка ~100 лет ,
поэтому если поделить 6-ти байтные миллисекунды на 1000 то вполне влезаем в 4 байта.

Вот возникла идея сделать так:
Цитировать
сек = (мсек >> 9) * (512/1000);
При этом,
1. >> 9 эквивалентно целому делению на 512 , т.е. этот результат - целое число
2. результат 512/1000 можно всунуть в float/double.
3. результат СЕК = тоже сделать float/double
4. Но потом как-то нужно преобразовать вещественный CEK в целое число, отбросив всё после запятой.

При таком "раскладе" погрешность составит ~1 сек, что вполне меня устраивает.
Главная проблема в п.4 


Название: Re: Простой алгоритм деления целого на 1000.
Отправлено: SimpleSunny от Февраль 17, 2011, 17:50
Если не боитесь потери старших битов, можно тогда сделать проще:
int sec = (a[4] + 256 * (a[3] + 256 * (a[2] + 256 * (a[1] + 256 * a[0])))) / 1000;
sec *= 256;


Название: Re: Простой алгоритм деления целого на 1000.
Отправлено: Fat-Zer от Февраль 17, 2011, 17:53
//оффтоп
а может не думать о 2029-м и остановится на 4-х байтах ;D

//по делу
// подразумеваю, что всё дело происходит на x86
1) старшие 4 байта поставить в правильном порядке и поделить на 1000
2) посчитать остаток от этого
3) остаток сдвинуть на 16 влево и прибавить к младшим двум байтам в правельном порядке
4) поделить (3) на 1000
5) прибавить к результату (1)<<16
всё быстрее плавающей арифметики..
Код
C
unsigned time6le_2sec(char *buff)
{
unsigned h;
unsigned l=0;
unsigned sech;
unsigned secl;
 
(char*)(&h)[3]=buff[0];
(char*)(&h)[2]=buff[1];
(char*)(&h)[1]=buff[2];
(char*)(&h)[0]=buff[3];
sech = h / 1000;
l = (h % 1000) << 16 + buff[4] << 8 + buff[5];
secl = l / 1000;
return secl + sech << 16;
}
 
для систем с ЛЕ алгоритм будет проще, но другой...

ЗЫ: это какой-то драйвер файловой системы?

Если не боитесь потери старших битов, можно тогда сделать проще:
int sec = (a[4] + 256 * (a[3] + 256 * (a[2] + 256 * (a[1] + 256 * a[0])))) / 1000;
sec *= 256;
выходите за разрядную сетку раньше, чем начинаете делить...


Название: Re: Простой алгоритм деления целого на 1000.
Отправлено: GreatSnake от Февраль 17, 2011, 17:57
Цитировать
Да, это понятно. До 4х байт (0xFFFFFFFF) секунды с 1970 года будут еще набираться порядка ~100 лет ,
С чего это вы взяли? Вообще-то до 19.01.2038 (http://en.wikipedia.org/wiki/Year_2038_problem).


Название: Re: Простой алгоритм деления целого на 1000.
Отправлено: Fat-Zer от Февраль 17, 2011, 18:03
Цитировать
Да, это понятно. До 4х байт (0xFFFFFFFF) секунды с 1970 года будут еще набираться порядка ~100 лет ,
С чего это вы взяли? Вообще-то до 19.01.2038 (http://en.wikipedia.org/wiki/Year_2038_problem).
да... чего-то меня заклинило. В 2029-м будет какой-то другой конец света...


Название: Re: Простой алгоритм деления целого на 1000.
Отправлено: SimpleSunny от Февраль 17, 2011, 18:24
выходите за разрядную сетку раньше, чем начинаете делить...

Да, ошибся. Можно деление внести в скобки. (:


Название: Re: Простой алгоритм деления целого на 1000.
Отправлено: Кутенок от Февраль 17, 2011, 18:45
Вот возникла идея сделать так:
сек = (мсек >> 9) * (512/1000);
При этом,
1. >> 9 эквивалентно целому делению на 512 , т.е. этот результат - целое число
2. результат 512/1000 можно всунуть в float/double.
3. результат СЕК = тоже сделать float/double
4. Но потом как-то нужно преобразовать вещественный CEK в целое число, отбросив всё после запятой.

При таком "раскладе" погрешность составит ~1 сек, что вполне меня устраивает.
Главная проблема в п.4  


А что такого в п.4? Чем тебя int(CЕК) не устраивает?


Название: Re: Простой алгоритм деления целого на 1000.
Отправлено: GreatSnake от Февраль 17, 2011, 18:50
Цитировать
Но потом как-то нужно преобразовать вещественный CEK в целое число, отбросив всё после запятой.
double modf(double x, double *iptr) :)


Название: Re: Простой алгоритм деления целого на 1000.
Отправлено: Fat-Zer от Февраль 17, 2011, 19:03
выходите за разрядную сетку раньше, чем начинаете делить...

Да, ошибся. Можно деление внести в скобки. (:
погрешность большая набежит


Название: Re: Простой алгоритм деления целого на 1000.
Отправлено: brankovic от Февраль 18, 2011, 00:13
почему тогда сразу не посчитать во флоатах? В смысле зачем сдвиги, 512 / 1000 и т.д.?

Код
C++ (Qt)
unsigned char buf [6];
 
double r = 0;
for (int i = 0; i < 6; ++i)
 r = r  * 256 + buf [i];
 
std::cout << (unsigned) (r / 1000) << std::endl;
 



Название: Re: Простой алгоритм деления целого на 1000.
Отправлено: kuzulis от Февраль 18, 2011, 10:32
Цитата: brankovic
почему тогда сразу не посчитать во флоатах? В смысле зачем сдвиги, 512 / 1000 и т.д.?
Да, это всё работает, но медленно!
Я немного переделал под себя:
Код
C
void div_1000_abs_time(u8 *t)
{
   double sec = t[0];
   sec = (sec * 256) + t[1];
   sec = (sec * 256) + t[2];
   sec = (sec * 256) + t[3];
   sec = (sec * 256) + t[4];
   sec = (sec * 256) + t[5];
   sec /= 1000;
   u32 r = u32(sec);
   t[0] = 0x00;
   t[1] = 0x00;
   t[2] = r >> 24;
   t[3] = r >> 16;
   t[4] = r >> 8;
   t[5] = r;
}
 

Цитата: Fat-Zer
всё быстрее плавающей арифметики..
Да, я согласен, но это было бы хорошо, если б твой пример адекватно работал, т.е. он правильно дает результат при компиляции MinGW и неправильный при Borland C 3x.
(По крайней мере у меня)
Вот немного измененный твой пример:
Код
C
void div_1000_abs_time2(u8 *t)
{
   u32 h;
   ((u8 *)(&h))[3] = t[0];
   ((u8 *)(&h))[2] = t[1];
   ((u8 *)(&h))[1] = t[2];
   ((u8 *)(&h))[0] = t[3];
 
   u32 sech = h / 1000;
   u32 secl = (h % 1000);
   secl <<= 16;
   secl += (t[4] << 8) + t[5];
   secl /= 1000;
   secl += (sech << 16);
 
   t[0] = 0x00;
   t[1] = 0x00;
   t[2] = secl >> 24;
   t[3] = secl >> 16;
   t[4] = secl >> 8;
   t[5] = secl;
}
 

Например, при делении числа:
Цитировать
0x 01  2d  e7  7d  84  d8
на 1000,
правильный результат должен быть:
Цитировать
0x 00  00  4d  49  98  f7
но оно в борланде даёт:
Цитировать
0x  00  00  4d  49  98  b5
Т.е. почему-то гдето что-то теряет.

ЗЫ: типы данных u8, u16, u32 это:
Код
C
typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned long u32;
 

Эх, а так хочется воспользоваться (и проверить на скорость) вариантом Fat-Zer


Название: Re: Простой алгоритм деления целого на 1000.
Отправлено: brankovic от Февраль 18, 2011, 11:34
Да, это всё работает, но медленно!
...
Эх, а так хочется воспользоваться (и проверить на скорость) вариантом Fat-Zer

попробуйте ещё столбиком поделить:

Код
C++ (Qt)
unsigned d1000 (unsigned char *buf)
{
  unsigned result = 0, carry = 0, d = 1000, char_bit = 8;
  for (int i = 0; i < 6; ++i, carry <<= char_bit)
  {
     unsigned u = buf [i] + carry;
     result = (result << char_bit) + u / d;
     carry = u % d;
  }
 
  return result;
}
 


Название: Re: Простой алгоритм деления целого на 1000.
Отправлено: kuzulis от Февраль 18, 2011, 12:38
Цитата: brankovic
попробуйте ещё столбиком поделить:

Вот, это уже дело! Спасибо! :)
Работает в ~два раза быстрее чем с флоатами. А после того как я раскрыл цикл и немного подправил - стало работать еще быстрее:
Код
C
...
#include <limits.h>
...
...
void div_1000_abs_time3(u8 *t)
{
   enum { D = 1000 };
   u32 u = t[0];
   u32 result = (u / D);
   u32 carry = (u % D) << CHAR_BIT;
   u = t[1] + carry;
   result = (result << CHAR_BIT) + (u / D);
   carry = (u % D) << CHAR_BIT;
   u = t[2] + carry;
   result = (result << CHAR_BIT) + (u / D);
   carry = (u % D) << CHAR_BIT;
   u = t[3] + carry;
   result = (result << CHAR_BIT) + (u / D);
   carry = (u % D) << CHAR_BIT;
   u = t[4] + carry;
   result = (result << CHAR_BIT) + (u / D);
   carry = (u % D) << CHAR_BIT;
   u = t[5] + carry;
   result = (result << CHAR_BIT) + (u / D);
   t[0] = 0x00;
   t[1] = 0x00;
   t[2] = result >> 24;
   t[3] = result >> 16;
   t[4] = result >> 8;
   t[5] = result;
}
 

Оставлю скорее всего этот вариант. Благодарю. :)


Название: Re: [РЕШЕНО]Простой алгоритм деления целого на 1000.
Отправлено: Waryable от Февраль 18, 2011, 13:23
А почему вы сразу отмели такой вариант:
Код
C++ (Qt)
char MasVal[6];            
unsigned long long int MSecs = 0;    
memcpy(MSecs, MasVal, 6);
 
unsigned int Secs = MSecs / 1000;


Название: Re: [РЕШЕНО]Простой алгоритм деления целого на 1000.
Отправлено: kuzulis от Февраль 18, 2011, 13:38
А почему вы сразу отмели такой вариант:
Код
C++ (Qt)
char MasVal[6];            
unsigned long long int MSecs = 0;    
memcpy(MSecs, MasVal, 6);
 
unsigned int Secs = MSecs / 1000;

А вы первый пост в теме читали?
Ну не поддерживает компилятор long long!
Код
C
...
printf("Size: %d", sizeof(long long));
 

Цитировать
...
Size: 4
...


Название: Re: [РЕШЕНО]Простой алгоритм деления целого на 1000.
Отправлено: brankovic от Февраль 18, 2011, 14:20
Ну не поддерживает компилятор long long!

Вообще сам факт использования Borland C довольно забавен, особенно имея в подписи arch linux amd64 / win 7 :)

2 Waryable: неправильно сработает memcopy на little-endian архитектурах (x86, amd64), у него big-endian порядок байт

вообще если скорость интересует, то надо не цикл разворачивать, а уменьшить число делений:

Код
C++ (Qt)
unsigned high = (buf [0] << 24) | (buf [1] << 16) | (buf [2] << 8) | buf [3];
unsigned low = (buf [4] << 8) | buf [5];
unsigned result = high / 1000 + ((high % 1000) << 16 + low) / 1000;
 


Название: Re: [РЕШЕНО]Простой алгоритм деления целого на 1000.
Отправлено: kuzulis от Февраль 18, 2011, 15:22
Цитата: brankovic
Вообще сам факт использования Borland C довольно забавен, особенно имея в подписи arch linux amd64 / win 7 :)
Ну просто есть железяка с процом 80188 и у неё на борту ROM DOS , вот надо это дело запрограммировать. :)

Цитата: brankovic
вообще если скорость интересует, то надо не цикл разворачивать, а уменьшить число делений:
Не работает этот код.

Кстати, код Fat-Zer-а (см. Ответ #12 ) все-таки работает, если использовать маску 0x0000FFFF:
Код
C
...
secl += ((t[4] << 8) + t[5]) & 0x0000FFFF;
...
 
Это причуды компилятора Borland C 3x  - он заполняет в этом случае старшие байты значением 0xFFFFxxxx  а не нулями


Название: Re: [РЕШЕНО]Простой алгоритм деления целого на 1000.
Отправлено: Fat-Zer от Февраль 18, 2011, 17:08
Ну просто есть железяка с процом 80188 и у неё на борту ROM DOS , вот надо это дело запрограммировать. :)
на такой железяке мой код скорей всего не пойдёт или будет работать медленно... я расчитывал, что есть 32-х битные регистры.

Цитата: kuzulis link=topic=16825.msg112573#msg112573
Цитата: brankovic
вообще если скорость интересует, то надо не цикл разворачивать, а уменьшить число делений:
Не работает этот код.

Кстати, код Fat-Zer-а (см. Ответ #12 ) все-таки работает, если использовать маску 0x0000FFFF:
Код
C
...
secl += ((t[4] << 8) + t[5]) & 0x0000FFFF;
...
 
Это причуды компилятора Borland C 3x  - он заполняет в этом случае старшие байты значением 0xFFFFxxxx  а не нулями
brankovic, тоже самое что у меня) хотя через | может и быстрей будет..


Название: Re: [РЕШЕНО]Простой алгоритм деления целого на 1000.
Отправлено: brankovic от Февраль 18, 2011, 18:34
Цитата: brankovic
вообще если скорость интересует, то надо не цикл разворачивать, а уменьшить число делений:
Не работает этот код.

скобочки забыл вокруг <<

Код:
((high % 1000) << 16)

но вообще 80188 там разве 4х-байтовые есть умножения и деления? Даже если есть тормозить должны.

brankovic, тоже самое что у меня) хотя через | может и быстрей будет..

Судя по тому, что от анроллинга циклов что-то убыстряется, оптимизатор совсем плохой. Тогда да, | будет быстрее.


Название: Re: [РЕШЕНО]Простой алгоритм деления целого на 1000.
Отправлено: kuzulis от Февраль 18, 2011, 18:36
Цитата: Fat-Zer
на такой железяке мой код скорей всего не пойдёт или будет работать медленно... я расчитывал, что есть 32-х битные регистры.
Прекрасно твой код работает. Медленно или быстро - хз , но факт в том, что оно быстрее в два раза чем код с флоатами.

Цитата: Fat-Zer
тоже самое что у меня) хотя через | может и быстрей будет..
Вот тут неизвестно что будет быстрее, или
1.
Код
C
   u32 h;
   ((u8 *)(&h))[3] = t[0];
   ((u8 *)(&h))[2] = t[1];
   ((u8 *)(&h))[1] = t[2];
   ((u8 *)(&h))[0] = t[3];
 

или
2.
Код
C
unsigned high = (buf [0] << 24) | (buf [1] << 16) | (buf [2] << 8) | buf [3];
 

Но склоняюсь к тому, что п.1 будет быстрее, т.к не нужно сдвигать и выполнять ИЛИ.



Название: Re: [РЕШЕНО]Простой алгоритм деления целого на 1000.
Отправлено: GreatSnake от Февраль 18, 2011, 18:52
Цитировать
Прекрасно твой код работает. Медленно или быстро - хз , но факт в том, что оно быстрее в два раза чем код с флоатами.
Ну дык, i80188 - это ж 16-битный проц с 8-битной внешней шиной данных без FPU. Вся работа с float делается в режиме эмуляции)