Most efficient way to store this collection of moduli and remainders?
- by Bryan
I have a huge collection of different moduli and associated with each modulus a fairly large list of remainders. I want to store these values so that I can efficiently determine whether an integer is equivalent to any one of the remainders with respect to any of the moduli (it doesn't matter which, I just want a true/false return).
I thought about storing these values as a linked-list of balanced binary trees, but I was wondering if there is a better way?
EDIT
Perhaps a little more detail would be helpful. As for the size of this structure, it will be holding about 10s of thousands of (prime-1) moduli and associated to each modulus will be a variable amount of remainders. Most moduli will only have one or two remainders associated to it, but a very rare few will have a couple hundred associated to it.
This is part of a larger program which handles numbers with a couple thousand (decimal) digits. This program will benefit more from this table being as large as possible and being able to be searched quickly.
Here's a small part of the dataset where the moduli are in parentheses and the remainders are comma separated:
(46) k = 20
(58) k = 15, 44
(70) k = 57
(102) k = 36, 87
(106) k = 66
(156) k = 20, 59, 98, 137
(190) k = 11, 30, 68, 87, 125, 144, 182
(430) k = 234
(520) k = 152, 282
(576) k = 2, 11, 20, 29, 38, 47, 56, 65, 74, ...(add 9 each time), 569
I had said that the moduli were prime, but I was wrong they are each one below a prime.
