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

mickfrancis · 2016-02-08, 12:00

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 here.

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:

Originally Posted by mickfrancis

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

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

mickfrancis · 2016-02-08, 18:35

Quote:

Originally Posted by CRGreathouse

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

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 here).

mickfrancis · 2016-03-29, 14:26

Quote:

Originally Posted by jasonp

Msieve's NFS line sieve uses remainder-tree-based batch factoring to handle the factorization of huge numbers of relatively small integers.

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.

2016-02-08, 12:00	#1
mickfrancis Apr 2014 Marlow, UK 2³·7 Posts	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?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Widely varying LL test speeds after reboot	TrellisCross	Information & Answers	3	2016-11-14 14:22
Speeding up 321	diep	Math	8	2012-12-04 15:32
Speeding up Mersenne hunting	m_f_h	Math	8	2007-05-18 13:49
Benchmarks varying FSB, Memory Latency and multiplier	S485122	Software	0	2006-11-08 20:21
Speeding up ECM 10x	clowns789	Software	2	2004-08-11 03:45

2016-02-08, 12:52	#2
bgbeuning Dec 2014 3·5·17 Posts	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.

2016-02-08, 13:37	#3
jasonp Tribal Bullet Oct 2004 DD9₁₆ Posts	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 here.

2016-02-08, 14:13	#4
mickfrancis Apr 2014 Marlow, UK 2³·7 Posts	Thanks guys - will definitely investigate this approach.

2016-02-08, 17:40	#5
mickfrancis Apr 2014 Marlow, UK 56₁₀ Posts	Hi Jason, do you have a reference for the Remainder Tree approach?

2016-02-09, 13:38	#8
jasonp Tribal Bullet Oct 2004 5×709 Posts	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 here).

2016-03-29, 19:00	#10
jasonp Tribal Bullet Oct 2004 5×709 Posts	It does not and I have not.