Деление длинного числа на короткое

Привет.



Есть очень длинное беззнаковое число длинной 240000 бит и более. Нужно поделить на беззнаковое число длинной 32 бита. Мне известно лобовое решение, но оно не устраивает меня по скорости. Есть ли какие-нибудь другие решения, с минимальным количеством команд div. Решение предполагается использовать на PIII.



Спасибо.

 

А может реализовать деление через умножение?

 

Посмотри здесь

http://www.priorartdatabase.com/IPCOM/000020404/

 

crypto



Можно по-подробнее об умножении. При замене делителя на множетель=2^32/делитель теряем точность.

 

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



То есть, команда деления заменяется на умножение и сдвиг.

 

Если производится деление 32 бита на 32 бита, то мы можем вычислить величину обратную к делителю и использовать её как множитель с последующим сдвигом. Длина множителя будет 32 бита и ошибка в результате будет только в последнем бите и это поправимо.



Если же производится деление 240000 бит на 32 бита, то длина соответствующего множителя будет 240000 бит иначе ошибка будет в 32 бите от "головы" числа. Или я не прав ?

 

Вот код, делающий деление длинного на короткое (сорри за Delphi):

Код (Text):

1. procedure DivideN1(var A:TLongNum;B:Cardinal;
2.            var Quotient:TLongNum;var Modulo:Cardinal);pascal;
3. asm
4.   push ebx
5.   push esi
6.   mov esi,A
7.   mov ecx,[esi]
8.   mov ebx,Quotient
9.   mov [ebx],ecx
10.   xor edx,edx
11.   @Divide:
12.   mov eax,[esi+ecx*4]
13.   div dword ptr B
14.   mov [ebx+ecx*4],eax
15.   dec ecx
16.   jnz @Divide
17.   mov eax,Modulo
18.   mov [eax],edx
19.   mov ecx,[ebx]
20.   cmp [ebx+ecx*4],1
21.   sbb ecx,0
22.   mov [ebx],ecx
23.   pop esi
24.   pop ebx
25. end;

В цикле нужное количество раз 64 бита делятся на 32 командой DIV. Так что задача сводится к замене деления 64:32 на соответствующее умножение и сдвиг.

 

[deleted]..[/deleted]

PS: Здесь был глюк связанный с переполнением Надеюсь никто не заметил )

 

У меня есть вот такой вариант решения. Глючит по страшному, да и написан криво. Может кто-нибудь подскажет решение ?





В Ebx адрес данных для деления, туда же возвращаем частное

D делитель

M число обратное делителю

N длина массива



Mov Edx,1

Xor Eax,Eax

Div D

Mov M,Eax

Mov Ecx,N

Xor Edx,Edx

@L:Mov Eax,Edx

Mul M

Mov Edi,Eax

Mov Eax,[Ebx]

Mov Esi,Eax

Mul M

Add Edx,Edi

Mov [Ebx],Edx

Mov Eax,Edx

Mul D

Sub Esi,Eax

Cmp Esi,D

Jng @J

Mov Eax,[Ebx]

Sub Esi,D

Add Eax,1

Mov [Ebx],Eax

@J:Mov Edx,Esi

Add Ebx,4

Sub Ecx,1

Jnz @L