4 replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
source | link

For people like me who study algorithms for a living, the 21st-century standard model of computation is the integer RAM. The model is intended to reflect the behavior of real computers more accurately than the Turing machine model. Real-world computers process multiple-bit integers in constant time using parallel hardware; not arbitrary integers, but (because word sizes grow steadily over time) not fixed size integers, either.

The model depends on a single parameter $w$, called the word size. Each memory address holds a single $w$-bit integer, or word. In this model, the input size $n$ is the number of words in the input, and the running time of an algorithm is the number of operations on words. Standard arithmetic operations (addition, subtraction, multiplication, integer division, remainder, comparison) and boolean operations (bitwise and, or, xor, shift, rotate) on words require $O(1)$ time by definition.

Formally, the word size $w$ is NOT a constant for purposes of analyzing algorithms in this model. To make the model consistent with intuition, we require $w \ge \log_2 n$, since otherwise we cannot even store the integer $n$ in a single word. Nevertheless, for most non-numerical algorithms, the running time is actually independent of $w$, because those algorithms don't care about the underlying binary representation of their input. Mergesort and heapsort both run in $O(n\log n)$ time; median-of-3-quicksort runs in $O(n^2)$ time in the worst case. One notable exception is binary radix sort, which runs in $O(nw)$ time.

Setting $w = \Theta(\log n)$ gives us the traditional logarithmic-cost RAM model. But some integer RAM algorithms are designed for larger word sizes, like the linear-time integer sorting algorithm of Andersson et al., which requires $w = \Omega(\log^{2+\varepsilon} n)$.

For many algorithms that arise in practice, the word size $w$ is simply not an issue, and we can (and do) fall back on the far simpler uniform-cost RAM model. The only serious difficulty comes from nested multiplication, which can be used to build very large integers very quickly. If we could perform arithmetic on arbitrary integers in constant time, we could solve any problem in PSPACE in polynomial time.

Update: I should also mention that there are exceptions to the "standard model", like Fürer's integer multiplication algorithm, which uses multitape Turing machines (or equivalently, the "bit RAM"), and most geometric algorithms, which are analyzed in a theoretically clean but idealized "real RAM" model"real RAM" model.

Yes, this is a can of worms.

For people like me who study algorithms for a living, the 21st-century standard model of computation is the integer RAM. The model is intended to reflect the behavior of real computers more accurately than the Turing machine model. Real-world computers process multiple-bit integers in constant time using parallel hardware; not arbitrary integers, but (because word sizes grow steadily over time) not fixed size integers, either.

The model depends on a single parameter $w$, called the word size. Each memory address holds a single $w$-bit integer, or word. In this model, the input size $n$ is the number of words in the input, and the running time of an algorithm is the number of operations on words. Standard arithmetic operations (addition, subtraction, multiplication, integer division, remainder, comparison) and boolean operations (bitwise and, or, xor, shift, rotate) on words require $O(1)$ time by definition.

Formally, the word size $w$ is NOT a constant for purposes of analyzing algorithms in this model. To make the model consistent with intuition, we require $w \ge \log_2 n$, since otherwise we cannot even store the integer $n$ in a single word. Nevertheless, for most non-numerical algorithms, the running time is actually independent of $w$, because those algorithms don't care about the underlying binary representation of their input. Mergesort and heapsort both run in $O(n\log n)$ time; median-of-3-quicksort runs in $O(n^2)$ time in the worst case. One notable exception is binary radix sort, which runs in $O(nw)$ time.

Setting $w = \Theta(\log n)$ gives us the traditional logarithmic-cost RAM model. But some integer RAM algorithms are designed for larger word sizes, like the linear-time integer sorting algorithm of Andersson et al., which requires $w = \Omega(\log^{2+\varepsilon} n)$.

For many algorithms that arise in practice, the word size $w$ is simply not an issue, and we can (and do) fall back on the far simpler uniform-cost RAM model. The only serious difficulty comes from nested multiplication, which can be used to build very large integers very quickly. If we could perform arithmetic on arbitrary integers in constant time, we could solve any problem in PSPACE in polynomial time.

Update: I should also mention that there are exceptions to the "standard model", like Fürer's integer multiplication algorithm, which uses multitape Turing machines (or equivalently, the "bit RAM"), and most geometric algorithms, which are analyzed in a theoretically clean but idealized "real RAM" model.

Yes, this is a can of worms.

For people like me who study algorithms for a living, the 21st-century standard model of computation is the integer RAM. The model is intended to reflect the behavior of real computers more accurately than the Turing machine model. Real-world computers process multiple-bit integers in constant time using parallel hardware; not arbitrary integers, but (because word sizes grow steadily over time) not fixed size integers, either.

The model depends on a single parameter $w$, called the word size. Each memory address holds a single $w$-bit integer, or word. In this model, the input size $n$ is the number of words in the input, and the running time of an algorithm is the number of operations on words. Standard arithmetic operations (addition, subtraction, multiplication, integer division, remainder, comparison) and boolean operations (bitwise and, or, xor, shift, rotate) on words require $O(1)$ time by definition.

Formally, the word size $w$ is NOT a constant for purposes of analyzing algorithms in this model. To make the model consistent with intuition, we require $w \ge \log_2 n$, since otherwise we cannot even store the integer $n$ in a single word. Nevertheless, for most non-numerical algorithms, the running time is actually independent of $w$, because those algorithms don't care about the underlying binary representation of their input. Mergesort and heapsort both run in $O(n\log n)$ time; median-of-3-quicksort runs in $O(n^2)$ time in the worst case. One notable exception is binary radix sort, which runs in $O(nw)$ time.

Setting $w = \Theta(\log n)$ gives us the traditional logarithmic-cost RAM model. But some integer RAM algorithms are designed for larger word sizes, like the linear-time integer sorting algorithm of Andersson et al., which requires $w = \Omega(\log^{2+\varepsilon} n)$.

For many algorithms that arise in practice, the word size $w$ is simply not an issue, and we can (and do) fall back on the far simpler uniform-cost RAM model. The only serious difficulty comes from nested multiplication, which can be used to build very large integers very quickly. If we could perform arithmetic on arbitrary integers in constant time, we could solve any problem in PSPACE in polynomial time.

Update: I should also mention that there are exceptions to the "standard model", like Fürer's integer multiplication algorithm, which uses multitape Turing machines (or equivalently, the "bit RAM"), and most geometric algorithms, which are analyzed in a theoretically clean but idealized "real RAM" model.

Yes, this is a can of worms.

3 added 498 characters in body
source | link

For people like me who study algorithms for a living, the 21st-century standard model of computation is the integer RAM. The model is intended to reflect the behavior of real computers more accurately than the Turing machine model. Real-world computers process multiple-bit integers in constant time using parallel hardware; not arbitrary integers, but (because word sizes grow steadily over time) not fixed size integers, either.

The model depends on a single parameter $w$, called the word size. Each memory address holds a single $w$-bit integer, or word. In this model, the input size $n$ is the number of words in the input, and the running time of an algorithm is the number of operations on words. Standard arithmetic operations (addition, subtraction, multiplication, integer division, remainder, comparison) and boolean operations (bitwise and, or, xor, shift, rotate) on words require $O(1)$ time by definition.

Formally, the word size $w$ is NOT a constant for purposes of analyzing algorithms in this model. To make the model consistent with intuition, we require $w \ge \log_2 n$, since otherwise we cannot even store the integer $n$ in a single word. Nevertheless, for most non-numerical algorithms, the running time is actually independent of $w$, because those algorithms don't care about the underlying binary representation of their input. Mergesort and heapsort both run in $O(n\log n)$ time; median-of-3-quicksort runs in $O(n^2)$ time in the worst case. One notable exception is binary radix sort, which runs in $O(nw)$ time.

Setting $w = \Theta(\log n)$ gives us the traditional logarithmic-cost RAM model. But some integer RAM algorithms are designed for larger word sizes, like the linear-time integer sorting algorithm of Andersson et al., which requires $w = \Omega(\log^{2+\varepsilon} n)$.

For many algorithms that arise in practice, the word size $w$ is simply not an issue, and we can (and do) fall back on the far simpler uniform-cost RAM model. The only serious difficulty comes from nested multiplication, which can be used to build very large integers very quickly. If we could perform arithmetic on arbitrary integers in constant time, we could solve any problem in PSPACE in polynomial time.

Update: I should also mention that there are exceptions to the "standard model", like Fürer's integer multiplication algorithm, which uses multitape Turing machines (or equivalently, the "bit RAM"), and most geometric algorithms, which are analyzed in a theoretically clean but idealized "real RAM" model.

Yes, this is a can of worms.

For people like me who study algorithms for a living, the 21st-century standard model of computation is the integer RAM. The model is intended to reflect the behavior of real computers more accurately than the Turing machine model. Real-world computers process multiple-bit integers in constant time using parallel hardware; not arbitrary integers, but (because word sizes grow steadily over time) not fixed size integers, either.

The model depends on a single parameter $w$, called the word size. Each memory address holds a single $w$-bit integer, or word. In this model, the input size $n$ is the number of words in the input, and the running time of an algorithm is the number of operations on words. Standard arithmetic operations (addition, subtraction, multiplication, integer division, remainder, comparison) and boolean operations (bitwise and, or, xor, shift, rotate) on words require $O(1)$ time by definition.

Formally, the word size $w$ is NOT a constant for purposes of analyzing algorithms in this model. To make the model consistent with intuition, we require $w \ge \log_2 n$, since otherwise we cannot even store the integer $n$ in a single word. Nevertheless, for most non-numerical algorithms, the running time is actually independent of $w$, because those algorithms don't care about the underlying binary representation of their input. Mergesort and heapsort both run in $O(n\log n)$ time; median-of-3-quicksort runs in $O(n^2)$ time in the worst case. One notable exception is binary radix sort, which runs in $O(nw)$ time.

Setting $w = \Theta(\log n)$ gives us the traditional logarithmic-cost RAM model. But some integer RAM algorithms are designed for larger word sizes, like the linear-time integer sorting algorithm of Andersson et al., which requires $w = \Omega(\log^{2+\varepsilon} n)$.

For many algorithms that arise in practice, the word size $w$ is simply not an issue, and we can (and do) fall back on the far simpler uniform-cost RAM model. The only serious difficulty comes from nested multiplication, which can be used to build very large integers very quickly. If we could perform arithmetic on arbitrary integers in constant time, we could solve any problem in PSPACE in polynomial time.

Yes, this is a can of worms.

For people like me who study algorithms for a living, the 21st-century standard model of computation is the integer RAM. The model is intended to reflect the behavior of real computers more accurately than the Turing machine model. Real-world computers process multiple-bit integers in constant time using parallel hardware; not arbitrary integers, but (because word sizes grow steadily over time) not fixed size integers, either.

The model depends on a single parameter $w$, called the word size. Each memory address holds a single $w$-bit integer, or word. In this model, the input size $n$ is the number of words in the input, and the running time of an algorithm is the number of operations on words. Standard arithmetic operations (addition, subtraction, multiplication, integer division, remainder, comparison) and boolean operations (bitwise and, or, xor, shift, rotate) on words require $O(1)$ time by definition.

Formally, the word size $w$ is NOT a constant for purposes of analyzing algorithms in this model. To make the model consistent with intuition, we require $w \ge \log_2 n$, since otherwise we cannot even store the integer $n$ in a single word. Nevertheless, for most non-numerical algorithms, the running time is actually independent of $w$, because those algorithms don't care about the underlying binary representation of their input. Mergesort and heapsort both run in $O(n\log n)$ time; median-of-3-quicksort runs in $O(n^2)$ time in the worst case. One notable exception is binary radix sort, which runs in $O(nw)$ time.

Setting $w = \Theta(\log n)$ gives us the traditional logarithmic-cost RAM model. But some integer RAM algorithms are designed for larger word sizes, like the linear-time integer sorting algorithm of Andersson et al., which requires $w = \Omega(\log^{2+\varepsilon} n)$.

For many algorithms that arise in practice, the word size $w$ is simply not an issue, and we can (and do) fall back on the far simpler uniform-cost RAM model. The only serious difficulty comes from nested multiplication, which can be used to build very large integers very quickly. If we could perform arithmetic on arbitrary integers in constant time, we could solve any problem in PSPACE in polynomial time.

Update: I should also mention that there are exceptions to the "standard model", like Fürer's integer multiplication algorithm, which uses multitape Turing machines (or equivalently, the "bit RAM"), and most geometric algorithms, which are analyzed in a theoretically clean but idealized "real RAM" model.

Yes, this is a can of worms.

2 added 18 characters in body
source | link

For people like me who study algorithms for a living, the 21st-century standard model of computation is the integer RAM. The model is intended to reflect the behavior of real computers more accurately than the Turing machine model. Real-world computers process multiple-bit integers in constant time using parallel hardware; not arbitrary integers, but (because word sizes grow steadily over time) not fixed size integers, either.

The model depends on a single parameter $w$, called the word size. Each memory address holds a single $w$-bit integer, or word. In this model, the input size $n$ is the number of words in the input, and the running time of an algorithm is the number of operations on words. Standard arithmetic operations (addition, subtraction, multiplication, integer division, remainder, comparison) and boolean operations (bitwise and, or, xor, shift, rotate) on words require $O(1)$ time by definition.

Formally, the word size $w$ is NOT a constant for purposes of analyzing algorithms in this model. To make the model consistent with intuition, we require $w \ge \log_2 n$, since otherwise we cannot even store the integer $n$ in a single word. Nevertheless, for most non-numerical algorithms, the running time is actually independent of $w$, because mostthose algorithms don't care about the underlying binary representation of their input. Mergesort and heapsort both run in $O(n\log n)$ time; median-of-3-quicksort runs in $O(n^2)$ time in the worst case. One notable exception is binary radix sort, which runs in $O(nw)$ time.

Setting $w = \Theta(\log n)$ gives us the traditional logarithmic-cost RAM model. But some integer RAM algorithms are designed for larger word sizes, like the linear-time integer sorting algorithm of Andersson et al., which requires $w = \Omega(\log^{2+\varepsilon} n)$.

For many algorithms that arise in practice, the word size $w$ is simply not an issue, and we can (and do) fall back on the far simpler uniform-cost RAM model. The only realserious difficulty comes from nested multiplication, which can be used to build very large integers very quickly. If we could perform arithmetic on arbitrary integers in constant time, we could solve any problem in PSPACE in polynomial time.

Yes, this is a can of worms.

For people like me who study algorithms for a living, the 21st-century standard model of computation is the integer RAM. The model is intended to reflect the behavior of real computers more accurately than the Turing machine model. Real-world computers process multiple-bit integers in constant time using parallel hardware; not arbitrary integers, but (because word sizes grow steadily over time) not fixed size integers, either.

The model depends on a single parameter $w$, called the word size. Each memory address holds a single $w$-bit integer, or word. In this model, the input size $n$ is the number of words in the input, and the running time of an algorithm is the number of operations on words. Standard arithmetic operations (addition, subtraction, multiplication, integer division, remainder, comparison) and boolean operations (bitwise and, or, xor, shift, rotate) on words require $O(1)$ time by definition.

Formally, the word size $w$ is NOT a constant for purposes of analyzing algorithms in this model. To make the model consistent with intuition, we require $w \ge \log_2 n$, since otherwise we cannot even store the integer $n$ in a single word. Nevertheless, for most algorithms, the running time is actually independent of $w$, because most algorithms don't care about the underlying binary representation of their input. Mergesort and heapsort both run in $O(n\log n)$ time; median-of-3-quicksort runs in $O(n^2)$ time in the worst case. One notable exception is binary radix sort, which runs in $O(nw)$ time.

Setting $w = \Theta(\log n)$ gives us the traditional logarithmic-cost RAM model. But some integer RAM algorithms are designed for larger word sizes, like the linear-time integer sorting algorithm of Andersson et al., which requires $w = \Omega(\log^{2+\varepsilon} n)$.

For many algorithms that arise in practice, the word size $w$ is simply not an issue, and we can (and do) fall back on the far simpler uniform-cost RAM model. The only real difficulty comes from nested multiplication, which can be used to build very large integers very quickly. If we could perform arithmetic on arbitrary integers in constant time, we could solve any problem in PSPACE in polynomial time.

Yes, this is a can of worms.

For people like me who study algorithms for a living, the 21st-century standard model of computation is the integer RAM. The model is intended to reflect the behavior of real computers more accurately than the Turing machine model. Real-world computers process multiple-bit integers in constant time using parallel hardware; not arbitrary integers, but (because word sizes grow steadily over time) not fixed size integers, either.

The model depends on a single parameter $w$, called the word size. Each memory address holds a single $w$-bit integer, or word. In this model, the input size $n$ is the number of words in the input, and the running time of an algorithm is the number of operations on words. Standard arithmetic operations (addition, subtraction, multiplication, integer division, remainder, comparison) and boolean operations (bitwise and, or, xor, shift, rotate) on words require $O(1)$ time by definition.

Formally, the word size $w$ is NOT a constant for purposes of analyzing algorithms in this model. To make the model consistent with intuition, we require $w \ge \log_2 n$, since otherwise we cannot even store the integer $n$ in a single word. Nevertheless, for most non-numerical algorithms, the running time is actually independent of $w$, because those algorithms don't care about the underlying binary representation of their input. Mergesort and heapsort both run in $O(n\log n)$ time; median-of-3-quicksort runs in $O(n^2)$ time in the worst case. One notable exception is binary radix sort, which runs in $O(nw)$ time.

Setting $w = \Theta(\log n)$ gives us the traditional logarithmic-cost RAM model. But some integer RAM algorithms are designed for larger word sizes, like the linear-time integer sorting algorithm of Andersson et al., which requires $w = \Omega(\log^{2+\varepsilon} n)$.

For many algorithms that arise in practice, the word size $w$ is simply not an issue, and we can (and do) fall back on the far simpler uniform-cost RAM model. The only serious difficulty comes from nested multiplication, which can be used to build very large integers very quickly. If we could perform arithmetic on arbitrary integers in constant time, we could solve any problem in PSPACE in polynomial time.

Yes, this is a can of worms.

1
source | link