Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Замена деления умножением по-другому / 25 сообщений из 27, страница 1 из 2
  1  все
19.08.2017, 11:13
    #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, 15:16
    #39507851
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Замена деления умножением по-другому
Можно поискать похожий материал у:
1) Генри Уоррен - Алгоритмические трюки для программистов.
2) Степанов - От математики...

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

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

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


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

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

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


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

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

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

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

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

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

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

Можно описать Result аналогично остатку, т.е. как еще один параметр.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.08.2017, 18:18
    #39507885
Aleksandr Sharahov
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Замена деления умножением по-другому
или как локальную переменную и вернуть ее значение по return
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.08.2017, 18:30
    #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:39
    #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:48
    #39507890
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Замена деления умножением по-другому
Круто. Значит метод точен. Мне это почему-то напомнило криптографию где есть операции
с экзотическим модулем например (mod 255).

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

Но дело не в этом, а в том что 'ширина' произведения уменьшена, правда, ценой таблицы.
Это новый алгоритм.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
19.08.2017, 18:59
    #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, 19:04
    #39507894
Aleksandr Sharahov
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Замена деления умножением по-другому
Delphi оптимизирует только деление на 2^k,
в остальных случаях использует честный div.

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

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

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

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

Лишь в 10.15 рассказывается, что для деления нацело
можно использовать мультипликативный обратный и как его найти.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.08.2017, 13:32
    #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, 14:12
    #39510902
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Замена деления умножением по-другому
Возникла мысль.

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

Таким образом мы избавились от деления по крайней мере в пунктах (2) и (3)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
26.08.2017, 15:02
    #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
| Ответить | Цитировать | Написать  
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Замена деления умножением по-другому / 25 сообщений из 27, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 413ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1340303]:
 0ms
get settings:
 5ms
get forum list:
 9ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 131ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 51ms
get tp. blocked users:
 1ms
others: 201ms
total:  413ms
x
x
Закрыть


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