1
$\begingroup$

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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – karmanaut
    Mar 14, 2020 at 4:48
  • $\begingroup$ @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. $\endgroup$
    – D.W.
    Mar 14, 2020 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.