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

[min@y™]

а если так?

а вроде всё ОК пока. Переводил на паскаль тупо в лоб, не думая.

function iDivMod_v3(const X: DWORD; const Y: Byte; out Z: Byte): DWORD;
var
  mumu: array[0..3] of DWORD;
begin
  mumu[0]:= X;
  mumu[1]:= Y;
  mumu[2]:= 0;
  mumu[3]:= 0;

  while mumu[0] <> 0 do
    begin
      Inc(mumu[2]);
      mumu[0]:= mumu[0] shr 1;
    end;

  while mumu[1] <> 0 do
    begin
      Dec(mumu[2]);
      mumu[1]:= mumu[1] shr 1;
    end;

  mumu[0]:= X;
  mumu[1]:= Y shl mumu[2];


   while mumu[1] >= Y do
    begin
      mumu[3]:= mumu[3] shl 1;

      if mumu[0] >= mumu[1]
        then begin
               mumu[0]:= mumu[0] - mumu[1];
               mumu[3]:= mumu[3] or 1;
             end;

      mumu[1]:= mumu[1] shr 1;
    end;

  Z:= Byte(mumu[0]);
  Result:= mumu[3];
end;

[min@y™]

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

Взял на проверку. Не думая, допилил под нужный тип данных.

// evg_m
function iDivMod_v4(const X: DWORD; const Y: Byte; out Z: Byte): DWORD;
var
  d: byte;
  vX: DWord;
begin
  d:= 0;
  vX:= X;

  while (Y shl d) < vX do
    Inc(d);

  Result:= 0;

  while d <> 0 do
    begin
      if vX > (Y shl d) // может выехать за старший бит?
        then begin
               vX:= vX - (Y shl d);
               Inc(Result);
             end;

      Result:= Result shl 1;
      Dec(d);
    end;

  z:= vX;
end;

Выглядит аппетитно, но работает криво. Может, допинаешь до 100%-ного результата?



Прога с исходниками и прочим мусором - тут.

[f.hump]

Может, допинаешь до 100%-ного результата?

и сам бы уже мог. сдвиг результата перенеси вперед проверки условия, и >=, вместо >. тоже деление в столбик.

[min@y™]

и сам бы уже мог.

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

function iDivMod_v4(const X: DWORD; const Y: Byte; out Z: Byte): DWORD;
var
  d: byte;
  vX: DWord;
begin
  d:= 0;
  vX:= X;

  while (Y shl d) < vX do
    Inc(d);

  Result:= 0;

  while d <> 0 do
    begin
      Result:= Result shl 1; // сдвиг результата перенеси вперед проверки условия
      
      if vX >= (Y shl d) // и >=, вместо > (может выехать за старший бит?)
        then begin
               vX:= vX - (Y shl d);
               Inc(Result);
             end;

      //Result:= Result shl 1;
      Dec(d);
    end;

  z:= vX;
end;

Целая часть результата отличается от правильного 2 раза (сдвинута на бит вправо), а остаток лежит в диапазоне 0...2Y-1 вместо 0...Y-1.
Я б, конечно, мог понавешать костылей, но отчаянно хочу врубиться, чо происходит с переменными и зачем.

[min@y™]

Сделал простейший бенчмарк. Самым быстрым оказался вариант от f.hump, но он имеет один маленький недостаток - работает неправильно. f.hump, мож допилишь?

[evg_m]

Выглядит аппетитно, но работает криво. Может, допинаешь до 100%-ного результата?

Исправленная версия

function iDivMod_v4(const X: DWORD; const Y: Byte; out Z: Byte): DWORD;
var
  d: byte;
  vX: DWord;
begin
  d:= 0;
  vX:= X;

  if y=0 then Abort; //деление на ноль ?
  while ((Y shl d) <= vX)
    and ((Y shl d) <=$7FFFFFFF) //НЕ выходить выход за старший бит
  do Inc(d);
  if vX>=$80000000 then Inc(d); //добавить обработку старшего бита X

  Result:= 0;

  while d >0 do
    begin
      Dec(d);
      Result:= Result shl 1;
      if vX >= (Y shl d) // может выехать за старший бит?
        then begin
               vX:= vX - (Y shl d);
               Inc(Result);
             end;
    end;

  z:= vX;
end;

P.S. возможно имеет смысл еще в одной переменной

ry:=y shl d;

[min@y™]

Исправленная версия

Принял.
Проверил.
Ок.

[f.hump]

f.hump, мож допилишь?

как-то лень, да и ошибок я не вижу.

зы: если зависает при попытке деления на 0, то это не ошибка, а фича.

[min@y™]

как-то лень, да и ошибок я не вижу.

а не надо. пытаюсь переписать на асме.