Moldulo and Integer Division

[stereologist]

Qfwfq, the reason for keeping the original values and using modulo, which has a marginal or undetectable impact on performance, is the simplicity in understanding the order of events.

 

For example, say I have a window of 10 items. Item 3 might be either before or after item 7. It all depends on where the oldest item is stored.

 

When item 4 is 24, then it is possible that item 3 is 23 and item 7 is 17.

It is also possible that item 4 is 24, and item 3 is 23, but item 7 is 27.

 

Differentiating the 2 is much simpler if the original item numbers are used.

[Qfwfq]

Of course, in cases other than the assumption I had stated (which appeared tacitly so by calling them the last n elements).

 

In your case they each have their own label, it isn't enough to increment a single variable. It's also to be remarked that, in this case, one might need to watch out against replacing the last element of a given class with a previous one, since they aren't chronologically ordered, so before the replacement you would want to compare the labels too.

[stereologist]

In your case they each have their own label, it isn't enough to increment a single variable. It's also to be remarked that, in this case, one might need to watch out against replacing the last element of a given class with a previous one, since they aren't chronologically ordered, so before the replacement you would want to compare the labels too.

 

Sure I can use a single variable. If I place an item into the list I place it at n%m. I know that I have items from n down to max(n-m,0). I also know that t(i) < t(j) if i < j. Therefore, mine are chronologically ordered. The indices are a chronological ordering defining a relative time of events.

[Qfwfq]

You don't get what I meant but it isn't worth arguing over; deducing the chronological order back from the labels doesn't spare the need for the labels. I meant that, if it's the order in which you're processing them that counts (in saying the last m ones), then it can be simplified, without needing the labels to mark that same order.

[stereologist]

I do get what you mean which is why I stated that the order was a relative time scale.

 

We're both on the same page. Thanks for your input.

[CraigD]

This thread’s continuing to show that there are many practical applications of modular arithmetic. Yee-haw! ;)

Another use of modulo arithmetic is adding information to a 'sliding window'. Let's say that you want to store the last m items. You drop the information into slot[i%m], where % is the modulus operator.

This is a common technique in my experience.

 

For example, a large, MUMPS based medical system (and MUMPS-variant languages – the system was and continues to be around, ported to many hardwares, languages, and language implementations) of my intimate acquaintance used this approach in its “give me a temporary global” utility (MUMPS “global” = persistent data of effectively unlimited size visible to all processes). When called, the utility simply incremented a counter, moded it by an appropriate constant (10000 was the default, suitable for 1980s disk systems, where a few GB was big), cleared all nodes descending from a global ref subscripted by the resulting number (ie: KILL ^%whatnot(A#10000)), and returned the reference. This approach avoided the need for a separate purge process to free space used by temp data left by programs that didn’t, intentionally or unintentionally, clean up after themselves, eliminating a potential point of disk-filling failure.

 

By the early 1990s, faster machines made it impractical to pick a modulus (technically, in the expression A%B, % is the modulo operator, while B is the modulus) small enough to purge frequently enough, yet large enough to avoid a temporary global used by a long-running process being deleted and used by processes that called for many temporary globals in a short period, so the utility was changed to use a datestamp and counter (ie: ^%whatnot(+$HOROLOG,A)) structure, which required a scheduled (cron job like) purge job, but the old technique remains useful in applications where its assumptions remain valid.

Let’s say we want to generate random-like numbers from 0 to 99999999.

 

Assign a number M = 99999999 + 1 = 100000000

Chose an “irregular” number P greater than M – let’s use 827347231

Chose another irregular number S less than M – let’s use 27347231

Chose a “seed” number A between 0 and 99999999 – let’s pick 46294630

 

To generate random-like numbers, reassign and output A = ((A+S)*P)%M

This is a reasonable way to generate pseudorandom numbers in situations where computations of PRNs has to be efficient. One of the problems with this method is the lack of long term uniformity of the numbers generated, i.e. some ranges occur more often that others. Then again something like the Mersenne twister chews up more CPU cycles generating PRNs.

It’s true my simple (perhaps the simplest possible) example is pretty poor at generating strong randomness. This slight modification of it, however, does better, with little increase in complexity or computation:

 

Chose an additional seed number C

 

The new generator function now has 2 simultaneous (in this example by virtue of a scratch variable I) assignments:

I = (A*P)+C

A = I%M

C = IM

 

This is actually a special case of the MWC PRNG, where the “lag-r” count of seed residues (remainders) is 1.

 

The MWC PRNG’s author, George Marsaglia, argues convincingly (or appears to a cryptography spectator like me) that the MWC PRNG and variants, which are all computationally similar to the special r=1 case above, are as random as the Merseene twister. They’re obviously much less computing piggish. (see the wikipedia section “Mersenne twister, Alternatives”)

 

Without getting into cryptographic esoterica, a easy, intuitive way to look at the randomness of various PRNGs is to generate via various methods many (eg: 10000) of them for a small range (eg: 0 to 99), and look at their resulting frequency of occurrence. For example …

... MWC PRNG, P=123, r={5}, C=6, FOO:

95, 38, 39, 114, 38, 133, 133, 76, 172, 95, 114, 76, 116, 171, 96, 59, 38, 96, 38, 95, 133, 96, 152, 152, 76, 76, 76, 209, 114, 38, 57, 96, 57, 76, 133, 114, 76, 209, 38, 114, 95, 171, 114, 76, 38, 57, 95, 57, 114, 152, 76, 171, 95, 95, 95, 134, 152, 95, 38, 38, 115, 19, 133, 134, 58, 173, 133, 114, 38, 116, 171, 133, 39, 38, 115, 38, 95, 114, 114, 95, 211, 57, 76, 95, 172, 114, 76, 57, 76, 58, 76, 133, 133, 76, 171, 76, 95, 96, 152, 133

 

... MWC PRNG, P=123, r={1,2,3,4,5}, C=6, FOO:

109, 88, 104, 113, 106, 98, 102, 108, 97, 87, 105, 105, 115, 98, 102, 100, 101, 94, 96, 96, 103, 96, 82, 114, 112, 102, 95, 115, 112, 97, 97, 103, 107, 100, 81, 94, 101, 96, 95, 98, 105, 94, 109, 88, 114, 92, 106, 100, 94, 111, 103, 114, 101, 116, 97, 104, 94, 110, 98, 89, 99, 98, 105, 103, 104, 97, 97, 96, 97, 101, 93, 101, 82, 97, 93, 102, 105, 101, 115, 88, 95, 86, 101, 81, 104, 101, 128, 97, 88, 99, 101, 94, 107, 84, 109, 102, 93, 121, 87, 85

 

... MWC PRNG, P=123, r={1,2,3,4,5,6,7,8,9,10,12,12,13,14,15,16}, C=17, FOO:

101, 100, 96, 87, 115, 100, 90, 108, 102, 124, 99, 89, 98, 102, 105, 104, 109, 110, 95, 102, 116, 94, 102, 101, 98, 92, 125, 89, 97, 97, 110, 100, 82, 106, 95, 101, 120, 84, 86, 101, 110, 105, 109, 88, 97, 94, 108, 109, 95, 91, 86, 120, 94, 110, 96, 89, 107, 88, 105, 102, 100, 106, 94, 77, 96, 95, 97, 89, 90, 109, 119, 119, 86, 102, 85, 93, 113, 99, 93, 108, 90, 88, 112, 104, 102, 85, 91, 110, 101, 86, 90, 95, 101, 120, 119, 107, 104, 103, 92, 95

 

... and the “real” PRNG built into my language interpreter, FOO:

100, 110, 136, 90, 105, 85, 93, 106, 105, 98, 88, 119, 105, 107, 94, 107, 98, 101, 103, 101, 95, 90, 102, 103, 97, 103, 108, 110, 105, 107, 103, 105, 107, 94, 110, 97, 106, 110, 105, 97, 100, 106, 95, 94, 102, 104, 96, 85, 102, 110, 84, 110, 87, 116, 100, 106, 93, 91, 86, 104, 110, 78, 92, 102, 79, 95, 92, 94, 106, 98, 96, 95, 87, 102, 96, 101, 91, 90, 99, 103, 94, 109, 101, 108, 93, 97, 95, 89, 97, 128, 89, 96, 110, 94, 117, 98, 101, 112, 105, 85

 

If you look a bit more deeply (eg: take the FOO of the FOO), you’ll see WMC PRNG with size®>=5 and my languages random number generator are clearly more random than WMC PRNG with size®=1. A look at my simple example (let’s call it SIMPLE), moduloed down to generate 0 to 99, looks glaringly non-random without deeper analysis:

SIMPLE, P=123, S=45, A=6, FOO:

0, 0, 0, 0, 0, 0, 500, 0, 0, 0, 0, 0, 0, 500, 500, 0, 0, 500, 0, 0, 0, 0, 0, 0, 0, 0, 500, 0, 0, 0, 0, 0, 0, 500, 500, 0, 0, 500, 0, 0, 0, 0, 0, 0, 0, 0, 500, 0, 0, 0, 0, 0, 0, 500, 500, 0, 0, 500, 0, 0, 0, 0, 0, 0, 0, 0, 500, 0, 0, 0, 0, 0, 0, 500, 500, 0, 0, 500, 0, 0, 0, 0, 0, 0, 0, 0, 500, 0, 0, 0, 0, 0, 0, 500, 500, 0, 0, 500, 0, 0

 

Showing that even a sequence that looks at first glance random may not be very!

This [sIMPLE] is a pretty crude scheme, as when, as it must, a number repeats, the entire sequence following it will repeat. There is an obvious way to avoid this with no change to the core generator formula, left as an exercise for the reader. :Nurse:

Since nobody’s taken up my “exercise to the reader” challenge, here’s what I noticed long ago when I first used SIMPLE for student-strength cryptography (and to write ca. 1980 handheld calculator programs that observant user/gamers wouldn’t quickly see through :doh:):

 

To avoid the repeating problem, generate PRNs with a larger range than you want (eg: 0 to 999999) then divide to get numbers in the range you want (eg: 0 to 99). For example:

SIMPLE 10000, P=8976241,S=635601,A=610006, FOO:

90, 85, 97, 127, 115, 91, 111, 89, 114, 103, 96, 99, 95, 134, 106, 87, 92, 106, 85, 93, 110, 91, 83, 90, 92, 99, 86, 103, 135, 97, 95, 81, 104, 99, 93, 104, 93, 98, 124, 102, 86, 100, 98, 88, 99, 90, 93, 102, 84, 85, 92, 105, 91, 132, 101, 89, 93, 90, 124, 94, 88, 96, 107, 128, 99, 99, 96, 94, 101, 105, 83, 107, 102, 95, 103, 100, 105, 93, 127, 102, 109, 102, 94, 128, 93, 97, 100, 85, 134, 105, 111, 91, 84, 106, 94, 97, 100, 96, 106, 108

 

Via its FOO of its FOO’s FOO, SIMPLE appears as random as MWC PRNG with size®>=5 and my built-in PRNG. I wonder if it really is :shrug: