Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #21  
Старый 30.07.2010, 22:21
Новичок

Отправить личное сообщение для deosis Посмотреть профиль Найти все сообщения от deosis
 
Регистрация: 30.07.2010
Сообщений: 8

Алгоритм вычисления А/В
Надо поделить А на В, где А=Х*2^32+Y, 0<X<B<2^32,
Определим 2^32 = q2*B+r2, Y = qy*B+ry,
тогда A=X*(q2*B+r2)+qy*B+ry = B*(X*q2+qy)+X*r2+ry,
X<B, q2*B<2^32, поэтому выражение в скобках считается в 32-хразрядной системе.
Осталось посчитать (X*r2+ry)/B
Пусть L=min(X,r2) , H=max(X,r2), тогда
1)L - четное, Н < 2^31:делим L на 2, умножаем Н на 2.
если H>B, выносим L в частное и вычитаем B из Н.
2)L - четное, H >=2^31: 2*H = 2*(H-2^31)+2*2^31=2*(H-2^31)+q2*B+r2, выносим q2*L в частное(при умножении переполнения не будет), L делим на 2, H=2*(H-2^31)+r2
3)L - нечетное: вычитаем 1 из L
if(H>=(B-ry)){++4astnoe;ry=H-(B-ry);}
else ry+=H;
повторяем пока L*H>2^32
за 2 прохода цикла L уменьшается как минимум в 2 раза => нужно не более 64 проходов
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Подскажите алгоритм нахождения остатка от деления AsDf Криптография 5 23.04.2009 18:21
Вывести значение целочисленного выражения, заданного в виде строки S в delphi SergeyHelpMe Математические алгоритмы 5 12.06.2008 12:59