Экспертная система Delphi.int.ru

Сообщество программистов
Общение, помощь, обмен опытом

Логин:
Пароль:
Регистрация | Забыли пароль?

Delphi.int.ru Expert

Другие разделы портала

Переход к вопросу:

#   

Статистика за сегодня:  


Лучшие эксперты

DNK
I. DNK
Баллы: 5

Подробнее »



Вопрос # 1 568

/ вопрос открыт /

Приветствую, уважаемые эксперты!
Прошу Вашей помощи в таком вопросе: как вычислить a mod b для больших чисел? подскажите алгоритм какого-нибуть разложения, ато бычисления "влоб" невозможно из-за довольно быльших чисел. Заранее благодарен!

volonter Вопрос ожидает решения (принимаются ответы, доступен мини-форум)

Вопрос задал: 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.

Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.

Версия движка: 2.6+ (26.01.2011)
Текущее время: 21 августа 2017, 15:00
Выполнено за 0.15 сек.
Рейтинг@Mail.ru