mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Computer Science & Computational Number Theory (https://www.mersenneforum.org/forumdisplay.php?f=116)
-   -   Speeding up (n mod m) for very large fixed n and varying smaller m (https://www.mersenneforum.org/showthread.php?t=20971)

 mickfrancis 2016-02-08 12:00

Speeding up (n mod m) for very large fixed n and varying smaller m

I have a large fixed n (around 100,000 digits, say) and need to calculate (n mod m) for many different values of m, which are smaller (tens of digits). Is there is any preconditioning I can use, or any transformations that might be applied to speed this process up at all?

 bgbeuning 2016-02-08 12:52

Sometimes it helps to multiply all the modulo together (M) and compute

X = n mod M

then

x[i] = X mod m[i]

is easier. But your m[i] sound too big for this to help.

 jasonp 2016-02-08 13:37

The recursive version of the above is a 'remainder tree', and is indeed a good idea. If the product of the m's far exceeds the size of n you can do the remainder tree tree a block of m's at a time, possibly combined with the fast small-m modulo operation described [url="http://arxiv.org/pdf/1303.0328.pdf"]here[/url].

 mickfrancis 2016-02-08 14:13

Thanks guys - will definitely investigate this approach.

 mickfrancis 2016-02-08 17:40

Hi Jason, do you have a reference for the Remainder Tree approach?

 CRGreathouse 2016-02-08 18:12

[QUOTE=mickfrancis;425634]Hi Jason, do you have a reference for the Remainder Tree approach?[/QUOTE]

I'm not Jason but I think Bernstein is standard here:
[url]https://cr.yp.to/arith/scaledmod-20040820.pdf[/url]

 mickfrancis 2016-02-08 18:35

[QUOTE=CRGreathouse;425641]I'm not Jason but I think Bernstein is standard here:
[url]https://cr.yp.to/arith/scaledmod-20040820.pdf[/url][/QUOTE]
Great - thanks very much.

 jasonp 2016-02-09 13:38

Bernstein's paper is probably the best theoretical reference; remainder trees are only one of the algorithms it describes.

Msieve's NFS line sieve uses remainder-tree-based batch factoring to handle the factorization of huge numbers of relatively small integers, and this lets the sieve use three large primes without the traditional overhead of doing so (code [url="http://sourceforge.net/p/msieve/code/HEAD/tree/trunk/common/batch_factor.c"]here[/url]).

 mickfrancis 2016-03-29 14:26

[QUOTE=jasonp;425721]Msieve's NFS line sieve uses remainder-tree-based batch factoring to handle the factorization of huge numbers of relatively small integers.[/QUOTE]

Hi Jason,

Do you use Bernstein's Scaled Remainder Trees? If not, have you experimented with them at all?

Mick.

 jasonp 2016-03-29 19:00

It does not and I have not.

 All times are UTC. The time now is 01:20.