Целочисленный MulDiv

← →
DayGaykin © (2016-08-25 10:28) [0]

Предлагается следующая задача:

Написать функцию MulDiv для 64х-битных знаковых аргументов.

Изначально задача поставлена для реализации на языке java: https://toster.ru/q/347954

Функция должна быть похожа на следующую:
function MulDiv(A, B, C: Int64):Int64; begin Result := A * B / C; end;
со следующими условиями:
1. Функция должна корректно работать при A * B > High(Int64).
2. Если результат вычисления не "влезает" в Int64, функция должна "поднять" исключение.
3. Точность выполнения и метод округления должен совпадать с точностью и округлением обычной целочисленной арифметики (той, что "помещается" в типы).
4. В функции нельзя использовать числа с плавающей точкой.
5. Нельзя выполнять операции, которые приведут к использованию кучи.
6. Можно использовать только чистый паскаль. Ассемблер использовать нельзя.
7. Нельзя использовать возможность процессора умножать числа с переполнением. (Хотя не понятно как это можно использовать без ассемблера).
8. Нельзя использовать функции, которые сами не удовлетворяют условиям 4, 5, 6, 7, 8.
9. Желательно не использовать беззнаковые типы.

На Java я написал тест, для Delphi напишу тест чуть позже.

← →
NoUser © (2016-08-25 16:18) [1]

// System.pas MulDivInt64(...); // ( _MulDivModInt64 )

Не?

← →
NoUser © (2016-08-25 16:49) [2]

зы.

п.2: противоречит п.1
п.3: что такое "округление обычной целочисленной арифметики"
п.4: хм, а ведь Max(Int64) = Int64(Double(NaN)) ;)

← →
DayGaykin © (2016-08-25 16:49) [3]

> NoUser © (25.08.16 16:18) [1]

Уверены, что удовлетворяет условиям?

← →
DayGaykin © (2016-08-25 16:51) [4]

> п.2: противоречит п.1

MaxInt64 * MaxInt64 / MaxInt64 - результат влезает в Int64,
хотя MaxInt64 * MaxInt64 - не влезает.

> п.3: что такое "округление обычной целочисленной арифметики"

А как вы думаете?

← →
NoUser © (2016-08-25 17:03) [5]

> Уверены, что удовлетворяет условиям?

Не знаю, а чё не так?

>> п.2: противоречит п.1

каюсь, прочитал как Если результат промежуточных вычислений

> А как вы думаете?

думаю, что "в обычной целочисленной арифметики" нет "округления"

> думаю, что "в обычной целочисленной арифметики" нет "округления"

А что по вашему произойдет при вычислении:
intVariable = 3/2;

> Не знаю, а чё не так?

К сожалению, у меня нет delphi под рукой. Я уверен, что там или асм или вызов апишной функции.

> intVariable = 3/2;

"Incompatible types:" ?

{$IF defined(CPUARM) or defined(CPUX86) or defined(EXTERNALLINKER)} function _MulDivModInt64(AValue, AMul, ADiv: Int64; Remainder: PInt64): Int64; var HVal, Temp, LVal, HRes, LRes: UInt64; Sign: Byte; begin // This function is used by division or multiply operator // for scaling "Comp" value // eq. Result := Int64((Int128(AValue) * Int128(AMul)) div ADiv); // or Result := Int64((Extended80(AValue) * Extended80(AMul)) / Extended80(ADiv)); Sign := 0; if AValue < 0 then begin AValue := - AValue; Sign := Sign xor 3; end; if AMul < 0 then begin AMul := - AMul; Sign := Sign xor 1; end; if ADiv < 0 then begin ADiv := - ADiv; Sign := Sign xor 1; end; // // Int128(HVal:LVal) := Int128(AValue) * Int128(AMul); // HVal := UInt64(UInt32(AValue shr 32)) * UInt64(UInt32(AMul shr 32)); Temp := UInt64(UInt32(AValue shr 32)) * UInt64(UInt32(AMul)) + UInt64(UInt32(AValue)) * UInt64(UInt32(AMul shr 32)); LVal := UInt64(UInt32(AValue)) * UInt64(UInt32(AMul)); Temp := Temp + (LVal shr 32); LVal := (Temp shl 32) + UInt64(UInt32(LVal)); HVal := HVal + (Temp shr 32); // // Result := Int128(HVal:LVal) div ADiv; // //URes := HVal div UInt64(ADiv); Temp := HVal mod UInt64(ADiv); Temp := (Temp shl 32) + (LVal shr 32); HRes := Temp div UInt64(ADiv); Temp := Temp mod UInt64(ADiv); Temp := (Temp shl 32) + UInt64(UInt32(LVal)); LRes := Temp div UInt64(ADiv); Result := (HRes shl 32) + LRes; if (Sign and 1) <> 0 then Result := - Result; if Assigned(Remainder) then begin Remainder^ := Temp mod UInt64(ADiv); if (Sign and 2) <> 0 then Remainder^ := - Remainder^; end; end; {$ENDIF CPUARM or CPUX86}

за UInt-ы невзыщите ))

> NoUser © (25.08.16 17:14) [7]

Интересно, изучу.

> > intVariable = 3/2;
>
> "Incompatible types:" ?

Прошу прощения, уже отвык немного от паскаля.
Имел ввиду: intVariable = 3 div 2

Целочисленный MulDiv Найти похожие ветки