Java BigInteger, обрезать последнюю цифру

Question

Довольно просто, если число BigInteger равно 543, я хочу, чтобы оно обрезало последнюю цифру до 54.

Два простых способа сделать это могут быть:

1. Используйте строки, получите подстроку и создайте новый biginteger с новым значением.
2. Используйте метод деления BigIntegers с номером 10. (543/10 = 54.3 => 54)

Дело в том, что я буду выполнять это много раз с большими целыми числами, конечно.

Я предполагаю, что играть со строками будет медленнее, но опять же, я не так много использовал Bigintegers и понятия не имею, сколько стоит операция "делить".

Здесь важна скорость, какой самый быстрый способ реализовать это (память не проблема, только скорость)?

Другие решения также приветствуются.

Answer 1

Деление на 10 скорее всего будет быстрее.

Answer 2

Деление на 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));

Answer 3

Если вы создадите статически BigInteger с номером 10, а затем используете его для деления на 10, это будет потенциально самый быстрый способ сделать это. Каждый раз он превосходит создание нового временного BigInteger.

Проблема с подстрокой заключается в том, что вы по сути создаете новую строку каждый раз, и это намного медленнее, не говоря уже о медлительности, которая проходит через строку для получения ее подстроки.

Answer 4

Различные люди говорили, что деление на 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.

Answer 5

ToString () один, вероятно, медленнее, чем подстрока.

Answer 6

Вероятно, преждевременно даже задавать этот вопрос. Сделайте это очевидным способом (разделите на десять), затем сравните его и оптимизируйте, если вам нужно. Преобразование в строковое представление и обратно будет намного медленнее.

Answer 7

Самая быстрая реализация, вероятно, заключалась бы в использовании типа данных, внутреннее представление которого использует основание 10, т. Е. Своего рода BCD . Тогда деление на 10 будет просто означать удаление последнего байта (или даже просто увеличение / уменьшение индекса, если вы правильно его реализуете).

Конечно, вам придется выполнять все необходимые арифметические и другие операции с нуля, что делает это большой работой.

Answer 8

если производительность имеет решающее значение ... не используйте Java

В языках, которые компилируются в машинный код (например, c или c ++), деление целых чисел быстрее на огромный фактор. Строковые операции используют (или могут использовать) выделения памяти и поэтому медленны.

Моя ставка в том, что в java int деления тоже будут быстрее. Иначе их реализация vm действительно странная.

Answer 9

Самый быстрый способ - разделить число на 10 с эффективной реализацией внутреннего деления. Внутренние элементы этой операции находятся за кадром, но, конечно, нетривиально, поскольку число хранится в base-2.