mersenneforum.org Speeding up (n mod m) for very large fixed n and varying smaller m
 Register FAQ Search Today's Posts Mark Forums Read

 2016-02-08, 12:00 #1 mickfrancis   Apr 2014 Marlow, UK 23×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?
 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 67318 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 23·7 Posts Thanks guys - will definitely investigate this approach.
 2016-02-08, 17:40 #5 mickfrancis   Apr 2014 Marlow, UK 708 Posts Hi Jason, do you have a reference for the Remainder Tree approach?
2016-02-08, 18:12   #6
CRGreathouse

Aug 2006

3×1,993 Posts

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

2016-02-08, 18:35   #7
mickfrancis

Apr 2014
Marlow, UK

5610 Posts

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.

 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, 14:26   #9
mickfrancis

Apr 2014
Marlow, UK

23·7 Posts

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.

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

 Similar Threads Thread Thread Starter Forum Replies Last Post TrellisCross Information & Answers 3 2016-11-14 14:22 diep Math 8 2012-12-04 15:32 m_f_h Math 8 2007-05-18 13:49 S485122 Software 0 2006-11-08 20:21 clowns789 Software 2 2004-08-11 03:45

All times are UTC. The time now is 17:36.

Wed Aug 10 17:36:47 UTC 2022 up 34 days, 12:24, 4 users, load averages: 1.60, 1.36, 1.32