Быстрое умножение очень больших чисел в perl

Question

У меня есть 50 000 номеров (может варьироваться от 0 до 50 000). И мне нужно (произведение этих чисел) MOD 1000000007. Следующий код настолько тривиален, должны быть другие способы. Слышал о методах «Разделить и побеждать», но понятия не имею, как их реализовать.

$ans *= ($_ % 1000000007) foreach @array; 
$ans %= 1000000007; 

Просьба предложить.

Answer 1

Хотя вы делаете $_ % 1000000007 на каждом номере вашего массива, ваш $ans может стать очень большим, пока вы, наконец, не сделаете $ans %= 1000000007 после просмотра.

Чтобы исправить это я предлагаю следующее:

foreach my $number (@array) 
{ 
    $ans *= ($number % 1000000007); 
    $ans %= 1000000007; 
} 

Answer 2

Результат $num % 1000000007 всегда будет $num для всех значений меньше, чем 1000000007. Так что, если все значения в @array находятся в диапазоне 0 .. 50000, такой расчет является избыточным. Вы должны сделать два шага, а не использовать *= оператора:

$ans = ($ans % 1000000007) * $_ for @array; 

Слово предостережения, хотя. Для любого несвязанного modulo всегда существует риск того, что ваша операция по модулю приведет к нулю, что, конечно же, вызовет полное умножение на нуль. Думаю, вы уже об этом подумали, так как 1000000007, кажется, простое число, но я все равно упомянул об этом.

ETA: Повторное использование промежуточных продуктов:

for (@array) { 
    $ans *= $_; 
    print "Before mod: $ans\n"; 
    $ans %= 1000000007; 
    print "After mod : $ans\n"; 
} 

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

Answer 3

Если вычислительное повторное использование является важным/ожидаемым (как указано в комментарии к ответу TLP), то memoizing функция поможет ускорить, эффективно запоминая ранее рассчитанные результаты.

См Chapter 3: Caching and Memoization in Higher-Order Perl