delphi – 检查64位乘以常数的参数

对于我的BigInteger代码,对于非常大的BigIntegers,输出结果很慢.所以现在我使用一个递归的分而治之算法,它仍然需要2’30“才能将当前最大的已知素数转换为超过2200万位数的十进制字符串(但只有135 ms将其转换为十六进制字符串) .

我仍然想减少时间,所以我需要一个例程,可以将NativeUInt(即32位平台上的UInt32,64位平台上的UInt64)除以100非常快.所以我使用乘法乘法.这在32位代码中工作正常,但我对64位不是100％肯定.

所以我的问题是：有没有办法检查乘以无符号64位值的乘法结果的可靠性？我通过简单地尝试使用UInt32的所有值(0 .. $FFFFFFFF)来检查32位值.这花费了大约. 3分钟.检查所有UInt64将花费比我的生命更长的时间.有没有办法检查使用的参数(恒定,换档后)是否可靠？

我注意到如果选择的参数错误(但接近),DivMod100()总是因为4000004B这样的值而失败.是否有特殊值或范围来检查64位,所以我不必检查所有值？

我目前的代码：

const
{$IF DEFINED(WIN32)}
  // Checked
  Div100Const = UInt32(UInt64($1FFFFFFFFF) div 100 + 1);
  Div100PostShift = 5;
{$ELSEIF DEFINED(WIN64)}
  // Unchecked!!
  Div100Const = $A3D70A3D70A3D71; 
  // UInt64(UInt128($3 FFFF FFFF FFFF FFFF) div 100 + 1); 
  // UInt128 is fictive type.
  Div100PostShift = 2;
{$IFEND}

// Calculates X div 100 using multiplication by a constant,taking the
// high part of the 64 bit (or 128 bit) result and shifting
// right. The remainder is calculated as X - quotient * 100;
// This was tested to work safely and quickly for all values of UInt32.
function DivMod100(var X: NativeUInt): NativeUInt;
{$IFDEF WIN32}
asm
        // EAX = address of X,X is UInt32 here.
        PUSH    EBX
        MOV     EDX,Div100Const
        MOV     ECX,EAX
        MOV     EAX,[ECX]
        MOV     EBX,EAX
        MUL     EDX
        SHR     EDX,Div100PostShift
        MOV     [ECX],EDX       // Quotient

        // Slightly faster than MUL

        LEA     EDX,[EDX + 4*EDX] // EDX := EDX * 5;
        LEA     EDX,[EDX + 4*EDX] // EDX := EDX * 5;
        SHL     EDX,2             // EDX := EDX * 4; 5*5*4 = 100.

        MOV     EAX,EBX
        SUB     EAX,EDX         // Remainder
        POP     EBX
end;
{$ELSE WIN64}
asm
        .NOFRAME

        // RCX is address of X,X is UInt64 here.
        MOV     RAX,[RCX]
        MOV     R8,RAX
        XOR     RDX,RDX
        MOV     R9,Div100Const
        MUL     R9
        SHR     RDX,Div100PostShift
        MOV     [RCX],RDX      // Quotient

        // Faster than LEA and SHL

        MOV     RAX,RDX
        MOV     R9D,100
        MUL     R9
        SUB     R8,RAX
        MOV     RAX,R8         // Remainder
end;
{$ENDIF WIN32}

#include <stdint.h>

// rem,quot ordering takes one extra instruction
struct divmod { uint64_t quotient,remainder; }
 div_by_100(uint64_t x) {
    struct divmod retval = { x%100,x/100 };
    return retval;
}

movabs  rdx,2951479051793528259
    mov     rax,rdi            ; Function arg starts in RDI (SysV ABI)
    shr     rax,2
    mul     rdx
    shr     rdx,2
    lea     rax,[rdx+rdx*4]    ; multiply by 5
    lea     rax,[rax+rax*4]    ; multiply by another 5
    sal     rax,2              ; imul rax,rdx,100 is better here (Intel SnB).
    sub     rdi,rax
    mov     rax,rdi
    ret
; return values in rdx:rax