如有必要，请切换到 BigInteger

Question

我正在读取一个文本文件，其中包含 [1, 10^100] 范围内的数字。然后我对每个数字执行一系列算术运算。仅当数字超出 int/long 范围时，我才想使用 BigInteger。一种方法是计算字符串中有多少位数字，如果太多则切换到 BigInteger。否则我只会使用原始算术，因为它更快。有更好的办法吗？

如果 int 太小，Java 无法自动执行此操作（即切换到 BigInteger）是否有任何原因？这样我们就不用担心溢出的问题了。

Answer 1

我怀疑对整数和实数使用原始值的决定（出于性能原因）使得该选项不可能实现。请注意，Python 和 Ruby 都按照您的要求执行。

在这种情况下，处理较小的特殊情况可能需要做更多的工作而不是值得的（您需要一些自定义类来处理这两种情况），并且您应该只使用 BigInteger。

Answer 2

如果 int 太小，Java 无法自动执行此操作（即切换到 BigInteger）是否有任何原因？

因为这是比当前 Java 更高级别的编程行为。该语言甚至不知道 BigInteger 类及其用途（即它不在 JLS 中）。它只知道用于装箱和拆箱目的的Integer（除其他外）。

说到装箱/拆箱，int 是一种原始类型； BigInteger 是一个引用类型。您不能拥有可以保存这两种类型的值的变量。

Answer 3

您可以将这些值读入 BigInteger，然后将它们转换为 long（如果它们足够小）。

private final BigInteger LONG_MAX = BigInteger.valueOf(Long.MAX_VALUE);
private static List<BigInteger> readAndProcess(BufferedReader rd) throws IOException {
    List<BigInteger> result = new ArrayList<BigInteger>();
    for (String line; (line = rd.readLine()) != null; ) {
        BigInteger bignum = new BigInteger(line);
        if (bignum.compareTo(LONG_MAX) > 0) // doesn't fit in a long
            result.add(bignumCalculation(bignum));
        else result.add(BigInteger.valueOf(primitiveCalculation(bignum.longValue())));
    }
    return result;
}
private BigInteger bignumCalculation(BigInteger value) { 
    // perform the calculation 
}
private long primitiveCalculation(long value) {
    // perform the calculation
}

（您可以将返回值设置为 List 并使其成为 BigInteger 和 Long 对象的混合集合，但这不会看起来非常好，但不会大幅提高性能。）

如果文件中的大量数字足够小，可以容纳在一个文件中，那么性能可能会更好 long（取决于计算的复杂程度）。仍然存在溢出风险，具体取决于您在 primitiveCalculation 中所做的操作，并且您现在已经重复了代码，（至少）使潜在错误加倍，因此您必须确定性能增益是否真的有效是值得的。

不过，如果您的代码与我的示例类似，那么通过并行化代码，您可能会获得更多收益，这样计算和 I/O 就不会在同一个线程上执行 - 您必须做一些对于像这样受 CPU 限制的架构来说，计算量相当大。

Answer 4

当较小的东西就足够了时，使用 BigDecimals 的影响是令人惊讶的，呃，大：

public static class MyLong {
    private long l;
    public MyLong(long l) { this.l = l; }
    public void add(MyLong l2) { l += l2.l; }
}

public static void main(String[] args) throws Exception {
    // generate lots of random numbers
    long ls[] = new long[100000];
    BigDecimal bds[] = new BigDecimal[100000];
    MyLong mls[] = new MyLong[100000];
    Random r = new Random();
    for (int i=0; i<ls.length; i++) {
        long n = r.nextLong();
        ls[i] = n;
        bds[i] = new BigDecimal(n);
        mls[i] = new MyLong(n);
    }
    // time with longs & Bigints
    long t0 = System.currentTimeMillis();
    for (int j=0; j<1000; j++) for (int i=0; i<ls.length-1; i++) {
        ls[i] += ls[i+1];
    }
    long t1 = Math.max(t0 + 1, System.currentTimeMillis());
    for (int j=0; j<1000; j++) for (int i=0; i<ls.length-1; i++) {
        bds[i].add(bds[i+1]);
    }
    long t2 = System.currentTimeMillis();
    for (int j=0; j<1000; j++) for (int i=0; i<ls.length-1; i++) {
        mls[i].add(mls[i+1]);
    }
    long t3 = System.currentTimeMillis();
    // compare times
    t3 -= t2;
    t2 -= t1;
    t1 -= t0;
    DecimalFormat df = new DecimalFormat("0.00");
    System.err.println("long: " + t1 + "ms, bigd: " + t2 + "ms, x"
            + df.format(t2*1.0/t1) + " more, mylong: " + t3 + "ms, x"
            + df.format(t3*1.0/t1) + " more");
}

在我的系统上运行以下代码会产生以下输出：

long：375ms，bigd：6296ms，多 x16.79，mylong：516ms，多 x1.38

MyLong 类只是为了查看拳击的效果，与您将得到的效果进行比较自定义 BigOrLong 类。

Answer 5

Java 很快——真的非常快。它只比 c 慢 2-4 倍，有时和大多数其他语言比 C/Java 慢 10 倍 (python) 到 100 倍 (ruby) 时一样快或快一点。 （顺便说一句，Fortran 也非常快）

部分原因是它不会为您执行诸如切换数字类型之类的操作。它可以，但目前它可以在几个字节内内联一个像“a * 5”这样的操作，想象一下如果 a 是一个对象，它必须经历的循环。它至少是对 a 的乘法方法的动态调用，这比 a 只是一个整数值时慢几百/千倍。

如今，Java 可能实际上可以使用 JIT 编译来更好地优化调用并在运行时内联它，但即使如此，也很少有库调用支持 BigInteger/BigDecimal，因此会有很多本机支持，这将是一种全新的语言。

还想象一下从 int 切换到 BigInteger 而不是 long 会让调试视频游戏变得非常困难！ （是的，每次我们移动到屏幕右侧，游戏速度就会减慢 50 倍，代码都是一样的！这怎么可能？！？）

Answer 6

这可能吗？是的。但它也存在很多问题。

例如，考虑一下 Java 存储对 BigInteger 的引用，它实际上是在堆上分配的，但存储的是 int 文字。在 C 中可以清楚地看出这种差异：

int i;
BigInt* bi;

现在，要自动从文字转换为引用，必须以某种方式对文字进行注释。例如，如果设置了 int 的最高位，则其他位可以用作某种表查找来检索正确的引用。这也意味着只要它溢出，您就会得到一个 BigInt** bi。

当然，这是通常用于符号的位，硬件指令很大程度上依赖于它。更糟糕的是，如果我们这样做，那么硬件将无法检测溢出并设置标志来指示它。因此，每个操作都必须伴随一些测试，以查看是否发生或将发生溢出（取决于何时可以检测到）。

所有这些都会给基本整数运算增加大量开销，这实际上会抵消您必须开始的任何好处。换句话说，假设 BigInt 比尝试使用 int 并检测溢出条件同时处理引用/文字问题更快。

因此，要获得任何真正的优势，就必须使用更多空间来表示整数。因此，我们不是在堆栈、对象或任何其他使用它们的地方存储 32 位，而是存储 64 位，并使用额外的 32 位来控制是否需要引用或文字。这可行，但有一个明显的问题——空间使用。 :-) 不过，我们可能会在 64 位硬件上看到更多这样的情况。

现在，您可能会问为什么不只是 40 位（32 位 + 1 字节）而不是 64 位？基本上，在现代硬件上，出于性能原因，最好以 32 位增量存储内容，因此无论如何我们都会将 40 位填充到 64 位。

编辑

让我们考虑如何在 C# 中执行此操作。现在，我没有 C# 编程经验，所以我无法编写代码来做到这一点，但我希望我可以给出一个概述。

这个想法是为其创建一个结构。它应该大致如下所示：

public struct MixedInt
{
   private int i;
   private System.Numeric.BigInteger bi;

   public MixedInt(string s) 
   {
      bi = BigInteger.Parse(s);
      if (parsed <= int.MaxValue && parsed => int.MinValue)
      {
          i = (int32) parsed;
          bi = 0;
      }   
   }

   // Define all required operations
}

因此，如果数字在整数范围内，我们使用 int，否则我们使用 BigInteger。这些操作必须确保根据需要/可能从一种操作过渡到另一种操作。从客户的角度来看，这是透明的。它只是一种 MixedInt 类型，该类负责使用更适合的类型。

但请注意，这种优化很可能已经成为 C# BigInteger 的一部分，因为它是作为结构体实现的。

如果 Java 有类似 C# 的 struct 的东西，我们也可以在 Java 中做类似的事情。

Answer 7

有什么原因导致Java不能
自动执行此操作，即切换到
BigInteger 如果 int 太小？

这是动态类型的优点之一，但Java是静态类型并阻止了这种情况。

在动态类型语言中，当两个Integer相加时会产生溢出，系统可以自由地返回Long。因为动态类型语言依赖于鸭子类型，所以没问题。在静态类型语言中不会发生同样的情况；它会破坏类型系统。

编辑

鉴于我的答案和评论不清楚，在这里我尝试提供更多详细信息，为什么我认为静态类型是主要问题：

1）事实上，我们谈到原始类型是一个静态类型问题；我们不会关心动态类型语言。

2) 对于基本类型，溢出的结果不能转换为 int 以外的其他类型，因为它对于静态类型来说是不正确的

   int i = Integer.MAX_VALUE + 1; // -2147483648

3) 对于引用类型，它是相同的，只是我们有自动装箱。尽管如此，加法仍无法返回 BigInteger，因为它与静态类型系统不匹配（无法将 BigInteger 转换为 Integer） >）。

  Integer j = new Integer( Integer.MAX_VALUE ) + 1; // -2147483648

4) 可以做的就是子类化 Number 并在 UnboundedNumeric 类型上实现，从而在内部优化表示（表示独立性）。

 UnboundedNum k = new UnboundedNum( Integer.MAX_VALUE ).add( 1 ); // 2147483648

不过，这并不是原来问题的真正答案。

5）对于动态类型，类似的东西

var d = new Integer( Integer.MAX_VALUE ) + 1; // 2147483648

会返回一个Long，这是可以的。