1

I've encountered a math problem in programming-language compilation, and I was wondering if there was a known, easy solution to it.

Suppose a chunk of memory is addressed in the usual fashion, using offsets relative to the start of the allocated memory. Also suppose that a program uses two different interpretations of that chunk of memory.

In one interpretation, the memory has this repeating layout: $a0, a1, a2, a0, a1, a2, ...$

In the other interpretation, the memory has this repeating layout: $b0, b1, b2, b3, b0, b1, b2, b3, ...$

So it looks like this: $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline \text{memory offset} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & \cdots \\ \hline \text{sequence A} & a0 & a1 & a2 & a0 & a1 & a2 & a0 & a1 & a2 & a0 & \cdots \\ \hline \text{sequence B} & b0 & b1 & b2 & b3 & b0 & b1 & b2 & b3 & b0 & b1 & \cdots \\ \hline \end{array}$$

So in the general case, the symbol $a_k$ is associated with all memory offsets $\{i*3 + k\ |\ i \ge 0\}$ and $b_k$ is associated with all memory offsets $\{i*4 + k\ |\ i \ge 0\}$.

Now here's my question. Suppose that for both sequences, I'm interested in a contiguous range of symbol names. For example, $A_{interest} = \{ a_x | q \le x \le r \}$ and $B_{interest} = \{ b_x | s \le x \le t \}$. I'd simply like to know whether or not any of the memory offsets will be associated with both an element of $A_{interest}$ and an element of $B_{interest}$.

I think a solution goes something like this:

  • If neither $|\text{sequence A}|$ nor $|\text{sequence B}|$ evenly divides into the other, the answer is simply yes, there's overlap. Regardless of what symbols comprise $A_{interest}$ and $B_{interest}$, every pairing of symbols from those two sets will end up sharing some of the memory locations.

  • Otherwise, I analyze the offsets generated by repeating the smaller of those two sequences, $|\text{sequence A}|$ or $|\text{sequence B}|$, inside the larger sequence. I could do brute-force here, but I'm sure there's a more elegant solution.

Christian Convey
  • 131
  • Can you clarify your definitions of A_interest and B_interest. I got confused with the new subscript notation. Is the x either 0, 1, or 2 (for the a's), or is the subscript the offset (the number on the first line of the table)? – TravisJ Feb 24 '15 at 21:30
  • And, are you looking at, for example, the memory offsets associated with a0 and b1 (to see if there is intersection)? – TravisJ Feb 24 '15 at 21:32
  • @TravisJ A_interest and B_interest come from some outside source. They're just the sets of symbols that some person has decided they'd like to understand. With the running example I had above, I may have (arbitrarily) chosen A_interest = a0...a1, and B_interest = b1...b1. – Christian Convey Feb 24 '15 at 22:12
  • @TravisJ The answer to your second questions is yes. I don't actually care what those offsets are. I simply want to know whether or not there are any memory elements which are associated with both a label from A_interest and a label from B_interest. I think Brent Kerby's answer addresses the question I was trying to ask. – Christian Convey Feb 24 '15 at 22:15

1 Answers1

0

Let $a$ and $b$ be the period of sequence $A$ and sequence $B$ respectively (so $a=3$ and $b=4$ in your example). Your question boils down to whether there exist integers $i_1, i_2, k_1, k_2$, such that $$ai_1+k_1 = bi_2+k_2$$ where $k_1$ and $k_2$ are constrained by $k_1 \in [q,r]$, and $k_2 \in [s,t]$. We can rearrange the equation like so: $$k_1-k_2 = -ai_1+bi_2$$ Now the set of possible values of the right-hand side is precisely the integer multiples of $g=\text{gcd}(a,b)$ (e.g., see http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity), while the set of possible values of the left-hand side is the interval $[q-t,r-s]$. So all you need to do is see if a multiple of $g$ is in the interval $[q-t,r-s]$. This will be the case if and only if (1) $q-t$ is divisible by $g$, or (2) the integer part of $\frac{r-s}g$ is greater than the integer part of $\frac{q-t}g$.

Brent Kerby
  • 5,539