Надежное умножение и модуль с числами больше, чем maxint

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

var numberOfColumns = 34359738368;
var numberOfRows = 28827050410;
var valueOverflow = 13719506;
var totalOfSingleRow = (numberOfColumns * (numberOfColumns - 1))/2;
var totalGridValue = totalOfSingleRow * numberOfRows;
var result = (totalOfSingleRow * totalGridValue) % valueOverflow;

Поскольку верхняя строка является последовательной, я могу вычислить сумму первой строки, выполнив (numberOfColumns * (numberOfColumns - 1))/2;.
Затем мне нужно умножить этот ответ на количество строк и применить модуль, чтобы получить результирующее значение.

Проблема
Проблема в том, что Javascript может вычислить надежность только с числом меньше 9007199254740991.
Только приведенный выше расчет дает totalGridValue из 17016487081526963049249353236480.
Вы можете себе представить, что мой расчет не приводит к желаемому значению 10552574, так как значение усекается до 1,7016487081526963e+31.
Это приводит к неправильному значению 8479672

Вопрос
Как я могу изменить свой расчет, чтобы результат стал желаемым 10552574.
Я пытался применить оператор по модулю раньше к numberOfColumns без желаемого результата.
Я' Я также рассматривал добавление двух больших значений в виде строк, но этот процесс стал бы медленным, так как мне приходилось добавлять две строки много раз.

Примечание
Поскольку мне нужно отправить это на codewars, я не могу использовать какие-либо внешние библиотеки!
Хотя я могу использовать другие языки, но я знаю, что это возможно в javascript.


performance algorithm modular-arithmetic
person Rick Hoving    schedule 26.01.2018    source источник
comment
Ну и важный трюк : (A*B)%M = ((A%M)*(B%M))%M.   -  person Sanket Makani    schedule 26.01.2018
comment
Это, безусловно, очень полезный трюк. Однако это непросто применить к такой величине, как (c * (c-1)/2) % n. Если вы примените это для c = 2 и n = 2, вы, безусловно, получите неправильный результат (0 вместо 1), а c = 13 и n = 8 (2 вместо 6) — еще один из многих случаев отказа.   -  person rwp    schedule 25.02.2018
comment
@rwp это работает, если вы сначала рассчитаете деление на 2, поэтому правильная формула будет c % n * ((c-1) / 2 % n) % n. При условии, что c-1 — четное число, если c-1 — нечетное число, формула (c-1) % n * (c / 2 % n) % n   -  person Rick Hoving    schedule 01.03.2018
comment
@RickHoving - Хороший вопрос, спасибо.   -  person rwp    schedule 04.03.2018

Ответы (2)


arrow_upward
1
arrow_downward

Я думаю, что вы были на правильном пути, переместив операцию по модулю дальше по цепочке, но я бы не стал использовать для этого оператор по модулю. Вместо этого используйте обычное деление с плавающей запятой и перенесите это значение на последний шаг, когда все остальные вычисления будут выполнены, а затем преобразуйте десятичную часть этого числа с плавающей запятой в целое число. По сути, при чистом делении вы просто выполняете преобразование значения, а не изменяете его. Как только вы перейдете к модулю, вы изменили значение. (Я бы также изменил формулу totalSingleRow, чтобы разделить большие значения, а затем умножить результаты, а не умножать, а затем делить.)

person Kevin Fichter    schedule 26.01.2018

arrow_upward
1
arrow_downward

Я согласен с тем, что перемещение операции модуля дальше вверх по цепочке является правильной основной идеей. Одна тонкость заключается в обработке вычисления totalOfSingleRow, потому что он включает в себя деление на два. Я думаю, что вам нужно выполнить этот этап по модулю (2 * valueOverflow) и только в конце вычислить результат по модулю valueOverflow. Возможно следующим образом:

var doubleOverflow = 2 * valueOverflow;
var totalOfSingleRow = (((numberOfColumns % doubleOverflow) * (numberOfColumns + doubleOverflow - 1)) / 2) % valueOverflow;
var totalGridValue = (totalOfSingleRow * (numberOfRows % valueOverflow)) % valueOverflow;
var result = (totalOfSingleRow * totalGridValue) % valueOverflow;

Вам нужно будет проверить, что (4 * valueOverflow*valueOverflow) меньше максимального целочисленного значения, которое может быть представлено правильно.

person rwp    schedule 25.02.2018