logo标签列表

将非常大的数字转换为十进制字符串

c#math
6
一个整数占用4字节。在我的例子中，我有以MB为单位的数字。如何将它们转换成人类可读的十进制数，而且要快速？
这些数字存在于包含Size个项的uint[]数组中。
7
如果一个数字需要占用1 MB的存储空间，我不确定它能否被人类读懂。 - Lester
3
有哪个人会想要阅读一百万位数字？ - J...
3
我认为你很难说一个这么大的数字是可读的。它必须是精确的吗？或者用10个有效数字 X 10^巨大的指数足够了吗？ - Kendrick
3
不确定为什么会有这么多负评？展示一个一百万位数字的想法可能听起来很荒谬，但我不知道具体情况。我觉得问题本身看起来不错，尽管缺少一些信息。这是我想知道的一件事：数组实际包含什么？如果该数字已经作为单个数字存在，那么这就变成了简单的字符串连接。如果这个数字是一个一百万位的比特位数，需要将其每4个字节分割并放入一个uint数组中，这是不同的。 - Michael Stum
5
这是一个“分而治之”的进制转换算法。其思想是递归使用基数，大致等于输入大小的一半。因此，不是每次都除以 10，而是除以例如 10^100000，并递归地继续，直到所有子转换都简化为微不足道的内容为止。要实现次二次性能，需要亚二次乘法运算。要实现 O(n * log(n)^2)，需要使用基于FFT的乘法。因此，这是一个非平凡的算法。 - Mysticial
显示剩余9条评论
4个回答
10
我已经考虑了你的问题。尽管我没有编写好解决方案，但是这里有一种方法：
首先，让我们假设您拥有2的n次方位的位集合（不失一般性）。在您的情况下，您说您有一百万个无符号整数，所以这是2的25次方位。
让我们还假设每个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运算符，用于快速乘以十的幂次。
加法和减法很容易实现。显然，如果较长的集合包含n位数字，则可以实现需要O(n)时间的加法和减法方法。
FullShift和HalfShift运算符从旧的数字集合中创建新的数字集合，以便快速乘以十的幂次。如果一个大小为2d+1的数字集合由大小为2d的子集合(X1, X2)组成，则“半移位”集合包含2d+2个项目，并且由((2d个前导零，X1)，(X2，2d个尾随零))组成。完全移位集合由((X1，X2)，(2d+1个尾随零))组成。
这些构造显然非常便宜。 乘法是我们遇到的大问题。假设不失一般性地，我们正在将两个具有恰好2d位数字的DigitCollections相乘。我们可以使用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 = 2d个数字。那么O(Multiply(n))是多少？我们递归三次，每次问题规模减半。其余的加、减和移位操作都不超过O(n)。因此我们得到一个递推公式：

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

这个问题可以通过主定理轻松解决：该算法的时间复杂度为O(n1/lg 3)，约等于O(n1.58)。
那么MakePowerOfTwo呢？由于我们已经有了一些东西，这很容易。我们使用以下公式：
2的(2n+1)次方=2的n次方x2的n次方+2的n次方x2的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(n1.58)。

现在我们可以看到Convert函数的原始调用也受到乘法运算的影响。

因此，使用此算法转换2d个二进制位，需要大约O(21.58 d)步骤。在您的情况下，您需要转换225个二进制位，因此需要进行约7770亿次计算。

关键事实是，该算法的成本完全由乘法运算的成本支配。如果您能将乘法运算的成本降低到小于O(n1.58)，则可以获得巨大的收益。如果我是您，我会研究改进Karatsuba算法的十进制乘法算法。

1
将其发挥到极致，这是由GMP C库实现的O（n * log（n）^ 2）[分治转换算法]（http://gmplib.org/manual/Binary-to-Radix.html）。 GMP使用接近于O（n * log（n））的基于FFT的乘法算法。我知道Java的BigInteger缺乏次二次幂乘法。只是好奇：C＃的 BigInteger是否具有次二次幂乘法？它是否具有O（n * log（n））乘法？ - Mysticial
@Mysticial：我不知道！找出来会很有趣。 - Eric Lippert
3

我不知道这个方法是否更快，但是这里有一个我很久以前用Delphi写的处理大整数作为字符串的例子（非常简单粗暴）- 这是针对128位无符号整数的，但你可以无限扩展。

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函数可以将一个小数字符串乘以2。

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万位长的二进制字符串尝试了一下，结果非常慢！这并不奇怪。这是完全未经优化的代码，有很多可以进行优化的地方。尽管如此，我仍然觉得这可能是你想要编写的类型（或规模）的问题，至少部分地使用完全优化的汇编语言。单个操作很小，但必须执行很多次——这意味着需要使用汇编语言。在这里还可以利用多线程。

这比我的尝试更快。我实现了它（思路而非复制粘贴），速度快多了，但是当处理一百万位小数并将其乘以2——一百万次时，速度也会变慢。但目前这是最好的方法。但我仍然愿意听取其他想法 :) - bytecode77
如果您不想使用汇编语言，可以通过按升序先执行所有“generateCard”调用来加快速度 - 假设您有足够的RAM将其全部保存在内存中，您可以为下一个计算重复使用每个调用（或将它们存储在某个地方）。我在大约50kbits时达到了约1GB的内存使用量 - 您可能需要20-30GB的系统内存才能使其正常工作。我认为可能有更好的方法... Mystical关于n * log（n）^ 2解决方案的断言很有趣。 - J...
3
你可以一次处理多个数字来节省时间。例如，一次处理10万个数字可能比一个一个地处理10个数字会稍微快一些。
当然，它仍然可能非常缓慢，但至少能节省一些时间。
有可能将其递归处理，并加快速度 - 获取数字的粗略平方根，向下舍入到最接近的10的指数。通过该数字进行除法和模运算，并将结果发送回同一函数。请注意，我不确定如何有效地运行这么大的除法或模运算，但如果您能够解决（并且不会耗尽内存），它仍然比按位除以数字更具时间效率。
备选版本：放弃小数 - 因为这个数字对于任何真正的人类读者来说都太大了，而在十六进制中呈现出来。虽然还是可读的，但你可以按字节呈现它，节省了很多麻烦。
2
同时执行很多任务可能会节省时间。递归很可能会导致堆栈溢出。 - Zéychin
0
感谢大家，我找到了一种方法，主要基于J...的想法，他建议通过每次加上2的幂将数字转换为10进制数字。但是，我使用的不是10进制（人类十进制系统），而是1000000000000000000（10 ^ 18）进制系统。因此，每个数字不仅有10个可能性（0…9），而实际上有10 ^ 18！这适合64位数字，然后我们将其转换为.ToString（）

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接