mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2016-02-08, 12:00   #1
mickfrancis
 
Apr 2014
Marlow, UK

23×7 Posts
Default 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?
mickfrancis is offline   Reply With Quote
Old 2016-02-08, 12:52   #2
bgbeuning
 
Dec 2014

3·5·17 Posts
Default

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.
bgbeuning is offline   Reply With Quote
Old 2016-02-08, 13:37   #3
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,181 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2016-02-08, 14:13   #4
mickfrancis
 
Apr 2014
Marlow, UK

23×7 Posts
Default

Thanks guys - will definitely investigate this approach.
mickfrancis is offline   Reply With Quote
Old 2016-02-08, 17:40   #5
mickfrancis
 
Apr 2014
Marlow, UK

1110002 Posts
Default

Hi Jason, do you have a reference for the Remainder Tree approach?
mickfrancis is offline   Reply With Quote
Old 2016-02-08, 18:12   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by mickfrancis View Post
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
CRGreathouse is offline   Reply With Quote
Old 2016-02-08, 18:35   #7
mickfrancis
 
Apr 2014
Marlow, UK

5610 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I'm not Jason but I think Bernstein is standard here:
https://cr.yp.to/arith/scaledmod-20040820.pdf
Great - thanks very much.
mickfrancis is offline   Reply With Quote
Old 2016-02-09, 13:38   #8
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,181 Posts
Default

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).
jasonp is offline   Reply With Quote
Old 2016-03-29, 14:26   #9
mickfrancis
 
Apr 2014
Marlow, UK

23·7 Posts
Default

Quote:
Originally Posted by jasonp View Post
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.
mickfrancis is offline   Reply With Quote
Old 2016-03-29, 19:00   #10
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,181 Posts
Default

It does not and I have not.
jasonp is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 07:58.


Mon Nov 29 07:58:46 UTC 2021 up 129 days, 2:27, 0 users, load averages: 1.10, 1.13, 0.96

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.