将非常大的数字转换为基数10字符串

Question

一个整数测量4个字节.在我的例子中,我的数字为1 MB.如何快速将它们转换为人类可读的十进制数？

该数字存在于uint[]包含Size项目的数组中.

Answer 1

我一直在考虑你的问题.我没有编写解决方案,但这是一种方法:

首先,让我们假设你有一个2 ⁿ位的集合而不失一般性.(如果你的位数少于2 ⁿ,则用前导零填充位数组,直到你这样做.显然,这样做的时间绝对不会超过数组的大小.)在你的情况下,你说你有一百万的uint,所以这是2 ²⁵位.

我们还假设每个2 ^{k + 1}位的集合可以均匀地分成两个位集合,左右集合,每个集合有2 ^k位.

因此,每个比特集合或子集合具有"大小",其是2的精确幂.最小的集合包含一个位,无法进一步细分.

其次,我们假设您同样具有十进制形式的数字的不可变表示,并且再次,在不失一般性的情况下,字符串中有2个^d十进制数字.如果少于恰好2 ^d,则再次使用前导零填充.同样,每个大小大于1的小数集合可以分成两个集合,每个集合大小只有一半.

现在我们勾勒出一个递归算法:

DigitCollection Convert(BitCollection bits)
{
    if (bits.Size == 1)
        return bits[0] ? DigitCollection.SingleOne : DigitCollection.SingleZero;
    DigitCollection left = Convert(bits.Left);        
    DigitCollection right = Convert(bits.Right);
    DigitCollection power = MakePowerOfTwo(bits.Right.Size);
    return Add(Multiply(left, power), right);
}

我们现在需要方法Add,Multiply和MakePowerOfTwo.正如我们稍后将看到的,我们还需要Subtract和两个Shift运算符,以便快速乘以10的幂.

加法和减法很容易.显然,如果较长的集合包含n个数字,则可以实现加法和减法方法以花费O(n)时间.

FullShift和HalfShift运算符从旧的数字集合中创建新的数字集合,以便于以10的幂进行快速乘法.如果大小为2 ^{d + 1}的数字集合由每个大小为2 ^d的子集合(X1,X2)组成,则"半移"集合包含2 ^{d + 2}项并由((2 ^d前导零,X1)组成),(X2,2 ^d尾随零)).全班集合包括((X1,X2),(2 ^{d + 1}尾随零)).

这些显然非常便宜.

乘法是我们遇到大问题的地方.假如没有,我们每两个DigitCollections相乘正好与2一般性的损失^d数字.我们可以使用Karatsuba的算法:

DigitCollection Multiply(DigitCollection x, DigitCollection y)
{
    // Assume x and y are the same digit size.
    if (x and y are both single digits)
        return the trivial solution;
    // Assume that z2, z1 and z0 are all the same digit size as x and y.
    DigitCollection z2 = Multiply(x.Left, y.Left);
    DigitCollection z0 = Multiply(x.Right, y.Right);
    DigitCollection z1 = Subtract(
        Multiply(Add(x.Left, x.Right), Add(y.Left, y.Right)),
        Add(z2, z0));
    return Add(Add(FullShift(z2), HalfShift(z1)), z0);
}

这个算法的顺序是什么？假设有n = 2个^d位.什么是O(乘(n))？我们递归三次,每次都有一半的数字问题.其余的加,减和移位操作都不超过O(n).所以我们有一个复发:

T(n) = 3 T(n/2) + O(n)

通过主定理有一个简单的解决方案:这个算法是O(n ^{1/lg 3}),大约是O(n ^1.58).

MakePowerOfTwo怎么样？鉴于我们已经拥有的东西,这很容易.我们使用身份:

2 ^{2n + 1} = 2 ⁿ x 2 ⁿ + 2 ⁿ x 2 ⁿ

并编写算法:

DigitCollection MakePowerOfTwo(int p)
{
    if (p == 0) return DigitCollection.SingleOne;
    DigitCollection power = MakePowerOfTwo(p / 2);
    power = Multiply(power, power);
    if (p % 2 != 0)
        power = Add(power, power);
    return power;
}

它由乘法的计算决定,O(n ^1.58)也是如此.

现在我们可以看到转换的原始调用也由乘法控制.

因此,如果您有2 ^d二进制数字进行转换,使用此算法,您可以预期这将需要大约O(2 ^{1.58 d})步骤.在你的情况下你有2 ²⁵位转换,所以这应该需要大约7,770亿计算.

这里的关键事实是该算法完全由乘法的成本支配.如果你可以将乘法的成本降低到小于O(n ^1.58),那么你将获得巨大的胜利.如果我是你,我将研究改进Karatsuba上的十进制乘法算法.

Answer 2

我不知道这是否更快，但这是我很久以前在delphi中写的一个例子，用于将大整数作为字符串处理（非常快和脏） - 这是针对128位uint的，但你可以无限期地扩展它

Function HexToBinShort(hex:integer):string;
begin
  case hex of
    0:  result:='0000';  //convert each hex digit to binary string
    1:  result:='0001';  //could do this with high-nybble and low nybble
    2:  result:='0010';  //of each sequential byte in the array (mask and bit shift)
    3:  result:='0011';  //ie: binstring:=binstring + HexToBinShort(nybble[i])
    4:  result:='0100';  //but must count DOWN for i (start with MSB!)
    5:  result:='0101';
    6:  result:='0110';
    7:  result:='0111';
    8:  result:='1000';
    9:  result:='1001';
    10: result:='1010';
    11: result:='1011';
    12: result:='1100';
    13: result:='1101';
    14: result:='1110';
    15: result:='1111';
  end;
end;

然后每次看到“1”时，取出连接的二进制字符串并添加 2 的幂

Function BinToIntString(binstring:string):string;
var i, j : integer;
var calcHold, calc2 :string;
begin
  calc2:=binstring[Length(binstring)];   // first bit is easy 0 or 1
  for i := (Length(binstring) - 1) downto 1 do begin       
    if binstring[i] = '1' then begin   
       calcHold:=generateCard(Length(binstring)-i);
       calc2 := AddDecimalStrings(calcHold, calc2);
    end;
  end;
  result:=calc2;
end;

generateCard 用于创建 2^i 的十进制字符串表示形式（对于 i>0）

Function generateCard(i:integer):string;
var j : integer;
var outVal : string;
begin
  outVal := '2';
  if i > 1 then begin
    for j := 2 to i do begin
      outVal:= MulByTwo(outVal);
    end;
  end;
  result := outVal;
end;

MulByTwo 将十进制字符串乘以二

Function MulByTwo(val:string):string;
var i : integer;
var carry, hold : integer;
var outHold : string;
var outString :string;
var outString2 : string;
begin
  outString:= StringOfChar('0', Length(val) + 1);
  outString2:= StringOfChar('0', Length(val));
  carry :=0;
  for i := Length(val) downto 1 do begin
    hold := StrToInt(val[i]) * 2 + carry;
    if hold >= 10 then begin
      carry := 1;
      hold := hold - 10;
    end else begin
      carry := 0;
    end;
    outHold := IntToStr(hold);
    outString[i+1] := outHold[1];
  end;
  if carry = 1 then begin
    outString[1] := '1';
    result := outString;
  end else begin
    for i := 1 to length(outString2) do outString2[i]:=outString[i+1];
    result := outString2;
  end;
end; 

最后 - AddDecimalStrings...好吧，它添加了两个十进制字符串：

Function AddDecimalStrings(val1, val2:string):string;
var i,j :integer;
var carry, hold, largest: integer;
var outString, outString2, bigVal, smVal, outHold:string;
begin
  if Length(val1) > Length(val2) then begin
    largest:= Length(val1);
    bigVal := val1;
    smVal := StringOfChar('0', largest);
    j:=1;
    for i := (largest - length(val2) +1) to largest do begin
      smVal[i] := val2[j];
      j:=j+1;
    end;
  end else begin
    if length(val2) > Length(val1) then begin
      largest:=Length(val2);
      bigVal:=val2;
      smVal := StringOfChar('0', largest);
      j:=1;
      for i := (largest - length(val1) +1) to largest do begin
        smVal[i] := val1[j];
        j:=j+1;
      end;
    end else begin
      largest:=length(val1);
      bigVal:=val1;
      smVal:=val2;
    end;
  end;
  carry:=0;
  outString:=StringOfChar('0', largest +1);
  outString2:=StringOfChar('0', largest);

  for i := largest downto 1 do begin
    hold := StrToInt(bigVal[i]) + StrToInt(smVal[i]) + carry;
    if hold >=10 then begin
      carry:=1;
      hold := hold - 10;
    end else begin
      carry:=0;
    end;
    outHold:= IntToStr(hold);
    outString[i+1]:=outHold[1];
  end;

  if carry = 1 then begin
    outString[1] := '1';
    result := outString;
  end else begin
    for i := 1 to length(outString2) do outString2[i]:=outString[i+1];
    result := outString2;
  end;  
end;

这些函数允许您对几乎任意大的整数作为字符串执行基本算术。当然，当位数太大而无法索引数组时，您就会遇到另一堵墙。

顺便说一句，这是除以二的结果（对于反方向很有用......）。我这里不处理奇数。

Function DivByTwo(val:string):string;
var i : integer;
var hold : integer;
var outHold : string;
var outString, outString2 :string;
begin
  outString:=StringOfChar('0',Length(val));

  for i := Length(val) downto 1 do begin
    if StrToInt(val[i]) mod 2 = 0 then begin
      hold:= Math.Floor(StrToInt(val[i]) / 2);
      outHold:= IntToStr(hold);
      outString[i]:=outHold[1];
    end else begin
      hold:= Math.Floor((StrToInt(val[i]) - 1) / 2);
      outHold:=IntToStr(hold);
      outString[i]:= outHold[1];
      if i <> Length(val) then begin
        hold:= StrToInt(outString[i+1]) + 5;
        outHold:= IntToStr(hold);
        outString[i+1] := outHold[1];
      end;
    end;
  end;
  outString2:=StringOfChar('0',Length(val)-1);
  if (outString[1] = '0') and (length(outString) > 1) then begin
    for i := 1 to length(outString2) do outString2[i]:=outString[i+1];
    result:=outString2;
  end else begin
    result:=outString;
  end;
end;

编辑：我刚刚用 900 万位长的二进制字符串尝试过，它慢得离谱！真的，这并不奇怪。这是完全未经优化的代码，有很多容易实现的目标可以加快速度。尽管如此，我还是忍不住觉得这就是您可能想要在完全优化的汇编中至少部分地编写的问题类型（或规模）。单个操作虽小，但必须进行多次——这意味着需要组装。当然也可以在这里利用多线程。