Блог

Главная - Вопросы по программированию - Реализации больших целых чисел с неограниченной точностью в Java

Реализации больших целых чисел с неограниченной точностью в Java

#java #data-structures #biginteger

#java #структуры данных #biginteger

Вопрос:

В настоящее время я работаю на Java 11, я вижу, что BigInteger имеет базовое представление, в котором само число хранится в an int[] .
Конечно, для индексации an int[] необходимо ограничить размер массива Integer.MAX_VALUE , это реализовано в исходном коде для текущей BigInteger реализации, если вы превысите это значение, вы получитеисключение ArithmeticException("BigInteger would overflow supported range") .
Я понимаю, что мы говорим здесь о действительно огромных числах (2^32)^(2^32) (заданные целые числа хранятся в 4 байтах), которые дают или принимают бит нечетного знака. Но в этом мире облачных вычислений и микросервисов я уверен, что существуют приложения для вычисления с точными целыми числами, превышающими это значение.

Знает ли кто-нибудь о каких-либо реализациях (в Java) для ReallyBigInteger, у которого нет этого ограничения.

Моей первой мыслью было бы использовать базовое представление, подобное деревьям RedBlack (например, Redblack-tree) с конечными узлами, содержащими эту часть значения.

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

Мне интересно услышать.

Комментарии:

1. Какое отношение облачные вычисления имеют к большим числам? Вам просто нужен какой-то уникальный идентификатор для какой-то цели или есть математическая проблема, которую вы пытаетесь решить?

2. Повторные облачные вычисления: я больше думал, что это решит / смягчит проблему нехватки памяти / памяти на устройстве для хранения такого большого значения. Что касается причины, я больше думал, что математические проблемы будут более вероятными вариантами использования, хотя что-то может появиться в других случаях. Для меня это было больше интереса.

3. Единственное приложение, которое я когда-либо видел для действительно огромных целых чисел, которые приближаются к размеру, который вы упоминаете, — это очень узкая область исследований теории вычислительных чисел. Этот фрагмент определенно слишком мал для разработчиков Java, чтобы модифицировать код для поддержки больших целых чисел. Большинство из этих исследователей в любом случае используют чрезвычайно тщательно настроенный вручную машинный код для своей работы, а не Java. Тем не менее, должна быть возможность иметь ReallyBigInteger класс, который использовал int[][] , другими словами, массив массивов int[] , который увеличивал бы размер целых чисел до максимума почти в 2 ** 69 бит.

4. Это int[] . Итак (2^32)^(2^32) или 8 ГБ памяти для одного номера. Я бы счел большие числа довольно экзотическими. А стандартная библиотека предназначена для масс. Если нужно большее число, это все еще возможно реализовать.

5. Это маловероятно по причинам, упомянутым выше. Большая часть интересных усилий, похоже, сосредоточена на ускорении библиотеки BigInteger .