Форум: "Основная";
Текущий архив: 2003.12.30;
Скачать: [xml.tar.bz2];

Вниз

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

← →
mike.dld   (2003-12-17 15:59) [0]

Помогите, пожалуйста, разобраться в процедуре Divide, по какоду принципу она работает (какой алгоритм использует)


const
MAXDIG = 250
BASE = 10000

type
TLongNumber = array [0..MAXDIG] of SmallInt;

function ShiftCompare(A,B: TLongNumber; Shift: SmallInt): Byte;
var
i: SmallInt;
begin
if A[0] > (B[0]+Shift) then
Result := 0
else
if A[0] < (B[0]+Shift) then
Result := 1
else
begin
i := A[0];
while (i > Shift) and (A[i] = B[i-Shift]) do
dec(i);
if i = Shift then
begin
Result := 0;
for i := 1 to Shift do
if A[i] > 0 then
Exit;
Result := 2;
end
else
Result := Byte(A[i]<B[i-Shift]) ;
end;
end;

function BinSearch(var A: TLongNumber; B: TLongNumber; Shift: SmallInt): SmallInt;
var
Down,Up: Word;
C: TLongNumber;
begin
Down := 0;
Up := BASE;
while Up-1 > Down do
begin
C := ShortMult(B,(Up+Down) div 2);
case ShiftCompare(A,C,Shift) of
0: Down := (Down+Up) div 2;
1: Up := (Up+Down) div 2;
2: begin
Up := (Up+Down) div 2;
Down := Up;
end;
end;
end;
C := ShortMult(B,(Up+Down) div 2);
if Compare(A,C) = 0 then
A := ShiftSub(A,C,Shift)
else
A := ShiftSub(C,A,Shift);
Result := (Up+Down) div 2;
end;

function Divide(A,B: TLongNumber; var Rem: TLongNumber): TLongNumber;
var
Shift: SmallInt;
begin
Rem := A;
Shift := A[0] - B[0];
if ShiftCompare(A,B,Shift) = 1 then
dec(Shift);
Result[0] := Shift + 1;
while Shift >= 0 do
begin
Result[Shift+1] := BinSearch(Rem,B,Shift);
dec(Shift);
end;
end;


---

← →
Amoeba   (2003-12-17 16:10) [1]

А собственная голова на плечах для чего? Шапку носить?

---

← →
MBo   (2003-12-17 16:47) [2]

Метод деления уголком, только очередная "10000-ричная цифра" результата ищется не прикидкой или перебором, а двоичным поиском

---

Страницы: 1 вся ветка

Форум: "Основная";
Текущий архив: 2003.12.30;
Скачать: [xml.tar.bz2];

Наверх

Память: 0.44 MB
Время: 0.007 c