Название: [РЕШЕНО]Простой алгоритм деления целого на 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 байта), без дополнительных оговорок, все равно не получится. Да, это понятно. До 4х байт (0xFFFFFFFF) секунды с 1970 года будут еще набираться порядка ~100 лет ,Сейчас 6 байт (48 разрядов), целочисленно поделить на 1000 (~1024) сдвинуть вправо на 10 разрядов. Итого значащих будет 38 разряда, а 4 байта (32 разряда). поэтому если поделить 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 всё быстрее плавающей арифметики.. Код для систем с ЛЕ алгоритм будет проще, но другой... ЗЫ: это какой-то драйвер файловой системы? Если не боитесь потери старших битов, можно тогда сделать проще: выходите за разрядную сетку раньше, чем начинаете делить...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).Название: 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 и т.д.?
Код
Название: Re: Простой алгоритм деления целого на 1000. Отправлено: kuzulis от Февраль 18, 2011, 10:32 Цитата: brankovic почему тогда сразу не посчитать во флоатах? В смысле зачем сдвиги, 512 / 1000 и т.д.? Да, это всё работает, но медленно!Я немного переделал под себя: Код
Цитата: Fat-Zer всё быстрее плавающей арифметики.. Да, я согласен, но это было бы хорошо, если б твой пример адекватно работал, т.е. он правильно дает результат при компиляции MinGW и неправильный при Borland C 3x.(По крайней мере у меня) Вот немного измененный твой пример: Код
Например, при делении числа: Цитировать 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 это: Код
Эх, а так хочется воспользоваться (и проверить на скорость) вариантом Fat-Zer-а Название: Re: Простой алгоритм деления целого на 1000. Отправлено: brankovic от Февраль 18, 2011, 11:34 Да, это всё работает, но медленно! ... Эх, а так хочется воспользоваться (и проверить на скорость) вариантом Fat-Zer-а попробуйте ещё столбиком поделить: Код
Название: Re: Простой алгоритм деления целого на 1000. Отправлено: kuzulis от Февраль 18, 2011, 12:38 Цитата: brankovic попробуйте ещё столбиком поделить: Вот, это уже дело! Спасибо! :) Работает в ~два раза быстрее чем с флоатами. А после того как я раскрыл цикл и немного подправил - стало работать еще быстрее: Код
Оставлю скорее всего этот вариант. Благодарю. :) Название: Re: [РЕШЕНО]Простой алгоритм деления целого на 1000. Отправлено: Waryable от Февраль 18, 2011, 13:23 А почему вы сразу отмели такой вариант:
Код
Название: Re: [РЕШЕНО]Простой алгоритм деления целого на 1000. Отправлено: kuzulis от Февраль 18, 2011, 13:38 А почему вы сразу отмели такой вариант: Код
А вы первый пост в теме читали? Ну не поддерживает компилятор 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 порядок байт вообще если скорость интересует, то надо не цикл разворачивать, а уменьшить число делений: Код
Название: Re: [РЕШЕНО]Простой алгоритм деления целого на 1000. Отправлено: kuzulis от Февраль 18, 2011, 15:22 Цитата: brankovic Вообще сам факт использования Borland C довольно забавен, особенно имея в подписи arch linux amd64 / win 7 :) Ну просто есть железяка с процом 80188 и у неё на борту ROM DOS , вот надо это дело запрограммировать. :)Цитата: brankovic вообще если скорость интересует, то надо не цикл разворачивать, а уменьшить число делений: Не работает этот код.Кстати, код Fat-Zer-а (см. Ответ #12 ) все-таки работает, если использовать маску 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: Код Это причуды компилятора Borland C 3x - он заполняет в этом случае старшие байты значением 0xFFFFxxxx а не нулями Название: 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. Код
или 2. Код
Но склоняюсь к тому, что п.1 будет быстрее, т.к не нужно сдвигать и выполнять ИЛИ. Название: Re: [РЕШЕНО]Простой алгоритм деления целого на 1000. Отправлено: GreatSnake от Февраль 18, 2011, 18:52 Цитировать Прекрасно твой код работает. Медленно или быстро - хз , но факт в том, что оно быстрее в два раза чем код с флоатами. Ну дык, i80188 - это ж 16-битный проц с 8-битной внешней шиной данных без FPU. Вся работа с float делается в режиме эмуляции) |