Java BigInteger,切断了最后一位数字

相当容易,如果BigInteger数字是543,我希望它切断最后一位数,使其为54 .

两种简单的方法可以是:

  • 使用字符串,获取子字符串并使用新值创建新的biginteger .

  • 使用数字10的BigIntegers除法 . (543/10 = 54.3 => 54)

事情是,我当然会用大整数执行这个_752091次 .

我的猜测是,用字符串来玩会慢一点,但我又没有那么多地使用Bigintegers,也不知道“除法”操作有多昂贵 .

速度在这里是必不可少的,实现这个的最快方法是什么(内存只是速度没问题)?

其他解决方案也受到欢迎 .

回答(9)

2 years ago

除以10比使用子串操作要快得多 . 使用以下基准测试,我得到大约161倍(比率与位数成比例)

long divTime = 0;
    long substrTime = 0;
    final int bitsCount = 1000;

    for (int i = 0; i < 1000; ++i) {
        long t1, t2;
        BigInteger random = new BigInteger(bitsCount, new Random());

        t1 = System.currentTimeMillis();
        random.divide(BigInteger.TEN);
        t2 = System.currentTimeMillis();
        divTime += (t2 - t1);

        t1 = System.currentTimeMillis();
        String str = random.toString();
        new BigInteger(str.substring(0, str.length() - 1));
        t2 = System.currentTimeMillis();
        substrTime += (t2 - t1);
    }

    System.out.println("Divide: " + divTime);
    System.out.println("Substr: " + substrTime);
    System.out.println("Ratio:  " + (substrTime / divTime));

2 years ago

除以10最有可能更快 .

2 years ago

如果静态地创建一个具有数字10的BigInteger,然后使用它除以10,那么这可能是最快的方法 . 每次都要创建一个临时的新BigInteger .

substring的问题在于你实际上每次都在创建一个新的String,而且速度要慢得多,更不用说迭代字符串来获取其子字符串的速度慢了 .

2 years ago

最快的实现可能是使用其内部表示使用基数10的数据类型,即某种BCD . 然后,除以10将简单地意味着删除最后一个字节(或者如果以正确的方式实现它,甚至只是递增/递减索引) .

当然,您必须从头开始实现所需的所有算术运算和其他运算,这需要做很多工作 .

2 years ago

最快的方法是使用有效的内部划分实现将数字除以10 . 该操作的内部是在幕后,但肯定是非平凡的,因为数字存储在base-2 .

2 years ago

甚至提出这个问题可能为时过早 . 以明显的方式(除以10),然后对其进行基准测试,并在需要时进行优化 . 转换为字符串表示并返回将慢得多 .

2 years ago

单独的toString()可能比子字符串慢 .

2 years ago

各种各样的人都说除以10将比转换为字符串和取子串更快 . 要理解原因,只需考虑从BigInteger转换为String所涉及的计算,反之亦然 . 例如:

/* simplified pseudo code for converting +ve numbers to strings */
StringBuffer sb = new StringBuffer(...);
while (number != 0) {
   digit = number % 10;
   sb.append((char)(digit + '0'));
   number = number / 10;
}
return sb.toString();

需要注意的重要一点是,从数字转换为字符串需要重复除以10.实际上,除法的数量与log10(数字)成正比 . 进入另一个方向涉及log10(数字)乘法 . 显而易见的是,这比单个除以10的计算要多得多 .

2 years ago

如果性能至关重要......不要使用java

在编译为机器代码的语言中(例如c或c),整数除法的速度要快得多 . 字符串操作使用(或可以使用)内存分配,因此很慢 .

我敢打赌,在java int中,分区也会更快 . 否则他们的vm实现真的很奇怪 .