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

本文关键字：字符串转换非常数字 | 更新日期: 2023-09-27 18:26:33

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

该编号存在于包含Size项的uint[]数组中。

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

我一直在考虑你的问题。我没有一个解决方案，但这里有一个方法：

首先，在不失一般性的情况下，假设您有一个2ⁿ位的集合。（如果您的比特数少于2ⁿ，请用前导零填充比特数组，直到您这样做为止。显然，这样做永远不会使数组的大小增加一倍。）在您的情况下，您说您有一百万个uint，所以这是2²⁵比特。

我们还假设每个2^k+1比特的集合可以被均匀地划分为两个比特集合，左集合和右集合，每个集合都有2^k个比特。

因此，每个位集合或子集合都有一个"大小"，它是二的精确幂。最小可能的集合包含一个位，不能再细分。

其次，让我们假设你同样有一个十进制形式的数字的不可变表示，并且，在不失一般性的情况下，字符串中有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方法。稍后我们将看到，我们还需要减法和两个Shift运算符，以便快速乘以10的幂。

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

FullShift和HalfShift运算符从旧的数字集合中生成新的数字集合，以便于快速乘以10的幂。如果大小为2^d+1的数字集合由子集合（X1，X2）组成，每个子集合的大小为2d，则"半移位"集合包含2^d+2项，并由（（2^{2^{前导零，X1），（X2，2^{3^{尾随零）组成。全移位集合由（（X1，X2），（2^d+1尾随零）组成。}}}}

这些显然建造起来非常便宜。

乘法是我们遇到大问题的地方。假设在不失一般性的情况下，我们将两个数字集合相乘，每个数字集合正好有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/lg3），大约是O（n^1.58

MakePowerOfTwo怎么样？考虑到我们现有的资源，这很容易。我们使用的身份：

2²ⁿ⁺¹=2ⁿx2ⁿ+2^n-n2^n-

并编写算法：

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）也是如此。

现在我们可以看到，最初对Convert的调用也是由乘法控制的。

因此，使用此算法，如果您有2个^d二进制数字要转换，您可以预期这将需要大约O（2^{1.58 d5}位要转换，因此这将需要约7770亿次计算。

这里的关键事实是，该算法完全由乘法的成本所支配。如果你能将乘法运算的成本降低到小于O（n^1.58），那么你就会获得巨大的胜利。如果我是你的话，我会在Karatsuba上研究十进制乘法算法的改进。

我不知道这是否更快，但这里有一个我很久以前在delphi中写的例子，将大int作为字符串处理（非常快速和肮脏）-这是针对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万比特长的二进制字符串尝试了这个，它慢得离谱！真的不奇怪。这是一个完全未优化的代码，它有很多悬而未决的结果可以用来加快速度。尽管如此，我还是忍不住觉得这是一种（或规模）问题，你可能想在完全优化的汇编中写，至少部分是这样。单独的行动规模很小，但必须多次进行——这意味着乞求集合。多线程当然也可以在这里得到利用。

您可以通过一次处理多个数字来节省一些时间。如果你一次做10万个，它可能会比一次10个快一点。

请注意，它仍然可能非常缓慢，但它会为您节省一些时间。

可以想象，你可以让它递归，并加快它的速度——得到数字的粗略平方根，四舍五入到最接近的指数10。div和mod，并将结果发送回同一函数。请注意，我不确定如何有效地运行这样大小的div或mod，但如果你能弄清楚（并且不会耗尽内存），它肯定会比一次分割一个数字更节省时间。

替代版本：放弃小数——因为这个数字太大了，对任何实际的人类读者来说都没有意义——用十六进制表示。从技术上讲，它仍然是人类可读的，但你可以一次渲染一个字节，并为自己节省大量的心痛。

感谢大家，我主要根据J…的想法找到了一种方法，他建议每次出现1时将数字加2的幂，将数字转换为基于10的数字。但我使用的不是基于10的（人类十进制）系统，而是基于1000000000000000000（10^18）的系统。因此，每个数字不仅有10个可能性（0…9），而且实际上有10^18！这适合64位数字，然后我们将其转换为.ToString()

这是迄今为止最有效的方法。