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

[Аватар]

Сообщение от BDA

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

Исправил

function iDivMod(const X: DWORD; const Y: Byte; out Z: Byte): DWORD;
var r: Int64;
    p: ^Word;
    i: Integer;
begin
  r:=X;
  p:=Addr(r);
  Inc(p,2);
  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;

[min@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;

Тестировал, не?
"div 2" юзать нельзя по условию задачи.
замени на "shr 1".

if k*y > x then

а если произведение вылезет за 32 бита?

[Poma][a]

Проморгал, данке

Тестировал, не?

Было дело.. тыц

[f.hump]

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

    DWORD mumu[4] = {X, Y, 0, 0};

    for (;mumu[0];mumu[0]>>=1) mumu[2]++;
    for (;mumu[1];mumu[1]>>=1) mumu[2]--;

    mumu[0] = X;
    mumu[1] = Y;
    mumu[1] <<= mumu[2];

    for (;mumu[2];mumu[2]--, mumu[1]>>=1) {
        if (mumu[0] >= mumu[1]) {
            mumu[0] -= mumu[1];
            mumu[3] |= (1<<mumu[2]);
        }

    }

    Z = mumu[0];
    return mumu[3];
}

как-то так

[min@y™]

Пасибо всем участникам. Написал я демо и потестил ваши алгоритмы. Результаты, прямо скажем, неоднозначные (особенно на границах диапазона)
Думаю, скриншот скажет больше 1000 слов.



И ещё по каждому из ваших алгоритмов у меня один и тот же вопрос: "как я буду объяснять всё это бабульке?". Бабулька должна перевести один из алгоритмов на ассемблер от дико урезанного контроллера (нету там логики и команд деления).
Короче, надо комменты и/или БСА.

Значения > 0x7FFFFFFF не подставлял пока, но требуется работа именно с беззнаковыми 4-байтными целыми. Надо будет допилить.

Приму в дар ещё варианты решения в неограниченном количестве, желательно, отлаженные для всех значений в диапазоне 0..0xFFFFFFFF. Хочу сделать бенчмарк по скорости работы.

[min@y™]

сорри, исходник + ехе забыл прицепить. поиграйтесь.

[Аватар]

Бабулька должна перевести один из алгоритмов на ассемблер от дико урезанного контроллера (нету там логики и команд деления).

У меня двоичное деление в столбик и только для интеловского порядка байтов - от младшего к старшему

ps - умозрительная приспособа для обратного порядка -> заменить Inc(p,2) на Inc(p,1)

[f.hump]

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

    DWORD mumu[4] = {X, Y, 0, 0};

    for (;mumu[0];mumu[0]>>=1) mumu[2]++;
    for (;mumu[1];mumu[1]>>=1) mumu[2]--;

    mumu[0] = X;
    mumu[1] = Y;
    mumu[1] <<= mumu[2];

    for (;mumu[1]>=Y;) {
        mumu[3] <<= 1;

        if (mumu[0] >= mumu[1]) {
            mumu[0] -= mumu[1];
            mumu[3] |= 1;
        }

        mumu[1] >>= 1;
    }

    Z = mumu[0];
    return mumu[3];
}

а если так?

"как я буду объяснять всё это бабульке?"

деление в столбик как и у Аватар. он воспользовался сдвигом в 3й WORD Int64. я выровнял делитель внутри DWORD.

[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 Real(k)*Real(y) > Real(x) then 
			b := k
		else
			a := k
	end;

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

Давайте тогда так сравнивать

[evg_m]

мои пять копеек

function divbyte(x: word; y: byte; out z: byte): word;
var
  d: byte;
begin
  d:=0;
  while (y shl d)<x do Inc(d);

  result:=0;
  while d>0 do begin
    if x>(y shl d) then begin 
      x:=x-(y shl d); 
      Inc(result);
    end;
    result:=result shl 1;
    dec(d);
  end;
  z:=x;
end;