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

 2016-02-08, 12:00 #1 mickfrancis   Apr 2014 Marlow, UK 3816 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 5·709 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

175B16 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

23·7 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 354510 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 01:32.

Fri May 20 01:32:30 UTC 2022 up 35 days, 23:33, 2 users, load averages: 1.55, 1.38, 1.56

Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔