Комментарии 8
> Для известного целого b найти такую пару целых M, B чтобы для всех целых a: 0 ≤ a < (1 << N ) выполнялось x = [a / b] = [a * B >> M], где [ ] – целая часть, а >> M это разделить a на 2 в степени M (и << умножить).
Вам надо идти преподом в какой-нибудь вуз.
Вам надо идти преподом в какой-нибудь вуз.
Здесь достаточно запутано изложено, студенты не поймут.
Простыми словами, автор хотел сказать, что если нельзя использовать числа с плавающей запятой (долго, дорого и т. п.), то нужно ввести числа с фиксированной запятой. Можно записать число, обратное делителю, с точностью до M-го знака после нуля (в двоичной системе) и работать как с целым. У автора M=19.
Это дает возможность «делить» умножая целые числа до 19 знаков — точными получатся только первые 19 цифр. Поэтому если больше 19 знаков, то точность падает.
Видимо, автор это понимает, и в конце привел информацию о том, что в x86 можно делить таким образом без потери точности — результат умножения 32-битных помещается в 64-битный регистр, результат будет в верхних 32-х.
В данном примере оптимальнее было бы M=16.
Кстати, прибавлять 1 к B не надо — нужно просто округлять результат в большую сторону.
Но все равно спасибо за изложение интересного метода. Во встраиваемой ВТ такое используется сплошь и рядом.
Простыми словами, автор хотел сказать, что если нельзя использовать числа с плавающей запятой (долго, дорого и т. п.), то нужно ввести числа с фиксированной запятой. Можно записать число, обратное делителю, с точностью до M-го знака после нуля (в двоичной системе) и работать как с целым. У автора M=19.
Это дает возможность «делить» умножая целые числа до 19 знаков — точными получатся только первые 19 цифр. Поэтому если больше 19 знаков, то точность падает.
Видимо, автор это понимает, и в конце привел информацию о том, что в x86 можно делить таким образом без потери точности — результат умножения 32-битных помещается в 64-битный регистр, результат будет в верхних 32-х.
В данном примере оптимальнее было бы M=16.
Кстати, прибавлять 1 к B не надо — нужно просто округлять результат в большую сторону.
Но все равно спасибо за изложение интересного метода. Во встраиваемой ВТ такое используется сплошь и рядом.
Вспомнился FORTH с его трёхоперандным «умноделением» N1 N2 N3 */
Это не только FORTH, даже в WinApi есть такая функция MulDiv
>выбираем N = (32 – 7) / 2 = 12
Откуда такая формула? В тексте её нет.
И вы, надеюсь, понимаете, что из всех этих выкладок следует, что функция divideBy127() будет правильно работать только для чисел 0 ≤ a < 2^12
В книге «Алгоритмические трюки для программистов» Генри Уоррена описано правильное решение этой задачи (и там всё не так просто).
Откуда такая формула? В тексте её нет.
И вы, надеюсь, понимаете, что из всех этих выкладок следует, что функция divideBy127() будет правильно работать только для чисел 0 ≤ a < 2^12
В книге «Алгоритмические трюки для программистов» Генри Уоррена описано правильное решение этой задачи (и там всё не так просто).
В примере число N выбирается такое, чтобы результат умножения помещался в 32-ух битный int в JVM те N + M <= 32 (тест крутится на числах из N бит). То что функция divideBy127 не будет работать на больших числах — верно. Но на JVM нет возможности достучатся до 64-ти битного результата умножения, более универсальный пример написать, к сожалению, нельзя. На C/C++ можно реализовать быстрое деление без усечения диапазона, но Gcc/MsVs умеет делать эту оптимизацию сам.
Отличия от Уоррена, в том, что там знаковое деление + учитываются особенности RISC набора команд, потому там алгоритм получился более сложным. Но для сделанных выше предположений, результаты работы алгоритмов — одинаковы. У меня не было цели описать самый общий случай, больше описать идею наглядно и понятно для школьника.
Отличия от Уоррена, в том, что там знаковое деление + учитываются особенности RISC набора команд, потому там алгоритм получился более сложным. Но для сделанных выше предположений, результаты работы алгоритмов — одинаковы. У меня не было цели описать самый общий случай, больше описать идею наглядно и понятно для школьника.
Давно пользуюсь такой онлайн-утилиткой
www.sxlist.com/cgi-bin/constdivmul.exe
она представляет деление на константу через умножение, но не такое ограниченное (a*B>>M), а совмещая сложение и сдвиги. Поэтому и точность там будет повыше.
www.sxlist.com/cgi-bin/constdivmul.exe
она представляет деление на константу через умножение, но не такое ограниченное (a*B>>M), а совмещая сложение и сдвиги. Поэтому и точность там будет повыше.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Быстрое целочисленное деление на константу