Что означает BigInteger без ограничений?

Я изучил этот вопрос о переполнении стека, относящийся к Big Integer, и конкретно я не понимаю эту строку ( слова курсивом):

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

Я не знаю, чего мне не хватает, но для представления чего-то безграничного вам потребуется бесконечная память? В чем тут подвох?


java integer-overflow biginteger
person Geek    schedule 23.08.2012    source источник
comment
См. также: stackoverflow.com/a/12693333/829571   -  person assylias    schedule 02.02.2017

Ответы (4)


arrow_upward
87
arrow_downward

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

Однако существуют некоторые практические ограничения, продиктованные доступной памятью. И есть дополнительные технические ограничения, хотя вряд ли вы будете затронуты: некоторые методы предполагают, что биты адресуются int индексами, поэтому все начнет ломаться, когда вы превысите Integer.MAX_VALUE бит.

person Graham Borland    schedule 23.08.2012
comment
Таким образом, это очень похоже на String или byte[] (хотя я думаю, что они технически ограничены элементами с целочисленной адресацией). - person Thilo; 23.08.2012
comment
@Thilo: как и BigInteger: данные хранятся в int[], что накладывает теоретический предел на размер чисел, которые он может представлять. - person Michael Borgwardt; 23.08.2012
comment
Я слышал, что работа над длинными массивами ведется (и мне интересно, кому это нужно) ;-) - person Thilo; 23.08.2012
comment
@Thilo Что вы имеете в виду под этим очень похоже на строку или байт [] (хотя я думаю, что они технически ограничены элементами с целочисленной адресацией). - person Geek; 23.08.2012
comment
@MichaelBorgwardt Резервный массив int[] наверняка является деталью реализации, а не заданным поведением, не так ли? - person Graham Borland; 23.08.2012
comment
@MichaelBorgwardt Каков пороговый предел для int[]? Разве массив не растет настолько, насколько может расти? Как бы long[] решил это? - person Geek; 23.08.2012
comment
Может ли он использовать 128-битную адресацию памяти? - person huseyin tugrul buyukisik; 23.08.2012
comment
@Geek: как и String, он (на самом деле) ограничен только тем, сколько у вас памяти. Есть и некоторые технические ограничения, но если вы их достигнете, вы, вероятно, уже выйдете за рамки практических вариантов использования. - person Thilo; 23.08.2012
comment
В настоящее время массив в Java может содержать только 2 ^ 32 элемента. Некоторые люди хотят 2^64. BigInteger хранит свои биты в int[], поэтому сейчас он может хранить не более 2^32 int, т.е. 2^37 бит. Довольно большой. - person Thilo; 23.08.2012
comment
@Thilo На самом деле это очень полезная вещь, когда вы хотите работать с огромными файлами в памяти. Установленная оперативная память современных машин действительно начинает показывать искусственный предел Integer.MAX_VALUE размера файлов, которые могут быть обработаны таким образом. - person Marko Topolnik; 23.08.2012
comment
@Graham Borland: поддержка int[] является деталью реализации, но API BigInteger имеет несколько методов, использующих параметры int для доступа к n-му биту, а методы toString() косвенно ограничивают теоретическую величину реализации BigInteger, поскольку число должно быть представляется как строка. Из-за этого BigInteger не может быть больше 2 ^ (2 ^ 31-1)-1, что намного меньше ограничения, налагаемого резервным массивом int. - person jarnbjo; 23.08.2012
comment
Отредактированный ответ, чтобы учесть внутреннюю проблему. - person Graham Borland; 23.08.2012

arrow_upward
17
arrow_downward

Грэм дал отличный ответ на этот вопрос. Я хотел бы только добавить, что вы должны быть осторожны с методом valueOf, потому что он создается с использованием параметра long, поэтому максимальное значение равно Long.MAX_VALUE.

person Adam Sznajder    schedule 23.08.2012
comment
Тот, который принимает длинный параметр, очевидно, не может выйти за его пределы, но есть конструкторы, которые принимают строки или массивы байтов. - person Thilo; 23.08.2012
comment
Нет общедоступного конструктора, который принимает long в качестве аргумента. Есть только геттер (с предупреждениями о потере информации в документации). - person martijno; 23.08.2012
comment
На самом деле не нужно быть осторожным, так как метод BigInteger.valueOf(long) даст вам ошибку компиляции, если вы попытаетесь написать литерал, превышающий Long.MAX_VALUE. Кроме того, легко построить BigInteger намного больше, скажем, BigInteger.valueOf(10).pow(10000) - person leonbloy; 10.01.2014

arrow_upward
6
arrow_downward

Да, он используется, когда нам нужны очень большие числа с произвольной точностью. Важно отметить, что «произвольная» точность или количество цифр не означает «неограниченность»: это означает, что количество цифр в числе или количество цифр точности в расчете ограничено памятью и/или определенными пределами точности. что мы указываем.

person Eduard    schedule 23.08.2012

arrow_upward
3
arrow_downward

Посмотрите на исходный код класса BigInteger, вы увидите (это можно сделать с помощью NetBean). Число будет представлено в виде массива int. Например, 10113 будет [1, 0, 1, 1, 3] (это не совсем то, что делает класс BigInteger, просто пример того, как работает модуль больших чисел). Так что технически единственным ограничением будет ваша память.

person Vũ Mạnh Cường    schedule 27.11.2016