|
Вопрос # 1 568/ вопрос открыт / |
|
Приветствую, уважаемые эксперты!
Прошу Вашей помощи в таком вопросе: как вычислить a mod b для больших чисел? подскажите алгоритм какого-нибуть разложения, ато бычисления "влоб" невозможно из-за довольно быльших чисел. Заранее благодарен!
 |
Вопрос задал: volonter (статус: Посетитель)
Вопрос отправлен: 9 мая 2008, 01:45
Состояние вопроса: открыт, ответов: 1.
|
Ответ #1. Отвечает эксперт: Dron
Здравствуйте, volonter!
С точки зрения математики остаток от деления считается довольно просто: сначала делим наше число на делитель, дальше округляем результат деления в меньшую сторону (т.е. просто отбрасывается дробная часть). Далее полученное число умножаем на делитель - получаем результат операции div. Осталось только вычесть из исходного числа полученное - вот и остаток от деления.
Пример. 15 mod 4.
1) 15/4 = 3.75
2) Floor(3.75) = 3 (функция Floor находится в модуле Math)
3) 3 * 4 = 12
4) 15 - 12 = 3 (15 mod 4 = 3)
Конечно, всё зависит от того, с числами какого порядка вы работаете. Если, например, числа 30-го порядка, то реализовать вычисление остатка непросто. Хотя, если функции деления, умножения и вычитания у вас реализованы, то сложностей возникнуть не должно.
 |
Ответ отправил: Dron (статус: Студент)
Время отправки: 9 мая 2008, 08:01
Оценка за ответ: 4
Комментарий к оценке: это понятно, но меня больше интересовал алгоритм разложения, например на квадраты или что то типа этого. Но все равно большое спасибо, что откликнулись
|
Мини-форум вопроса
Всего сообщений: 1; последнее сообщение — 9 мая 2008, 09:21; участников в обсуждении: 1.
|
Матвеев Игорь Владимирович (статус: Студент), 9 мая 2008, 09:21 [#1]:
Сложность деления такая же, как и взятия остатка, если не больше, я уж не говорю про floating point.
Используя тип Int64 можно получать остаток от деления для чисел -2^63..2^63–1. В этом случае компилятор Delphi автоматически заменяет этот операнд на функцию __llmod - 64 битные числа на 32 битном оборудовании представляются в виде пары регистров EAX/EDX, эта функция берет остаток от деления такого числа.
Вот листинг этой функции:
procedure __llmod;
asm
push ebp
push ebx
push esi
push edi
xor edi,edi
//
// dividend is pushed last, therefore the first in the args
// divisor next.
//
mov ebx,20[esp] // get the first low word
mov ecx,24[esp] // get the first high word
or ecx,ecx
jnz @__llmod@slow_ldiv // both high words are zero
or edx,edx
jz @__llmod@quick_ldiv
or ebx,ebx
jz @__llmod@quick_ldiv // if ecx:ebx == 0 force a zero divide
// we don't expect this to actually
// work
@__llmod@slow_ldiv:
//
// Signed division should be done. Convert negative
// values to positive and do an unsigned division.
// Store the sign value in the next higher bit of
// di (test mask of 4). Thus when we are done, testing
// that bit will determine the sign of the result.
//
or edx,edx // test sign of dividend
jns @__llmod@onepos
neg edx
neg eax
sbb edx,0 // negate dividend
or edi,1
@__llmod@onepos:
or ecx,ecx // test sign of divisor
jns @__llmod@positive
neg ecx
neg ebx
sbb ecx,0 // negate divisor
@__llmod@positive:
mov ebp,ecx
mov ecx,64 // shift counter
push edi // save the flags
//
// Now the stack looks something like this:
//
// 24[esp]: divisor (high dword)
// 20[esp]: divisor (low dword)
// 16[esp]: return EIP
// 12[esp]: previous EBP
// 8[esp]: previous EBX
// 4[esp]: previous ESI
// [esp]: previous EDI
//
xor edi,edi // fake a 64 bit dividend
xor esi,esi
@__llmod@xloop:
shl eax,1 // shift dividend left one bit
rcl edx,1
rcl esi,1
rcl edi,1
cmp edi,ebp // dividend larger?
jb @__llmod@nosub
ja @__llmod@subtract
cmp esi,ebx // maybe
jb @__llmod@nosub
@__llmod@subtract:
sub esi,ebx
sbb edi,ebp // subtract the divisor
inc eax // build quotient
@__llmod@nosub:
loop @__llmod@xloop
//
// When done with the loop the four registers values' look like:
//
// | edi | esi | edx | eax |
// | remainder | quotient |
//
mov eax,esi
mov edx,edi // use remainder
pop ebx // get control bits
test ebx,1 // needs negative
jz @__llmod@finish
neg edx
neg eax
sbb edx,0 // negate
@__llmod@finish:
pop edi
pop esi
pop ebx
pop ebp
ret 8
@__llmod@quick_ldiv:
div ebx // unsigned divide
xchg eax,edx
xor edx,edx
jmp @__llmod@finish
end;
Если найдется достаточно терпения, можно разобраться в алгоритме (в коде много комментариев) и придумать алгоритм последовательного вычисления остатка для неограниченно больших чисел.
Можно также обратиться на algolist.ru.
|
Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.
|
