<p>One approach is to implement an interpreter for the RAM model, and then instrument the interpreter with a counter that keeps track of the number of instructions executed.  I suspect it should be possible to build an interpreter that incurs at most a <span class="math-container">$O(1)$</span>-factor slowdown, but I haven't checked the details (the instruction set is so primitive that the programming is ugly) -- you should be able to check whether the obvious approach works.</p>

CC BY-SA 4.0
2020-03-14T04:48:08.367Z
You are right that if I can have a counter that keeps track of the number of instructions executed, then I am done. Would an "interpreter" be equivalent to inserting a statement (after each instruction of the algorithm) that increments a counter, checks if it has crossed a threshold, and if it has, print and reset it. Clearly this requires 4 instructions in the RAM model for each execution of an instruction of the algorithm. This seems to be the obvious approach -- I was hoping that some paper might have already talked about this.
karmanaut
CC BY-SA 4.0
2020-03-14T15:39:57.680Z
@karmanaut, no, that strategy doesn't appear to work, because you need to ensure that the algorithm you're interpreting doesn't overwrite the counter.  Perhaps there is some other instrumentation that would work (e.g., something like SFI) -- but it might be simpler to just write an interpreter for the instruction set of a RAM model.
D.W.
CC BY-SA 4.0
2020-03-14T04:37:58.607Z
2020-03-14T04:37:58.607Z
D.W.
<p>Suppose there is a deterministic algorithm of size <span class="math-container">$O(1)$</span> that operates on an input of size <span class="math-container">$N$</span> on a RAM model machine. I want to run the algorithm for <span class="math-container">$O(\sqrt{N})$</span> time, pause the algorithm, print "Hello", and then resume its execution, run it again for <span class="math-container">$O(\sqrt{N})$</span> time and repeat this cycle until the algorithm execution terminates. If the algorithm takes time <span class="math-container">$T$</span>, then there would be <span class="math-container">$O(T/\sqrt{N})$</span> print statements.</p>

<p>It is obvious that an algorithm can be paused/resumed in constant time by storing/loading the content of all registers of the CPU in the memory. However, how is it possible to measure elapsed time in the RAM model and stop the algorithm after <span class="math-container">$O(\sqrt{N})$</span> steps? Does the RAM model support such an operation (a Turing machine definitely does)? Any reference or a simple argument is welcome!</p>

<ds.algorithms><time-complexity><machine-models><formal-methods>
Running an algorithm for fixed amount of time on RAM model machine
karmanaut
# Running an algorithm for fixed amount of time on RAM model machine

(Asked by: username_0 on 2020-03-13)

Suppose there is a deterministic algorithm of size $O(1)$ that operates on an input of size $N$ on a RAM model machine. I want to run the algorithm for $O(\sqrt{N})$ time, pause the algorithm, print "Hello", and then resume its execution, run it again for $O(\sqrt{N})$ time and repeat this cycle until the algorithm execution terminates. If the algorithm takes time $T$, then there would be $O(T/\sqrt{N})$ print statements.

It is obvious that an algorithm can be paused/resumed in constant time by storing/loading the content of all registers of the CPU in the memory. However, how is it possible to measure elapsed time in the RAM model and stop the algorithm after $O(\sqrt{N})$ steps? Does the RAM model support such an operation (a Turing machine definitely does)? Any reference or a simple argument is welcome!

**Tags:** ds.algorithms, time-complexity, machine-models, formal-methods

---

## 1 answers

### Answer by username_1 on 2020-03-14. Score: 2

One approach is to implement an interpreter for the RAM model, and then instrument the interpreter with a counter that keeps track of the number of instructions executed. I suspect it should be possible to build an interpreter that incurs at most a $O(1)$-factor slowdown, but I haven't checked the details (the instruction set is so primitive that the programming is ugly) -- you should be able to check whether the obvious approach works.

> **Comments:**
> **username_0**: You are right that if I can have a counter that keeps track of the number of instructions executed, then I am done. Would an "interpreter" be equivalent to inserting a statement (after each instruction of the algorithm) that increments a counter, checks if it has crossed a threshold, and if it has, print and reset it. Clearly this requires 4 instructions in the RAM model for each execution of an instruction of the algorithm. This seems to be the obvious approach -- I was hoping that some paper might have already talked about this.  
> **username_1**: @karmanaut, no, that strategy doesn't appear to work, because you need to ensure that the algorithm you're interpreting doesn't overwrite the counter.  Perhaps there is some other instrumentation that would work (e.g., something like SFI) -- but it might be simpler to just write an interpreter for the instruction set of a RAM model.  

---

