大整数加法优化 Delphi / Windows SDK/APIhttp://www.delphi2007.net/DelphiBase/html/delphi_20061217100254136.html
改自FGInt单元,将原来的
TGInt = Record
Sign : TSign;
Number : Array Of Int64;
定义做了修改.又用汇编做了部分优化,效率提升应该在40%左右.
还有没有更大的优化空间
Unit FBigInt;
Interface
Uses Windows, SysUtils, Controls, Math;
Type
TCompare = (Lt, St, Eq, Er);
TSign = (negative, positive);
TBInt = Record
Sign : TSign;
Number : Array Of Longword;
End;
Function FBIntNew(Size:int64):TBInt;
Procedure FBIntDestroy(Var FBInt : TBInt);
Function FBIntAdd(Const FBInt1, FBInt2 : TBInt):TBInt;
Function FBIntCompareAbs(Const FBInt1, FBInt2 : TBInt) : TCompare;
Implementation
{$H+}
Function FBIntNew(Size:int64):TBInt;
begin
SetLength(Result.Number,Size);
ZeroMemory(Result.Number,Size*8);
Result.Number[0]:=Size-1;
Result.Sign:=positive;
end;
Procedure FBIntDestroy(Var FBInt : TBInt);
Begin
FBInt.Number := Nil;
End;
Function FBIntAdd(Const FBInt1, FBInt2 : TBInt):TBInt;
Var
i, size1, size2, size : longint;
rest : integer;
Trest : int64;
Begin
If FBInt1.Number[0] < FBInt2.Number[0] Then Result:=FBIntAdd(FBInt2, FBInt1) Else
Begin
If FBInt1.Sign = FBInt2.Sign Then
Begin
SetLength(Result.Number, FBInt1.Number[0] + 2);
//rest := 0;
asm
clc
mov eax,[esi+$04]
mov ebp,[eax]
test ebp,ebp
jle @LoopOneEnd
mov ecx,$00000001
@LoopOne:
mov eax,[ebx+$04]
mov eax,[eax+ecx*4]
mov edx,[esi+$04]
adc eax,[edx+ecx*4]
mov edx,[edi+$04]
mov [edx+ecx*4],eax
inc ecx
dec ebp
jnz @LoopOne
@LoopOneEnd:
pushf
mov eax,[esi+$04]
mov ebp,[eax]
mov eax,[ebx+$04]
sub ebp,[eax]
popf
test ebp,ebp
jle @LoopOneEnd
jnc @looptwoend
mov eax,[ebx+$04]
mov eax,[eax+ecx*4]
adc eax,$0
dec ebp
jnz @LoopOneEnd
@looptwoend:
end;
size := FBInt1.Number[0]+1;
// For i := 1 To FBInt2.Number[0] Do
// Begin
// Trest := FBInt1.Number[i] + FBInt2.Number[i] + rest;
// Result.Number[i] := Trest And 4294967295;
// rest := Trest Shr 32;
// End;
// For i := (FBInt2.Number[0] + 1) To FBInt1.Number[0] Do
// Begin
// Trest := FBInt1.Number[i] + rest;
// Result.Number[i] := Trest And 4294967295;
// rest := Trest Shr 32;
// End;
// size := FBInt1.Number[0]+1;
// Result.Number[size] := rest;
While (Result.Number[size] = 0) And (size > 1) Do size := size - 1;
If size <= FBInt1.Number[0] Then SetLength(Result.Number , size + 1);
Result.Number[0] := size ;
Result.Sign := FBInt1.Sign;
End
Else
Begin
If FBIntCompareAbs(FBInt2, FBInt1) = Lt Then Result:=FBIntAdd(FBInt2, FBInt1)
Else
Begin
SetLength(Result.Number, FBInt1.Number[0] + 1);
rest := 0;
asm
clc
mov eax,[esi+$04]
mov ebp,[eax]
test ebp,ebp
jle @LoopOneEnd
mov ecx,$00000001
@LoopOne:
mov eax,[ebx+$04]
mov eax,[eax+ecx*4]
mov edx,[esi+$04]
SBB eax,[edx+ecx*4]
mov edx,[edi+$04]
mov [edx+ecx*4],eax
inc ecx
dec ebp
jnz @LoopOne
@LoopOneEnd:
pushf
mov eax,[esi+$04]
mov ebp,[eax]
mov eax,[ebx+$04]
sub ebp,[eax]
popf
test ebp,ebp
jle @LoopOneEnd
jnc @looptwoend
mov eax,[ebx+$04]
mov eax,[eax+ecx*4]
SBB eax,$0
dec ebp
jnz @LoopOneEnd
@looptwoend:
end;
// For i := 1 To FBInt2.Number[0] Do
// Begin
// Trest := FBInt1.Number[i] - FBInt2.Number[i] + rest;
// Result.Number[i] := Trest And 4294967295;
// If (FBInt1.Number[i] > FBInt2.Number[i]) Then rest := 0 Else rest := -1;
// End;
// For i := (FBInt2.Number[0] + 1) To FBInt1.Number[0] Do
// Begin
// Trest := FBInt1.Number[i] + rest;
// Result.Number[i] := Trest And 4294967295;
// If (FBInt1.Number[i] > FBInt2.Number[i]) Then rest := 0 Else rest := -1;
// End;
size := FBInt1.Number[0];
While (Result.Number[size] = 0) And (size > 1) Do size := size - 1;
If size <= FBInt1.Number[0] Then SetLength(Result.Number , size + 1);
Result.Number[0] := size ;
Result.Sign := FBInt1.Sign;
End;
End;
End;
end;
// Compare 2 FBInts in absolute value, returns
// Lt if FBInt1 > FBInt2, St if FBInt1 < FBInt2, Eq if FBInt1 = FBInt2,
// Er otherwise
Function FBIntCompareAbs(Const FBInt1, FBInt2 : TBInt) : TCompare;
Var
size1, size2, i : longint;
Begin
FBIntCompareAbs := Er;
size1 := FBInt1.Number[0];
size2 := FBInt2.Number[0];
If size1 > size2 Then FBIntCompareAbs := Lt Else
If size1 < size2 Then FBIntCompareAbs := St Else
Begin
i := size2;
While (FBInt1.Number[i] = FBInt2.Number[i]) And (i > 1) Do i := i - 1;
If FBInt1.Number[i] = FBInt2.Number[i] Then FBIntCompareAbs := Eq Else
If FBInt1.Number[i] < FBInt2.Number[i] Then FBIntCompareAbs := St Else
If FBInt1.Number[i] > FBInt2.Number[i] Then FBIntCompareAbs := Lt;
End;
End;
End
注释掉的部分是被ASM替代掉的原代码
自己顶下
支持
虽然用处好像不大。^_^
呵呵，主要是因为最近在研究RSA加密，可是里面使用FGInt大整数运算单元效率太低，所以打算重写一下，看能不能提高效率