Алгоритм деления без восстановления

Код из #58 работает не во всех случаях - взял от балды dword [q] = dword [q+4] = 9ABCDEF0h, правильный остаток 0B5765398h, а код выдаёт 0B5865397h. Код из #57 не тестил.

 

А может я отбираю себе код на конкурсной основе =))) Мне сначала нужно посмотреть портфолио, типа как это быстро и круто в сравнении с другими претендентами.

 

Mikl___
советую подойти к решению задачи более творчески. пост 27 использовал естественное разбиение числа на 64 бит как a*2^32 + b, но можно также представить его как a*2^20 + b. Тогда для нахождения искомого остатка достаточно разделить a на FFF, тут пригодятся и остаточек и частное от этого деления, если так нравится делить по Уоррену.

 

Mikl___
Метод поста н27 будет хорош для числа FFF00001, но будет плох для числа C0000001. Советую изучить разнообразные трюки именно для взятия остатков.

 

Просто значения, взятые от балды, посчитались правильно; тогда взял edx:eax = FFF00001 * ABCDEFAB, прогнал - получил остаток FFF00001 вместо правильного 0. Добавил единицу, получил FFF00002. Добавил вместо единицы 100000h, код выдал остаток 1.

 

Mikl___
Код поста 67 просто замечательный, совсем другое дело!
Я пока не совсем понимаю как он работает, меня от использования шифтов отворачивала необходимость вычитать, но тут идет прибавление .
Однако, есть ряд недочетов.
1) может возвращать недобитый остаток, например (p-1)(p-1) выдает p+1
2) где гарантия, что невозможно переполнение в пределах допустимых значений множителей меньше p
3) переполнение можно вызвать явно умножив -1 на -1, однако это не является недостатком процедуры, поскольку -1 лежит вне диапазона
Это я говорю про процедуру дополренную вначале mul edx, поскольку мне нужно edx и eax вначале перемножить а уж потом брать остаток

 

в подтыерждение опасения 2) нашел пример, когда допустимые входные величины вызывают потерю значимости, а именно (p-1)(p-FFFFF) должно преспокойненько давать FFFFF, а получается угадайте что? Лажа...

 

MS тоже любит накладывать заплатки... как показывает практика, дыр от этого меньше не становится.
Отчётливо видна коррекция предыдущего решения. Снова взял edx:eax = FFF00001 * ABCDEFAB + 100000, снова получил остаток 1 вместо правильного 100000h.

 

Mikl___
Ну это просто звиндец! Клюв вынул - хвост увяз. Старые дыры ты залечил, не спорю, но попробуй теперь (p-1). А где гарантия, что и через десять постов оно будет абсолютно надежно? Теперь я понял, что значит деление без восстановления =))))))

 

Для примера 2) твой код выдает FFFFFFFF

 

Если цель всего этого - арифметика по модулю p и над числами производится много последовательных операций по модулю p, то можно воспользоваться трюком из статьи Монтгомери http://www2.itu.edu.tr/~orssi/dersler/cryptography/Montgomery.pdf : можно так кодировать вычеты по mod p, что операции сложения/вычитания устроены так же, как и при стандартном представлении, а умножение реализуется проще. При этом все константы и все входные данные нужно перекодировать (это некоторая перестановка на множестве вычетов), а все выходные данные - перекодировать обратно. Применительно к p = 0xFFF00001 три операции кодирования/умножения/декодирования выглядят так:

Код (Text):

1. start:
2.     mov eax, 0x12345678 ; первый множитель в стандартном представлении
3.     call    input2coded
4.     push    eax
5.     mov eax, 0x9ABCDEF0 ; второй множитель в стандартном представлении
6.     call    input2coded
7.     pop edx
8.     call    coded_mul
9.     call    coded2output
10. ; eax = residue
11.     ret
12.  
13. coded2output:
14. ; eax -> eax
15.     xor edx, edx
16.     jmp coded_mul_doit
17.  
18. input2coded:
19. ; eax -> eax
20.     mov edx, 0x0FDFFF01
21. coded_mul:
22. ; eax*edx -> eax
23.     mul edx
24. coded_mul_doit:
25.     mov esi, eax
26.     shl eax, 20
27.     add eax, esi
28.     xor esi, esi
29.     mov ebx, eax
30.     shld    esi, eax, 20
31.     shl ebx, 20
32.     mov edi, eax
33.     sub eax, ebx
34.     sbb edi, esi
35.     sub edx, edi
36.     sbb eax, eax
37.     and eax, 0xFFF00001
38.     add eax, edx
39.     ret

Если производится несколько операций по mod p подряд, то между этими операциями кодировать/декодировать ничего не нужно.

 

Про Монтгомери мысль была, но останавливают такие соображения
1) лень переводить числа в другой формат
2) грехх юзать универсальный метод с почти-Мерсеновским числом 2^32-2^20+1 !!!
3) код #27 работает на умножениях без деления, как и Монтгомери
4) murder , SSE2 ускоряет его в ТРИ раза !
5) я не верю, что в Монтгомери можно складывать без компенсации. Если обычным порядком у меня произошло переполнение при сложении то я отниму p и все дела.
А если у меня произойдет переполнение при сложении измененных данных, я разумеется не смогу взять просто младшие 32-бит, нужна такая же компинсация как и при умножении... Мне так кажется.

 

1) Код уже приведён.
2) Пока что не видно работающих алгоритмов, использующих специфику числа, а то, что есть, заметно длиннее кода из #78.
3) И использует цикл, а цикл - это ветвление, а ветвлений рекомендуется избегать.
4) Это говорит скорее о тормознутости исходного кода
5) Даже при обычном порядке если произошло переполнение при сложении, нужно это специально обрабатывать - нельзя просто взять младшие 32 бит (нужно ещё вычесть p). В методе Монтгомери всё точно так же.