Задачка для спинного мозга. Рубрика "А вам слабо?".

[min@y™]

Попросили "глянуть" за полчаса до конца рабочего дня.

Честно скажу - нахрапом ниасилил, до сих пор залипаю.
Но постановка задачи мне показалась интересной. Поэтому вываливаю в интернеты.
Разомните мозг, коллеги!

Задача: натыкать вот такую функцию:

function iDivMod(const X: DWORD; const Y: Byte; out Z: Byte): DWORD;
begin
  // Result <--- целая часть результата деления X на Y
  // Z  <--- остаток от деления X на Y
end;

или аналогичную на С++:

DWORD iDivMod(const DWORD X, const UCHAR Y, UCHAR* Z)
{
  // return <--- целая часть результата деления X на Y
  // *Z  <--- остаток от деления X на Y
}

Требования: максимальная скорость работы.

Ограничения:
1. память юзать по совести, она не резиновая.
2. операторы деления (div, mod, /, %), функции, ассемлер не использовать! ho-ho-ho!!!
3. использовать только типы Byte, Word, DWord, а также, если нужно, массивы этих типов.

Рекомендации:
1. приветствуется использование целочисленных операторов (+, -, *, ++, --)
и побитовых (not, and, or, xor, shl, shr, !, &, |, ^, <<, >>).
2. таблицы констант использовать в разумных пределах. для начала, разумными
будем считать 2 мегабайта памяти.

Условия прежние - нашедшему катер плачу гинею! (ставлю пиво)

З.Ы. Если вариантов нет, можем пересмотреть условия. Главная цель - деление 4-байтного на байт без использования операторов деления. Иначе задача не имеет смысла.

[ДралсяСошибками]

В чём подвох?

function iDivMod(X: DWORD; Y: Byte; out Z: Byte): DWORD;
begin
  Result := 0;
    while x >= y do
      begin
        x := x - y;
        Inc(Result);
      end;
  z := x;
end;

[min@y™]

А делением в столбик можно?

можно. только без деления.
использовать только типы Byte, Word, DWord.

[BDA]

http://www.cyberforum.ru/post5356777.html - если верно понял "Деление через умножение", то с помощью 1024 + 96 байт можно будет задать магические числа и сдвиги для всех возможных значений Y. Таким образом получится посчитать частное, а Остаток = Делимое - Частное * Делитель.

PS Не уверен в идее.И инт64 тоже понадобится.

[Аватар]

Кто тестировать будет?

function iDivMod(const X: DWORD; const Y: Byte; out Z: Byte): DWORD;
var r: Int64;
    p: ^Byte;
    i: Integer;
begin
  r:=X;
  p:=Addr(r);
  Inc(p,4);
  Result:=0;
  for i:=1 to 32 do begin
    r:=r shl 1;
    Result:=Result shl 1;
    if p^>=Y then begin
      Result:=Result or 1;
      p^:=p^-Y;
    end;
  end;
  z:=p^;
end;

использовать только типы Byte, Word, DWord.

Так не честно, int64 уже запилил

[BDA]

Аватар, запустил вот так:

var
  i: Integer;
  j: Byte;
  a: DWORD;
  res1, res2: DWORD;
  ost1, ost2: Byte;
begin
  Memo1.Clear;
  Memo1.Lines.BeginUpdate;
  for i := 0 to 1000 do
  begin
    a := random($FFFFFFFF);
    for j := 1 to 255 do
    begin
      res1 := a div j;
      ost1 := a mod j;
      res2 := iDivMod(a, j, ost2);
      if (res1 <> res2) or (ost1 <> ost2) then
        Memo1.Lines.Add(inttostr(a) + ' ' + inttostr(j) + ' = ' + inttostr(res1)
          + ' ' + inttostr(res2) + ' ' + inttostr(ost1) + ' ' + inttostr(ost2));
    end;
  end;
  Memo1.Lines.EndUpdate;
end;

Например:

X = 527292212
Y = 231
div = 2282650
idivmod = 2097664
mod = 62
idivmod = 52

Delphi XE6

[min@y™]

Так не честно, int64 уже запилил

это мой косяк, сорри.
Щас похаваю чоньть и погоняю.

Аимадара умырзын.

[Poma][a]

Бинарным поиском найти такое k, что x >= k*y.. Потом радоваться, не?

[min@y™]

Бинарным поиском найти такое k, что x >= k*y.. Потом радоваться, не?

Если алгоритмов будет несколько, можно будет устроить бенчмарк. Пиши, если интересно, проверю.

[Poma][a]

function iDivMod(const X: DWORD; const Y: DWord; var Z: DWord): DWORD;
var
	a, b, k : DWord;
begin

	a := 0;
	b := x+1;
	
	while b-a > 1 do begin
		k := (a+b) div 2;
		if k*y > x then 
			b := k
		else
			a := k
	end;

	iDivMod := a;
	z := x-a*y
  // Result <--- целая часть результата деления X на Y
  // Z  <--- остаток от деления X на Y
end;