1
$\begingroup$

So, this comes from a programming problem, but it is math that I feel like should be easy, that I just can't figure out a quick way to do, short of writing a python script. It's an optimization problem, so maybe calculus could help me, but I need integer solutions, and I wouldn't know how to apply calculus to that.

I'm trying to write an assembly language program which delays the CPU for exactly n ms. The CPU is running at 16 MHz, and I have written an inner loop which delays for 160 cycles. It is called repeatedly by an outer loop which has an overhead of 2 cycles. So, each time the out loop runs, it delays the CPU by 162 cycles.

The CPU also has overhead of 12 cycles to account for additional needed instructions. So, I need the inner loop to run for 15,988 cycles. I can modify the outer loop to include additional instructions which delay the CPU by 1 cycle each, but the keep the routine short, I want to minimize the number of instructions for this.

In other words, if $x=162$ is the number of cycles the loop takes, $\Delta{x}$ is the amount of cycles I add to the loop, and $15,988 \mod{(x+\Delta{x})} =n$, I'd like to minimize $\Delta{x} + n$

How can I efficiently solve this, without just writing a program to iterate through each x and check the remainder?

(We're just gonna pretend we live in a perfect world where all CPU's run exactly at their advertised clock speed and hardware interrupts never happen)

$\endgroup$
9
  • $\begingroup$ $15988$ is divisible by prime $571$ which is greater than $\sqrt{15988} <130$ (so other factors will be below your minimum). So $(15988 \bmod 571)=0$. $\endgroup$
    – Joffan
    Commented Sep 30, 2017 at 17:54
  • $\begingroup$ This is a nice upper bound, but I'd like to try and get closer $\endgroup$
    – Bassinator
    Commented Sep 30, 2017 at 17:57
  • $\begingroup$ What is your acceptable range for $(15988 \bmod x)$ then? $\endgroup$
    – Joffan
    Commented Sep 30, 2017 at 17:59
  • $\begingroup$ I just edited my question, I realized I was unclear $\endgroup$
    – Bassinator
    Commented Sep 30, 2017 at 18:00
  • $\begingroup$ I'd estimate 10 or 15 for minimum value of 15988 mod x. The result of that expression gives me the number of lines of code I'll need to delay with, so I'd like to keep it low. In other words, I'd like to know the minimum amount I need to increase x by to have the lowest remainder. So, I'd like to keep the increase of x below around 15 and the remainder lower than the same. $\endgroup$
    – Bassinator
    Commented Sep 30, 2017 at 18:01

1 Answer 1

Reset to default
2
$\begingroup$

It turns out that you don't need to search many numbers to minimize $\Delta x + n$.

$(15988 \bmod 162) = 112$, so you won't need to have $\Delta x >112$ .

Then $(15988 \bmod 163) = 14$, giving $\Delta x + n=15$. This limits the search even more - we won't need to check any value above $162+15 = 177$.

And in fact no better value of $\Delta x + n$ occurs in that range. $170 = 162+8$ is close with $(15988 \bmod 170) = 8$ and $\Delta x + n =16$, which might be useful if $\Delta x =1$ turns out to be too small.

$\endgroup$
3
  • $\begingroup$ These numbers are higher than I'd like, but the world doesn't always work out that nicely I guess, lol. Your help is greatly appreciated. I really like your approach to narrowing in on the solution. I think I learned something here. $\endgroup$
    – Bassinator
    Commented Sep 30, 2017 at 18:27
  • $\begingroup$ Wait, isn't 15,988 mod 162 = 112? $\endgroup$
    – Bassinator
    Commented Sep 30, 2017 at 18:34
  • 1
    $\begingroup$ Yes, typo corrected. I didn't give that value much attention after $163$ changed the limits so significantly. $\endgroup$
    – Joffan
    Commented Sep 30, 2017 at 18:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .