Java: деление BigInteger на представление 3 / Base 3

Question

Мне нужен быстрый способ деления BigInteger (1000 байт) на 3. Поскольку сдвиг не работает, я должен использовать divAndReminder (). Есть ли лучший / более быстрый вариант? Я использую это часто, так что чаще всего Jit оптимизирует его.

Answer 1

Беззнаковое деление на 3 можно выполнить умножением на 0xAA ... AA + 1, сдвиг вправо n + 1 , где n - количество бит в умножителе и n - кратное 8 (или 4).

Чтобы минимизировать стоимость, для данного дивиденда требуется множитель n , где n = длина дивиденда, округленная до кратного 8. Я думаю, это то, что делает private exactDivideBy3(). [Чтобы построить множитель для данного дивиденда, вы можете начать с 0xAA ... AA для самого большого дивиденда, с которым вам нужно справиться, затем сдвинуть вправо и / или в 1. Вы можете сохранить их в таблице.]

Конечно, вы можете округлить n до кратного 64, если предположите, что BigInteger запускает 64 бита за раз.

Answer 2

В то время как 1000 байтов, по-видимому, не оправдывают переход к крайним значениям (преобразование радиуса Шёнхаге), один из подходов состоит в том, чтобы разбить BigInteger на части, которые легко обрабатываются - 3 ^ 20 или 3 ^ 40 выглядят кандидатами, и преобразовать в 3 оттуда.