|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Roma Baklanov 2:5050/38.30 02 Mar 2002 23:11:22
To : Ilia Kantor
Subject : Большие числа
--------------------------------------------------------------------------------
Давече заходил на твой? сайт (AlgoNew.Manual.ru).
Здорово, есть почти все, что надо, что хотел.
Есть практически все по большим числам и куча хороших алгоритмов во многих
областях. Всем оччччень советую.
Hо все равно хочу привести свое решение умоножения больших дробных чисел с
фиксированной запятой и вопрос:
const
lv_ValueSize = 16; // 64Kbytes maximum ( 2^524288 ).
lv_FracSize = 2;
lv_IntegerSize = lv_ValueSize - lv_FracSize;
type
TLongValue = record
case LongInt of
0:(
Integer: array[0..lv_IntegerSize-1] of byte;
Frac: array[0..lv_FracSize-1] of byte);
1:(
Value: array[0..lv_ValueSize-1] of byte);
end;
{==========================================================================}
function lv_Zero: TLongValue;
begin
FillChar(Result,sizeof(Result),0);
end;
{==========================================================================}
function lv_Neg(V: TLongValue): TLongValue;
var
i,o: word;
begin
o:=1;
for i:=lv_ValueSize-1 downto 0 do begin
o:=255-V.Value[i]+o;
Result.Value[i]:=o and $FF;
o:=o shr 8;
end;
end;
{==========================================================================}
function lv_Add(V1,V2: TLongValue): TLongValue;
var
i,o: word;
begin
o:=0;
for i:=lv_ValueSize-1 downto 0 do begin
o:=V1.Value[i]+V2.Value[i]+o;
Result.Value[i]:=o and $FF;
o:=o shr 8;
end;
end;
{==========================================================================}
function lv_Sub(V1,V2: TLongValue): TLongValue;
begin
Result:=lv_Add(V1,lv_Neg(V2));
end;
{==========================================================================}
function lv_ShL(V: TLongValue; Count: LongInt): TLongValue;
var
i,k: LongInt;
l,o: byte;
begin
if Count<0 then begin
Result:=lv_ShR(V,-Count);
exit;
end;
Result:=lv_Zero;
k:=Count shr 3;
l:=Count and 7;
o:=0;
for i:=lv_ValueSize-1-k downto 0 do begin
Result.Value[i]:=(V.Value[i+k] shl l) or o;
o:=V.Value[i+k] shr (8-l);
end;
end;
{==========================================================================}
function lv_ShR(V: TLongValue; Count: LongInt): TLongValue;
var
i,k: LongInt;
l,o: byte;
begin
if Count<0 then begin
Result:=lv_ShL(V,-Count);
exit;
end;
Result:=lv_Zero;
k:=Count shr 3;
l:=Count and 7;
o:=0;
for i:=k to lv_ValueSize-1 do begin
Result.Value[i]:=(V.Value[i-k] shr l) or o;
o:=V.Value[i-k] shl (8-l);
end;
end;
{==========================================================================}
function lv_Mul(V1,V2: TLongValue): TLongValue;
var
i,j: word;
o: LongInt;
begin
Result:=lv_Zero;
for i:=0 to lv_ValueSize-1 do begin
if V2.Value[i]=0 then
continue;
for j:=0 to 7 do begin
if (V2.Value[i] shl j) and 128 = 0 then
continue;
o:=(lv_IntegerSize-1-i) shl 3+(7-j);
Result:=lv_Add(Result,lv_ShL(V1,o));
end;
end;
end;
Как видно, оптимизации практически нет, но сам алгоритм хороший и простой.
Максимальный размер чисел можно запросто увеличить до 4Gb, а скорость -
увеличить практически в 2 раза, путем изменения элемента с Byte на Word или DW.
При данном тексте на моем K6-2-300 умножение с результатом в 64Kb выполняется
за доли секунды, точно не замерял.
Единственная проблема - погрешность в дробной части:
10.3*1 будет выглядеть как 10.2999... -Из-за разницы систем исчисления.
Так вот, может, у кого есть какие-нить идеи на счет решения данной проблемы?
Хотя сам не представляю, как по-умному можно от этого избавиться.
C уважением, Roma Baklanov.
--- UNREG UNREG
* Origin: А нам все равно, что вино, что пулемет, лишь бы стеба (2:5050/38.30)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
