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

Question

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

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

Пожалуйста, предложите.

Answer 1

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

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

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

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

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

Примечаниечто вам не нужно составлять здесь операторы.

Answer 2

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

См. Глава 3: Кэширование и запоминание в Perl высшего порядка

Answer 3

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

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

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