English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the literature of algorithms, the specific computation model is often notexplicit as it is assumed that the model of computation is the RAM (RandomAccess Machine) model. However, the RAM model itself is ill-founded in theliterature, with disparate definitions and no unified results.  The ambition of this paper is to found the RAM model from scratch byexhibiting a RAM model that enjoys interesting algorithmic properties and therobustness of its complexity classes, notably LIN, the class of linear-timecomputable problems, or the now well-known CONST-DELAY-lin class of enumerationproblems computable with constant delay after linear-time preprocessing,  The computation model that we define is a RAM whose contents and addresses ofregisters are $O(N)$, where $N$ is the size (number of registers) of the input,and where the time cost of each instruction is 1 (unit cost criterion). The keyto the foundation of our RAM model will be to prove that even if addition isthe only primitive operation, such a RAM can still compute all the basicarithmetic operations in constant time after a linear-time preprocessing.Moreover, while the RAM handles only $O(N)$ integers in each register, we willshow that our RAM can handle $O(N^d)$ integers, for any fixed d, by storingthem on $O(d)$ registers and we will have surprising algorithms that computesmany operations acting on these "polynomial" integers -- addition, subtraction,multiplication, division, exponential, integer logarithm, integer square root(or $c$-th root, for any integer $c$), bitwise logical operations, and, moregenerally, any operation computable in linear time on a cellular automaton --in constant time after a linear-time preprocessing.

Which arithmetic operations can be performed in constant time in the RAM model with addition?