Работа с большими числами в Engee

Введение

Современные инженерные и научные задачи часто требуют вычислений, выходящих за пределы 64-битных целых и стандартной плавающей точки двойной точности. Криптография, теория чисел, комбинаторика, проверка простоты больших чисел — всё это сталкивается с необходимостью хранить и обрабатывать значения, которые не помещаются в стандартные типы. Julia предлагает элегантный и производительный подход к этой проблеме: встроенные типы Int128, UInt128, а также BigInt и BigFloat из стандартной библиотеки позволяют работать с большими числами без внешних зависимостей и без потери точности.

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

Присоединение библиотек

Подключим необходимые библиотеки:

MATLAB– для запуска Matlab-скриптов, сравнения синтаксиса и производительности;
Primes– для работы с простыми числами, в данной работе мы будем проверять, является ли большое число простым.

for pkg in (["MATLAB", "Primes"])
    try
        eval(Meta.parse("using $pkg"))
    catch
        Pkg.add(pkg)
        eval(Meta.parse("using $pkg"))
    end
end

Целочисленные типы фиксированной ширины и переполнение

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

print(Int8(127)+Int8(1))

-128

print(UInt8(255)+UInt8(1))

0

Знаковое переполнение даёт переход через ноль в отрицательную область, беззнаковое - циклический возврат к нулю. Это ожидаемое поведение, но оно напоминает: для больших значений нужны более расширенные типы.

Предел UInt128

Тип UInt128 позволяет хранить целые числа до .

Убедимся, что это значение представимо точно:

print(UInt128(340282366920938463463374607431768211455))

340282366920938463463374607431768211455

Однако прибавление единицы к максимальному UInt128 снова приводит к переполнению:

print(UInt128(340282366920938463463374607431768211455)+UInt128(1))

0

Это важный момент: даже 128-битный тип имеет жёсткий предел. Для выхода за него необходимы типы произвольной точности.

BigInt: произвольная точность

Преимущество Julia заключается в автоматическом повышение типа при работе с целочисленными литералами, выходящими за пределы Int64/UInt128. Достаточно написать длинное число, и Julia самостоятельно преобразует его BigInt. Выполним сложение и замерим время:

@time A = 340282366920938463463374607431768211455+1
display(A)

  0.000080 seconds (11 allocations: 504 bytes)

340282366920938463463374607431768211456

Результат точен. Время выполнения составило 80 микросекунд. Убедимся в типе и количестве цифр:

typeof(A)

BigInt

length(string(A))

39

Сравнение с MATLAB: неявная потеря точности

Аналогичное определение большого числа в MATLAB не работает корректно: числовой литерал сразу интерпретируется как double и теряет точность.

mat"""
A = 340282366920938463463374607431768211455 + 1;
format long
disp(A)
"""

>> >> >> >> >>      3.402823669209385e+38

Даже представление числа в MATLAB в качестве символьной переменной sym(...) не помогает, если аргумент является числовым литералом: число уже округлено до double на этапе парсинга, и sym получает искажённое значение.

mat"""
A = sym(340282366920938463463374607431768211455)+sym(1);
disp(A)
"""

>> >> >> >> 340282366920938463463374607431768211457

Результат вместо ожидаемого — наглядная иллюстрация потери точности. Правильный способ в MATLAB – сначала представить число в виде строки, затем в виде символьной переменной sym:

mat"""
tic
A = sym('340282366920938463463374607431768211455')+sym('1');
toc
disp(A)
"""

>> >> >> >> >> Elapsed time is 0.012461 seconds.
>> 340282366920938463463374607431768211456

Здесь результат верен, но обратите внимание на время: около 12.46 миллисекуунд. В Julia аналогичная операция заняла 80 микросекунд. Аналогично, в MATLAB можно использовать функцию vpa() (Variable-Precision Arithmetic), но тогда данная операция будет выполняться ещё медленнее:

mat"""
digits(50)
tic
A = vpa('340282366920938463463374607431768211455') + vpa('1');
toc
disp(A)
"""

>> >> >> >> >> >> Elapsed time is 0.094311 seconds.
>> >> 340282366920938463463374607431768211456.0

Время выполнения заняло более 94 миллисекунд. Таким образом, в Julia переход к произвольной точности происходит естественно на уровне синтаксиса, тогда как в MATLAB требуется явное преобразование через строку, это преобразование ещё и заметно медленнее.

BigFloat: точность плавающей точки произвольной длины

Тип BigFloat обеспечивает плавающую точку с настраиваемой точностью. Однако здесь есть важная тонкость: преобразование уже округлённогоFloat64 в BigFloat не восстанавливает потерянную точность, оно лишь переупаковывает приближение.

B = 340282366920938463463374607431768211457.0 + 2.0
print(B)

3.402823669209385e38

Литерал с .0 был сначала приведён к Float64, и точность уже потеряна. Преобразование big(B) не помогает:

B = big(B)

3.40282366920938463463374607431768211456e+38

typeof(B)

BigFloat

Обратите внимание: big(B) даёт 3.40282366920938463463374607431768211456e+38, что соответствует 2¹²⁸, а не исходному значению. Это прямое следствие того, что литерал с .0 был сначала приведён к Float64. Чтобы получить истинную точность, нужно использовать строку или макрос big"...":

B = big"340282366920938463463374607431768211457.0" + big"2.0"

3.40282366920938463463374607431768211459e+38

Числовое сравнение и идентичность

Интересный эффект: BigInt и BigFloat, представляющие одно и то же числовое значение, равны по ==, но не тождественны по ===:

B = B - big"3.0"
A == B

true

A === B

false

Это иллюстрирует фундаментальное различие между абстрактным равенством значений и программной неразличимостью объектов (тип и битовое представление).

Производительность: проверка простоты больших чисел

Одна из практически важных операций с большими числами — проверка на простоту (то есть проверка: делится ли число только само на себя и на единицу). Сравним производительность Julia и MATLAB на числе . Определим данное число и узнаем количество цифр.

N = big(2)^big(521)-big(1)
length(string(N))

157

Проверим, является ли число простым с помощью функции Julia isprime() (библиотека Primes):

@time isprime(N)

  0.000475 seconds (7 allocations: 2.781 KiB)

true

С помощью MATLAB (vpa() Symbolic Math Toolbox):

mat"""
digits(160)
N = vpa('2')^vpa('521')-vpa(1);
tic
isprime(N)
toc
"""

>> >> >> >> >> >> 
ans =

  logical

   1

>> Elapsed time is 6.366448 seconds.

true

С помощью (sym() Symbolic Math Toolbox):

mat"""
N = sym('2')^sym('521')-sym(1);
tic
isprime(N)
toc
"""

>> >> >> >> >> 
ans =

  logical

   1

>> Elapsed time is 7.127730 seconds.

true

Julia выполняет проверку простоты числа значительно быстрее обоих вариантов MATLAB: isprime(N) в Julia заняла около 475 микросекунд (0.000475 с), тогда как в MATLAB с vpa() — 6.37 секунды, а с sym() — 7.13 секунды. Для задач, где проверка простоты выполняется в цикле, такая разница превращает минуты вычислений в миллисекунды.

Заключение

Проведённое исследование демонстрирует три ключевых преимущества Julia при работе с большими числами:

Синтаксическое удобство и безопасность точности. В Julia длинный целочисленный литерал автоматически становится BigInt, тогда как в MATLAB числовой литерал сначала теряет точность как double, и только преобразование через строку в sym/vpa даёт корректный результат. Это устраняет целый класс ошибок, связанных с неявным округлением.
Прозрачное поведение переполнения. Типы Int8, UInt8, UInt128 ведут себя предсказуемо (по модулю ), а переход к BigInt/BigFloat происходит естественно, когда это необходимо.
Высокая производительность, растущая с разрядностью. На сложении больших чисел Julia быстрее MATLAB примерно в 155 раз (против sym) и в 1 180 раз (против vpa). На проверке простоты 521-битного числа разрыв достигает 13 000–15 000 раз (0.475 мс против 6.37 с и 7.13 с).

Данное исследование применимо в различных областях: оно даёт криптографам и специалистам по кибербезопасности ускорение проверки простоты чисел, напрямую влияющее на генерацию ключей в RSA и при подборе параметров эллиптических кривых, разработчикам, переходящим с MATLAB на Julia защиту от ошибок с double-литералами и оценку выигрыша в лаконичности и скорости, а в академической среде компактную иллюстрацию различий между арифметикой фиксированной и произвольной точности и между == и ===, и в целом представляет собой не только теоретическое понимание, но и готовый практический инструмент для решения реальных инженерных задач.

Большие числа

Работа с большими числами в Engee

Введение

Присоединение библиотек

Целочисленные типы фиксированной ширины и переполнение

Предел UInt128

BigInt: произвольная точность

Сравнение с MATLAB: неявная потеря точности

BigFloat: точность плавающей точки произвольной длины

Числовое сравнение и идентичность

Производительность: проверка простоты больших чисел

Заключение

Тип

Краткое описание

Связанные материалы

Теги

Категории

Языки

Форматы

Уровень

Статус

Опубликовано

Обновлено

Источник