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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 03.03.2010, 19:48
aleks2

 
Сообщений: n/a

Алгоритм целочисленного деления
Быстрое целочисленное деление беззнакового_64_битного_Цел го на беззнаковое_32_битное_Целое
!!!используя ТОЛЬКО инструкции 32-битного целочисленного деления.
=======================
Постановка:

есть произвольные

a) беззнаковое_64_битное_целое I
б) беззнаковое_32_битное_целое J

Ограничение: старшие 32 бита I образуют целое МЕНЬШЕЕ J.

надо найти [I/J].

ВНИМАНИЕ!!! Использовать ТОЛЬКО 32-битные операции. Доступ к 32-битным половинкам I имеется.
============================
Решение (как я придумал):

Итак: I=(2^32)*X+Y, где 0<=X<J, 0<=Y,J<(2^32)

1. Представляем (2^32) так

(2^32)=((2^32)-1)+1

представляем
((2^32)-1) = n*J+r, где n=[((2^32)-1)/J], r=((2^32)-1)-J*n

n и r можно вычислить 32-битным целочисленным делением.

Окончательно
(2^32)=n*J+r+1 (1)

2. Используя (1)

I=(2^32)*X+Y=(n*J+r+1)*X+Y=n*J*X+(r+1)*X+Y

[I/J]=[(n*J*X+(r+1)*X+Y)/J]=n*X+[((r+1)*X+Y)/J]

Определяя:

(r+1)*X=k*J+l, где k=[((r+1)*X)/J], l=((r+1)*X)-J*k
и
Y=i*J+j, где i=[Y/J], j=Y-J*i

k,l и i,j можно вычислить 32-битным целочисленным делением.

3. Окончательно

[I/J]=
=[(n*J*X+(r+1)*X+Y)/J]=
=n*X+[(k*J+l+i*J+j)/J]=
=n*X+k+i+[(l+j)/J]
=========================
ПРОБЛЕМА: не получается. Неверный результат в программе

[I/J]<>n*X+k+i+[(l+j)/J]

МОЖЕТ Я ЧЕГО УПУСТИЛ?
  #2  
Старый 03.03.2010, 22:46
_persicum_

 
Сообщений: n/a

Че за фигня? Смотри, как нормальные пацаны такие задачки решают:

function div32(low64,high64,denum:Cardinal):Cardinal;
asm
div ecx
end;
  #3  
Старый 04.03.2010, 02:13
гость

 
Сообщений: n/a

А вот подели 128-битное целое на 64-битное, раз ты такой реальный пацан.
  #4  
Старый 04.03.2010, 07:03
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Такое должно быть в книге Уоррена "Алгоритмические трюки для программистов" (Warren Hacker's Delight)
  #5  
Старый 04.03.2010, 11:56
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
А вот подели 128-битное целое на 64-битное, раз ты такой реальный пацан.
Так для этого желательно уметь делить две цифры делимого на одну цифру делителя, но автор темы это запретил o:
  #6  
Старый 05.03.2010, 15:11
Пользователь

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

Делим число ( ( hi shl 32 ) or low ) на dv.
asm
mov edx,hi
mov eax,low
div dv
mov result,eax
  #7  
Старый 07.03.2010, 13:30
aleks2

 
Сообщений: n/a

Хе-хе... спасибо, канешно,
div ECX
ето круто.

Но я в курсе наличия на 32-битных процессорах операции деления 64-бит на 32 бита. На 64-битных процессорах - ишо проще...

Тут вопрос по АЛГОРИТМУ, не по реализации
  #8  
Старый 07.03.2010, 21:18
гость

 
Сообщений: n/a

а алгоритм простой - деление в столбик. в школе проходят знаешь ли.
  #9  
Старый 07.03.2010, 21:36
@persicum@

 
Сообщений: n/a

А правда, может тебе перейти к основанию 16бит?
Тогда для решения задачи тебе нужно будет поделить 4-х значное число на двухзначное, для предсказания очередной цифры частного используй деление 32бит на 16бит, т.е. получается стандартная задача длинного деления.
  #10  
Старый 08.03.2010, 14:38
aleks2

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
а алгоритм простой - деление в столбик. в школе проходят знаешь ли.
Не все так просто. Деление в столбик излишне медленно, в той задаче, которая описана. Ибо предполагает, что очередную цифру частного можно и не угадать, а это означает цикл со сложением.

PS. Лицам, не имеющим НИЧЕГО сказать по существу, предлагается молча пройти мимо.
 


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

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


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