Простые факторизации

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

Встроенные целые типы MATLAB подходят для целых чисел меньше 2 ^ 64. Однако мы хотим провести статистические исследования простых факторизаций больших целых чисел. Для этого мы используем символические целые числа, потому что их размер неограниченен. Исследуйте целые числа между$$N_0+1$$ и $$N_0+100$$, где $$N_0=3*10^{23}$$. Встроенные типы данных не могут точно хранить такие значения. Таким образом, оберните самое внутреннее число 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