нет явного цикла для вычисления произведения списка по некоторому модулю в Mathematica

Question

В Mathematica, должен ли я использовать явный цикл для вычисления произведения элементов в данном списке (потенциально очень длинном) по модулю на другое число?

Пожалуйста, научите меня своему элегантному подходу, если у вас есть. Спасибо!

Редактировать

Просто для примера

list=Range[2000];Mod[Product[list],32327]

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

Редактировать 2

Полагаю, мой вопрос связан с тем, как заменить цикл на

.

Module[{ret = initial_value}, For[i = 1, i <= Length[list], i++, ret = general_function[list[[i]],ret]; ret]

с учетом общей функции general_function и списка list.

Answer 1

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

Вот пример. Мы будем использовать список из 10 ^ 6 целых чисел, все от 0 до 10 ^ 10.

SeedRandom[1111111];
len = 6;
max = 10;
list = RandomInteger[10^max, 10^len];

Умножение и взятие модуля для немного большего мода (я хотел уменьшить вероятность того, что результат будет нулевым):

In[119]:= Timing[Mod[Times @@ list, 32327541]]

Out[119]= {1.360000, 8826597}

Вот вариант, который я описал. Методика проб и ошибок указала, что списки длиной 2 ^ 9 или около того лучше всего составлять нерекурсивно, по крайней мере для чисел в диапазоне размеров, указанном выше.

tmod2[ll_List, m_] := With[{len=Floor[Length[ll]/2]},
  If[len<=256,
    Mod[Times @@ ll, m],
    Mod[tmod2[Take[ll,len],m] * tmod2[Drop[ll,len],m], m]]]

In[120]:= Timing[tmod2[list, 32327541]]

Out[120]= {0.310000, 8826597}

Когда я увеличиваю длину списка до 10 ^ 7 и разрешаю целые числа от 0 до 10 ^ 20, первый метод занимает 50 секунд, а второй - 5 секунд. Очевидно, что масштабирование работает нам на пользу.

Для ситуаций, когда итерация, чередующая две операции, может быть предпочтительнее, чем разделяй и властвуй, можно использовать Fold, как показано ниже.

tmod3[ll_List, m_] := Fold[Mod[#1*#2,m]&, First[ll], Rest[ll]]

Хотя он и не конкурирует с tmod2 в длинных списках, это быстрее, чем умножение всего до запуска Mod. Для длины 10 ^ 7 и максимального элемента 0f 10 ^ 20 требуется примерно 8 секунд, чтобы сделать то, что сделал tmod2 в 5.

Answer 2

Почему бы не использовать Times? Следующие

list=Range[2000];
Mod[Times@@list,32327]

, вероятно, будет самым эффективным. Из недавнего сообщения в блоге WRI ,

Times знает хитрый прием двоичного разбиения, который можно использовать, когда у вас есть большое количество целочисленных аргументов. Рекурсивно разбивать аргументы на два меньших продукта быстрее (1 * 2 *… 32767) (32768 *… * 65536), а не обрабатывать аргументы от первого до последнего. Он все еще должен делать то же количество умножений, но меньшее количество из них включает очень большие целые числа, и поэтому, в среднем, быстрее сделать

Я предполагаю, что list в вашем вопросе является лишь примером. Если вам действительно нужно взять произведение n последовательных целых чисел, начинающихся с 1, то Factorial будет самым быстрым. то есть.,

Mod[2000!, 32327]

Answer 3

Это в два раза быстрее, чем код Даниэля в моей системе:

SeedRandom[1];
list = RandomInteger[1*^20, 1*^7];
m = 32327501;

Mod[Times @@ Mod[Times @@@ Partition[list, 50, 50, 1, {}], m], m] // AbsoluteTiming

tmod2[list, m] // AbsoluteTiming

{1.5800904, 21590133}

{3.1081778, 21590133}

Для настройки этой системы и рабочего набора можно использовать разные длины разделов.