Первичные факторизации

В этом примере показано, как использовать некоторые элементарные функции на sym с помощью Toolbox™ Символьная математика (Symbolic Math).

Встроенные целочисленные типы MATLAB подходят для целых чисел, меньших 2 ^ 64. Однако мы хотим провести статистические исследования простых факторизаций больших целых чисел. Для этого мы используем символические целые числа, потому что их размер неограничен. Исследуйте целые числа $${\mathrm{между}}_{\mathrm{}}\mathrm{N0}$$ + 1 $${}_{\mathrm{}}и\mathrm{}\mathrm{}\mathrm{N0}$$+ 100, $${}_{\mathrm{}}\mathrm{}где\mathrm{}{\mathrm{}}^{\mathrm{N0}\mathrm{}}$$= 3 * 1023. Встроенные типы данных не могут точно хранить такие значения. Таким образом, оберните самое внутреннее число наsym для использования символического представления в расчетах. Это позволяет избежать ошибок округления или переполнения:

N0 = 3*sym(10)^23;
disp(['Roundng error for doubles: ' char(3*10^23 - N0)]);

Roundng error for doubles: -25165824

disp(['Overflow error for integers: ' char(3*uint64(10)^23 - N0)]);

Overflow error for integers: -299981553255926290448385

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

A = N0 + (1:100);

Вычислить простые факторизации элементов A использование factor. Количество простых факторов различается. Массивы не могут содержать векторы разной длины, но массивы ячеек могут. Чтобы избежать повторного выделения памяти, сначала инициализируйте массив ячеек, а затем вычислите факторизации в цикле:

Bcell = cell(1, 100);
for i=1:100
   Bcell{i} = factor(A(i)); 
end

Более эффективный подход заключается в использовании arrayfun. Настройка UniformOutput кому false возвращает результат в виде массива ячеек.

Bcell = arrayfun(@factor, A, 'UniformOutput', false);

Например, первые простые факторизации:

Bcell{1:5}

ans = $$\left(\begin{array}{cccc}13& 43& 233& 2303316007278478583\end{array}\right)$$

ans = $$\left(\begin{array}{ccccccc}2& 17& 173& 991& 1223& 244939& 171805943\end{array}\right)$$

ans = $$\left(\begin{array}{cccccc}3& 11& 47& 139& 2531& 549797184491917\end{array}\right)$$

ans = $$\left(\begin{array}{ccccc}2& 2& 330131& 2953837& 76910994983\end{array}\right)$$

ans = $$\left(\begin{array}{cccc}5& 6271& 2650266823& 3610146697\end{array}\right)$$

Получение наибольшего простого коэффициента с помощью max. Обратите внимание, что если выходные данные состоят из объектов sym, опция UniformOutput всегда должно быть задано значение false даже если выходные данные однородны.

Mcell = cellfun(@max, Bcell, 'UniformOutput', false);

Например, первые максимальные простые множители:

Mcell{1:5}

ans = $$2303316007278478583$$

ans = $$171805943$$

ans = $$549797184491917$$

ans = $$76910994983$$

ans = $$3610146697$$

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

M = [Mcell{:}];
histogram(double(log(M)./log(A)), 20);
title('Ratio of lengths of the largest prime factor and the number');

Таким же образом, теперь исследовать распределение числа простых факторов. Здесь результат содержит однородные числовые данные. Поэтому устанавливать не нужно UniformOutput кому false.

omega = cellfun(@numel, Bcell);
histogram(omega);
title('Number of prime factors');

Исследуемый интервал содержит два простых числа:

A(omega == 1)

ans = $$\left(\begin{array}{cc}300000000000000000000037& 300000000000000000000049\end{array}\right)$$

Мы проверяем, что максимальные простые коэффициенты примерно одинаково часто в классах остатков 1 и 3 по модулю 4. Следует отметить, что уравнения объектов sym являются собственно символическими объектами, а не логическими значениями; мы должны преобразовать их, прежде чем суммировать:

sum(logical(mod(M, 4) == 1))

ans = 49

sum(logical(mod(M, 4) == 3))

ans = 51