2

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.

16
  • A map of sets, with the keys being moduli, and the sets containing the remainders?
    – Doval
    Commented May 14, 2014 at 23:01
  • I want to be able to quickly tell if an integer is sent to any remainder with respect to any of my moduli. With that kind of map implementation, I would still have to cycle through the keys to see if a remainder is associated to a key. I don't see how that's better than what I was already contemplating.
    – user127741
    Commented May 14, 2014 at 23:41
  • 2
    Have you ever checked out Bloom filters? Depending on the scale of this problem you might find something like this useful...
    – J Trana
    Commented May 15, 2014 at 2:35
  • @JTrana that is very interesting, and I'll keep it in mind for the future; however in terms of probabilistic structures, something which gives false positives is unacceptable for the structure I'm trying to implement. Also, true positives are very desirable.
    – user127741
    Commented May 15, 2014 at 4:05
  • 1
    If we can throw away the moduli while keeping the intended functionality, that's fine. And it is a load-once-read-frequently scenario.
    – user127741
    Commented May 21, 2014 at 16:50

2 Answers 2

Reset to default
1

Your best bet is going to be to parse the data as you read it in, and throw away what you don't need. Since you don't care which modulus a given remainder corresponds to, or how many times a given remainder shows up, you can just keep a list of remainders.

In pseudocode, building this might look something like:

while (data = ReadNextModulus())
   foreach (rem in data.Remainders)
      if !allRemainders.HasRemainder(rem) // We do this check because presumably lookups are faster 
         allRemainders[rem] = true        // than inserts, so we want to skip the insert if possible.

Then when you're done and actually using it, you just check allRemainders.HasRemainder(rem).

In terms of the best data structure to store this, I don't have any specific recommendations myself, but I can point you in the right direction. You're going to have a list of int values which you need fast lookup for. The naive implementation would be to store it as an unsorted array of ints. This would have O(n) time. If you sorted it before using it, that'd reduce to O(log n), presuming you use a binary search.

There's other options out there, though. This question talks about it. The answers suggest trying a Van Emde Boas tree, a bitmap, or just the previously discussed sorted array. You'll need to take a look at them, consider the sparseness of the data you have, and what your language of choice has as built in data structures, and pick the one you think will be best.

But the key is that you're just storing whether a given remainder has been seen, not the full data structure.

3
  • If I've thrown away the moduli, when I put in an integer which is outside the range (greater than any) of the moduli how will I tell its equivalent to any of the remainders? Wouldn't I have to perform a mod test for every integer that was below my limit to see if it's equivalent to any of the remainders, and not just the moduli I cared about?
    – user127741
    Commented May 22, 2014 at 2:58
  • @Bryan - I'm not 100% sure I'm following you, but you can always just store the single largest moduli in a separate variable.
    – Bobson
    Commented May 22, 2014 at 15:58
  • What would have been your recommendation if I wanted to keep the moduli? But just so you know, I settled on a 'splay list' of balance binary trees. Each binary tree represented the remainders associated to a certain modulus. And whenever I tested an integer, I looped through the trees taking mods and searching that tree for the remainders. The first tree I found that matched my test integer was moved to the front of the list.
    – user127741
    Commented May 23, 2014 at 20:41
-1

Since you don't mind which reminder the integer is related to and I see 87 is duplicated (and you will count only once), you could use a unique structure to store theese values. A boolean array gives you O(1) complexity to find if an element exists or not (if you know the maximum dimention and you can have it all in RAM). If also theese values can have thousands of digits and RAM is not enought you should use structures as tree (eg. B-trees) to have O(log n) complexity (the height of the tree).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.