ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Замена деления умножением по-другому
25 сообщений из 27, страница 1 из 2
  1  все
Замена деления умножением по-другому
    #39507809
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Все знают о замене целочисленного деления умножением с использованием обратного reciprocal.
Пробую найти в сети упоминание о замене деления умножения с помощью обратного modular multiplicative inverse.
И не находится. Киньте ссылочку, люди добрые :-)

Вот пример, ищу нечто похожее (для C-шников - все числа и сдвиги беззнаковые):
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
function ShaDivMod10(ADividend: cardinal; var ARest: cardinal): cardinal;
const
  Shift= 1;
  Inverse= $CCCCCCCD;
  ToIndex= 28;
  Stamp: array[0..15] of cardinal= ($00000000, $00000000, $00000001, $33333334,
                                    $33333334, $00000001, $66666667, $66666667,
                                    $66666667, $9999999A, $9999999A, $9999999A,
                                    $CCCCCCCD, $CCCCCCCD, $CCCCCCCD, $00000001);
  Rest: array[0..15] of cardinal= (0, 0, 10, 8, 8, 10, 6, 6, 6, 4, 4, 4, 2, 2, 2, 10);
var
  i: cardinal;
begin;
  Result:=ADividend shr Shift * Inverse;
  i:=Result shr ToIndex;
  Result:=Result - Stamp[i];
  ARest:=Rest[i] + ADividend and (1 shl Shift - 1);
  end;



Краткое описание здесь: http://guildalfa.ru/alsha/node/34
...
Рейтинг: 0 / 0
19.08.2017, 11:13
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507851
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Можно поискать похожий материал у:
1) Генри Уоррен - Алгоритмические трюки для программистов.
2) Степанов - От математики...

В обоих книгах есть масса технических хитростей в численных методах. Но будьте осторожны.
Часть этих методов дают приближенный результат. Например Уоррен приводит алгоритм деления
без "деления" который дает шум в младших разрядах частного.

Тоесть для бухгалтерского деления это может быть неприменимо.
...
Рейтинг: 0 / 0
19.08.2017, 15:16
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507852
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Спасибо, сейчас гляну Степанова.
У Уоррена точно не было.
...
Рейтинг: 0 / 0
19.08.2017, 15:23
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507862
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
У Степанова тоже нет. Но интересно излагает.
...
Рейтинг: 0 / 0
19.08.2017, 16:22
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507870
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Для тех кто хочет поучаствовать в разборе алгоритма.

Давайте переведем алгоритм из Паскале-Адо-подобного (о боже какая метафора) ЯП на язык математики.
Я не могу прочитать словами алгоритм в том виде как он записан. Ибо я не помню
как работает shr (что за хрень? Вроде сдвиг вправо? Вроде беззнаковый) и каков приоритет.
Каков приоритет операций здесь?
Код: sql
1.
ADividend shr Shift * Inverse


Сначала сдвиг? Или сначала произведение.

И развернем операции в 1 на строку. Так будет их проще обсуждать.
...
Рейтинг: 0 / 0
19.08.2017, 16:51
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507872
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonДля тех кто хочет поучаствовать в разборе алгоритма.

Давайте переведем алгоритм из Паскале-Адо-подобного (о боже какая метафора) ЯП на язык математики.
Я не могу прочитать словами алгоритм в том виде как он записан. Ибо я не помню
как работает shr (что за хрень? Вроде сдвиг вправо? Вроде беззнаковый) и каков приоритет.
Каков приоритет операций здесь?
Код: sql
1.
ADividend shr Shift * Inverse


Сначала сдвиг? Или сначала произведение.

И развернем операции в 1 на строку. Так будет их проще обсуждать.

shr - сдвиг вправо беззнаковый, shl - влево,
приоритет сдвигов такой же как у умножения,
значит, здесь операции выполняются слева направо, как написаны.
...
Рейтинг: 0 / 0
19.08.2017, 17:16
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507874
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Правильно ли я понимаю что эта функция делит делимое (dividend) на 10 и возвращает остаток в Rest?
...
Рейтинг: 0 / 0
19.08.2017, 17:30
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507876
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonПравильно ли я понимаю что эта функция делит делимое (dividend) на 10 и возвращает остаток в Rest?

Да, правильно.

Забыл добавить, у бинарного and приоритет такой же как у сдвигов и умножения.
...
Рейтинг: 0 / 0
19.08.2017, 17:32
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507878
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Эта функция делит делимое (dividend) на 10 и возвращает частное в Result, а остаток в Rest
...
Рейтинг: 0 / 0
19.08.2017, 17:36
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507879
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А как "извне" получить доступ к Result? Он не объявлен в декларативной части функции.
...
Рейтинг: 0 / 0
19.08.2017, 17:40
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507881
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonА как "извне" получить доступ к Result? Он не объявлен в декларативной части функции.

Это магия компилятора, результат функции возвращается в регистре eax.
Возвращаемый результат можно использовать в операторах присваивания и вычислениях, например:
Код: pascal
1.
2.
d:=ShaDivMod10(a, r);
e:=1+ShaDivMod10(a, r);
...
Рейтинг: 0 / 0
19.08.2017, 17:53
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507882
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov, я знаю про эту магию. Я спрашиваю как нам протестировать эту замечательную функцию.

Я считаю что TDD очень подходит для этой задачи.
...
Рейтинг: 0 / 0
19.08.2017, 17:59
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507883
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonAleksandr Sharahov, я знаю про эту магию. Я спрашиваю как нам протестировать эту замечательную функцию.

Я считаю что TDD очень подходит для этой задачи.

Можно описать Result аналогично остатку, т.е. как еще один параметр.
...
Рейтинг: 0 / 0
19.08.2017, 18:07
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507885
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
или как локальную переменную и вернуть ее значение по return
...
Рейтинг: 0 / 0
19.08.2017, 18:18
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507886
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahovили как локальную переменную и вернуть ее значение по return
Исходя из главного кейса использования (функция должна расчитывать остаток от деления на 10) я-бы
предложил оформить ее интерфейс так:

Код: pascal
1.
2.
3.
4.
5.
6.
7.
/**
 * ADividend - делимое
 * (делитель - всегда = 10)
 * AQuotiend - частное
 * ARest - возвращается как результат функции.
 */
function ShaDivMod10(ADividend: cardinal; var AQuotient: cardinal): cardinal;



Тогда будут справедливы следующие кейсы

Код: pascal
1.
2.
3.
4.
assertThat(MOD(2147483647,10) == function ShaDivMod10(2147483647, quotient));
assertThat(2147483647 / 10 == quotient);

..


И тест зациклить для большой выборки случайных чисел.

P.S. Я не знаю как этих Паскалях-Оберонах пишут тесты.
...
Рейтинг: 0 / 0
19.08.2017, 18:30
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507888
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Все три функции (ShaDivMod10, ShaDiv10, ShaMod10)
прошли полную проверку для всех возможных значений делимого 0..FFFFFFFF:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
procedure TForm1.Button11Click(Sender: TObject);
var
  a, b, c, d, b2, c2, e: cardinal;
label
  err1, err2;
begin;
  e:=0;
  d:=10;
  a:=0;
  repeat;
    b:=a div d;
    c:=a - b*d;

    b2:=ShaDivMod10(a, c2);
    if (b<>b2) or (c<>c2) then goto err1;

    b2:=ShaDiv10(a);
    c2:=ShaMod10(a);
    if (b<>b2) or (c<>c2) then goto err2;

    inc(a);
    until a=0;
  Memo1.Lines.Add('done');
  exit;

err2: inc(e);
err1: inc(e);
  Memo1.Lines.Add(Format('Error%d:  %d  %d  %d  %d  %d  %d',
    [e, int64(a), int64(b), int64(c), int64(d), int64(b2), int64(c2)]));
  end;
...
Рейтинг: 0 / 0
19.08.2017, 18:39
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507890
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Круто. Значит метод точен. Мне это почему-то напомнило криптографию где есть операции
с экзотическим модулем например (mod 255).

А есть бенчмарк который сравнивает скорость ShaDivMod10 и обычного mod ?
...
Рейтинг: 0 / 0
19.08.2017, 18:48
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507891
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Разумеется, обычные div и mod медленнее. Сильно зависит от процессора.

Но дело не в этом, а в том что 'ширина' произведения уменьшена, правда, ценой таблицы.
Это новый алгоритм.
...
Рейтинг: 0 / 0
19.08.2017, 18:53
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507893
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr SharahovРазумеется, обычные div и mod медленнее. Сильно зависит от процессора.

Но дело не в этом, а в том что 'ширина' произведения уменьшена, правда, ценой таблицы.
Это новый алгоритм.

А варианте с mod(...) Delphi генерит код с
Код: xml
1.
2.
3.
4.
mov ax,
mov bx,
mov cx,
div ...


?

Или как то по другому?
...
Рейтинг: 0 / 0
19.08.2017, 18:59
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507894
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Delphi оптимизирует только деление на 2^k,
в остальных случаях использует честный div.

Многие C-компиляторы могут оптимизировать деление
заменой на 'широкое' умножение.
...
Рейтинг: 0 / 0
19.08.2017, 19:04
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507898
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я думаю что Генри Уоррен все таки описывал ваш метод. Почитайте начиная с:
Глава 10 - Целое деление на константы

А также 10.9 Беззнаковое деление на делитель, не меньший 1.
10.14 (упоминание магических констант 66666667 и сдвигов для делителя 10).
...
Рейтинг: 0 / 0
19.08.2017, 19:22
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39507905
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
maytonЯ думаю что Генри Уоррен все таки описывал ваш метод. Почитайте начиная с:
Глава 10 - Целое деление на константы

А также 10.9 Беззнаковое деление на делитель, не меньший 1.
10.14 (упоминание магических констант 66666667 и сдвигов для делителя 10).

Нет, у него везде используется "традиционный" метод.

Лишь в 10.15 рассказывается, что для деления нацело
можно использовать мультипликативный обратный и как его найти.
...
Рейтинг: 0 / 0
19.08.2017, 20:06
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39510892
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Aleksandr SharahovmaytonЯ думаю что Генри Уоррен все таки описывал ваш метод. Почитайте начиная с:
Глава 10 - Целое деление на константы

А также 10.9 Беззнаковое деление на делитель, не меньший 1.
10.14 (упоминание магических констант 66666667 и сдвигов для делителя 10).

Нет, у него везде используется "традиционный" метод.

Лишь в 10.15 рассказывается, что для деления нацело
можно использовать мультипликативный обратный и как его найти.

На сайте книги Генри Уоррен дополнил главу 10 новым материалом http://www.hackersdelight.org/divcMore.pdf

В добавлении в пункте 10-20 Converting to Exact Division он снова упоминает multiplicative inverse:

авторSince the remainder can be computed without computing the quotient, the possibility
arises of computing the quotient by first computing the
remainder, subtracting this from the dividend n, and then dividing the difference
by the divisor d. This last division is an exact division, and it can be done by multiplying
by the multiplicative inverse of d (see Section 10–15 on page 190). This
method would be particularly attractive if both the quotient and remainder are
wanted.

И снова предлагает использовать его только для деления нацело (т.е. если остаток заранее известен или вычислен каким-то иным способом)
...
Рейтинг: 0 / 0
26.08.2017, 13:32
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39510902
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Возникла мысль.

1) Любое 32х разрядное целое можно факторизовать с небольшим количеством множителей.
2) Далее. Целочисленное деление сводится к сложениям и вычитаниям факторизованных делимого и делителя.
3) В конце - обратный перевод из факторизованной формы в 32х разрядное целое. Это только уножения и сложения.

Таким образом мы избавились от деления по крайней мере в пунктах (2) и (3)
...
Рейтинг: 0 / 0
26.08.2017, 14:12
| Ответить | Цитировать | Написать  
Замена деления умножением по-другому
    #39510918
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Еще есть метод о котором кажется писали Шикин и Боресков в Комп-графике.
Я не помню точно все шаги но попробую воспроизвести похожие
оптимизации по памяти.

Они описывали для 16/32bit но я попробую обобщить на 32/64.

Понимаю что это не формат топика но КМК это тоже можно рассмотреть.

Я не умею пользоватся Latex, поэтому прошу прощения за возможные очепятки.

Дано. Надо поделить A на B. При этом предполагается что A это переменная а B
константа в рамках решаемой функции. Деление целочисленное. Без использования
деления как такового в функции.

Я предполагаю что A больше B иначе результат целочисленного деления лишен смысла.

Я делаю следующие допущения.



Далее несколько тождеств.



Поскольку b=const, вводим магическое число Bm (множитель).


Мы его расчитываем один раз для машей функции.

Далее. Помня что деление-умножение на степени двойки - машинная операция сдвига
получаем следующую формулу. Она лишена деления явно.



Далее. Разрядная сетка. Мы не можем двигать а вправо без потери знаков. Поэтому
мы вводим fixpoint-арифметику формата 32:32. Тоесть числа А и B хранятся в 64х
битных регистрах. Но предварительно сдвигаются на 32 разряда влево. Shl(32,..)
Младшие-же разряды используются как дробные. Внешние арифметика остается
целочисленной. Дробность просто нами подразумевается. Магическое число в числителе
2^32 также предварительно сдвигается влево до упора.

Открытые вопросы:

1) Точность. Какая она? Надо исследовать.
2) Эмуляция 64х на 32х. Некоторое железо должно эмулировать умножение с переносом. Надо исследовать.
Со сдвигами все просто. Есть возможность двигать 32х разрядные с учотом переносов.
...
Рейтинг: 0 / 0
26.08.2017, 15:02
| Ответить | Цитировать | Написать  
25 сообщений из 27, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Замена деления умножением по-другому
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]