Понимание использования BigInt

Я изо всех сил пытаюсь понять, как правильно использовать BigInt. Мне кажется, что нужно использовать BigInt, когда Int64 или Int128 недостаточно, и, по-видимому, BigInt использует арифметику произвольной точности (о которой я ничего не знаю).

Допустим, я хочу вычислить факториал некоторого большого числа, например. 30. Я не знаю, сколько битов требуется для хранения factorial(30), но оба

test = Int128
test = factorial(30)

а также

test = BigInt
test = factorial(30)

выдает -8764578968847253504, что явно неверно.

Согласно документации Julia lang, кажется, что для этого типа (BigInt) определены обычные математические операторы, а результаты повышаются до BigInt. Поэтому я не вижу, что я делаю неправильно, я явно что-то неправильно понял. Надеюсь, у кого-то из вас есть объяснение для меня :)

PS: я использую 64-битную версию Windows 7, если это что-то говорит


person kip820    schedule 07.10.2014    source источник


Ответы (3)


factorial будет вычислять результат того же типа, что и его аргумент, поэтому

test = factorial(BigInt(30))  

Будет работать, во время вычислений будет использоваться BigInt.

test = BigInt(factorial(30))

Не сработает, преобразует уже переполненный результат Int в BigInt.

test = BigInt(factorial(BigInt(30)))

Будет работать, но внешний BigInt избыточен, так как результат уже является BigInt.

Код, который вы написали

test = BigInt
test = factorial(30)

по сути бессмысленно. Вы сказали

Согласно документации Julia lang, кажется, что для этого типа определены обычные математические операторы (BigInt), а результаты повышаются до BigInt.

поэтому я предполагаю, что вы думали, что это означает, что «результат должен быть BigInt», но это не так. Он присваивает тип BigInt переменной test, затем вычисляет factorial для литерала Int 30. Затем он сохраняет его в test, уничтожая предыдущее значение, которое было BigInt. Возможно, ознакомьтесь с разделом «Типы» руководства. Джулия не повышает автоматически Ints до BigInts при переполнении — вам нужно начать с BigInt. Это связано с производительностью (и другими) причинами.

Большинство операций определены на BigInts — только некоторые операции линейной алгебры (например, собственные значения) могут не быть. Просто измените свое число на BigInt один раз, и оно будет распространяться на протяжении всего вычисления. Большинству людей никогда не понадобятся BigInts — они, как правило, возникают только в исследовательской среде. Int (что соответствует целочисленному размеру платформы, поэтому Int64 на вашем компьютере) довольно большой и быстрый.

person IainDunning    schedule 07.10.2014
comment
Спасибо за объяснение, имеет смысл, с этого момента будем придерживаться явного приведения при работе с BigInts :) - person kip820; 07.10.2014

Связанный вопрос о математике произвольной точности. Обратите внимание, что я провел всего два дня, экспериментируя с языком Julia. После просмотра этой публикации я добавил кастинг BigInt, который распечатал еще одно число. Я должен что-то упустить, поскольку он все еще не выполняется, как будто он использует произвольную точность для всех необходимых вычислений. Мне также пришлось добавить try/catch, так как функция ismersenneprime выдает ошибку, если это не простое число Mersene. Согласно документации, я думал, что он должен возвращать true или false.

# Perfect numbers are 2^(p-1)x(2^p-1) if 2^p-1 is Mersenne prime.
using Compat
using Primes

limit = 1000000

for p = 1:limit
  perfect = BigInt(2^(p-1))*(BigInt(2^p)-1)
  try 
    if ismersenneprime(BigInt(2^p)-1)
      println("$p $perfect")
    end
  catch e
#   println(e)
  end
end

2 6
3 28
5 496
7 8128
13 33550336
17 8589869056
19 137438691328
31 2305843008139952128
61 2658455991569831744654692615953842176
person user3316586    schedule 10.09.2018
comment
Думаю, я также не осилил публикацию здесь, так как он полностью стер форматирование. Можно ли в будущем просто использовать теги HTML; как ‹pre› ‹/pre›? - person user3316586; 10.09.2018
comment
Наконец-то я заставил его работать, переопределив limit как limit = BigInt(typemax(Int128)) + 1 - person user3316586; 12.09.2018

Я хочу поставить перед этим ответом утверждение, что я ничего не знаю о Джулии, но читаю документацию по адресу https://docs.julialang.org/en/v1/manual/integers-and-floating-числовыеточки/#Произвольная-Точность-Арифметика-1 видно, что они используют factorial(BigInt(40)), поэтому явное приведение типов кажется необходимым.

Попробуйте factorial(BigInt(30)), чтобы увидеть, дает ли это ожидаемый результат.

Также с этой страницы:

Однако повышение типов между примитивными типами, указанными выше, и типами BigInt/BigFloat не является автоматическим и должно быть указано явно.

Итак, я бы попробовал 3 вещи, чтобы увидеть, что работает:

test = factorial(BigInt(30))
test = BigInt(factorial(30))
test = BigInt(factorial(BigInt(30)))
person anothershrubery    schedule 07.10.2014
comment
Спасибо. работал. На самом деле это имеет большой смысл, поскольку большинство функций в Julia полиморфны (думаю, я правильно использую полиморфность), поэтому, когда factorial получает тип BigInt, он также возвращает тип BigInt, в отличие от того, что я сделал сначала, который кормил его типом Int - person kip820; 07.10.2014
comment
Чтобы уточнить, сработало явное приведение, первый пример в вашем списке работал отлично, другие не пробовал - person kip820; 07.10.2014
comment
Просто замечу, что в Джулии, если я правильно понимаю, BigInt(30) не является кастингом, а также не преобразованием или продвижением (хотя эти операции возможны в Джулии). Вы фактически вызываете конструктор. Руководство объясняет это и многое другое. - person rickhg12hs; 07.10.2014