106
Addition is fast because CPU designers have put in the circuitry needed to make it fast. It does take significantly more gates than bitwise operations, but it is frequent enough that CPU designers have judged it to be worth it. See https://en.wikipedia.org/wiki/Adder_(electronics).
Both can be made fast enough to execute within a single CPU cycle. They'...
52
The best algorithm that is known is to express the factorial as a product of prime powers. One can quickly determine the primes as well as the right power for each prime using a sieve approach. Computing each power can be done efficiently using repeated squaring, and then the factors are multiplied together. This was described by Peter B. Borwein, On the ...
48
I assume that the task is to compute $mul(10, a)= 10a$. You don't need to do multiplication. A single binary adder is enough since $$10a = 2^3a + 2a$$
meaning you add one-time left-shifted $a$ to 3-time left-shifted $a$.
For general multiplication $mul(x,y)$ please see this article.
44
Short version: it doesn't know. There's no way to tell.
If 1111 represents -7, then you have a sign-magnitude representation, where the first bit is the sign and the rest of the bits are the magnitude. In this case, arithmetic is somewhat complicated, since an unsigned add and a signed add use different logic. So you'd probably have a SADD and a UADD opcode,...
41
There are several aspects.
The relative cost of a bitwise operation and an addition. A naive adder will have a gate-depth which depend linearly of the width of the word. There are alternative approaches, more costly in terms of gates, which reduce the depth (IIRC the depth then depend logarithmically of the width of the word). Others have given ...
30
To compute the exact mean (no confidence interval or estimate) of each exam, you must at least observe every student's exam score. This takes $\Omega(r)$ per exam. There are $c$ exams you must do this for, this problem should take at least $\Omega(c \cdot r)$ time.
25
CPUs operate in cycles. At each cycle, something happens. Usually, an instruction takes more cycles to execute, but multiple instructions are executed at the same time, in different states.
For example, a simple processor might have 3 steps for each instruction: fetch, execute and store. At any time, 3 instructions are being processed: one is being fetched, ...
22
Keep in mind that the factorial function grows so fast that you'll need arbitrary-sized integers to get any benefit of more efficient techniques than the naive approach. The factorial of 21 is already too big to fit in a 64-bit unsigned long long int.
As far as I know, there is no algorithm to compute $n!$ (factorial of $n$) which is faster than doing the ...
answered Sep 20 '13 at 8:53
Gilles 'SO- stop being evil'
40.9k7 gold badges108 silver badges172 bronze badges
21
There is no way to represent all real numbers without errors if each number is to have a finite representation. There are uncountably many real numbers but only countably many finite strings of 1's and 0's that you could use to represent them with.
20
It all depends what you want to do.
For example, what you show is a great way of representing rational numbers. But it still can't represent something like $\pi$ or $e$ perfectly.
In fact, many languages such as Haskell and Scheme have built in support for rational numbers, storing them in the form $\frac{a}{b}$ where $a,b$ are integers.
The main reason ...
20
In typical floating point implementations, the result of a single operation is produced as if the operation was performed with infinite precision, and then rounded to the nearest floating-point number.
Compare $a+b$ and $b+a$: The result of each operation performed with infinite precision is the same, therefore these identical infinite precision results ...
19
The confusion here stems from a missing word. A correct statement is "The result of XORing two bits is the same as that of adding those two bits mod 2."
For example, $(0+1)\bmod 2 = 1\bmod 2 = 1=(0\text{ XOR }1)$
and
$(1+1) \bmod 2= 2\bmod 2 = 0 =(1\text{ XOR }1)$
19
If your algorithm uses asymptotically less than $n$ time, then it does not have enough time to read all the digits of the numbers it is adding. You are to imagine you are handling very large numbers (stored for example in 8MB text files). Of course, addition can be done very quickly compared to the value of the numbers; it runs in $\mathcal{O}(\log(N))$ time,...
19
In 1's complement you just invert all the bits.
Consider these 2 examples (assuming 8 bits):
$4 = 00000100$, so $-4= 11111011$
$0 = 00000000$, so $-0=11111111$.
So you have 2 ways to represent the number 0
In 2's complement you add 1 to the 1's complement representation of the negative number
$-4$ that in 1's complement was $11111011$ becomes $...
16
The short and simple answer is: it doesn't. No modern mainstream CPU ISA works the way you think it does.
For the CPU, it's just a bit pattern. It's up to you, the programmer, to keep track of what that bit pattern means.
In general, ISAs do not distinguish between different data types, when it comes to storage. (Ignoring special-purpose registers such as ...
15
Gilles answer is a good one, except for the paragraph on the real numbers, which is completely false, except for the fact that the real numbers are indeed a different kettle of fish. Because this sort of misinformation seems to be quite widespread, I would like to record here a detailed rebuttal.
It is not true that all inductive types are denumerable. For ...
13
Processors are clocked, so even if some instructions can clearly be done faster than others, they may well take the same number of cycles.
You'll probably find that the circuitry required to transport data between registers and execution units is significantly more complicated than the adders.
Note that the simple MOV (register to register) instruction ...
12
Modular exponentiation is a well-known algorithm. It is routinely available in libraries and languages that can manipulate large integers, including Wolfram Alpha.
When making computations modulo a large number, one does not first make the whole computation in $\mathbb{N}$ and then take the remainder of the result, because for something like an ...
answered Nov 26 '14 at 22:42
Gilles 'SO- stop being evil'
40.9k7 gold badges108 silver badges172 bronze badges
12
There are multiple ways to define a mathematical structure, depending on what properties you consider to be the definition. Between equivalent characterizations, which one you take to be the definition and which one you take to be an alternative characterization is not important.
In constructive mathematics, it is preferable to pick a definition that makes ...
answered Mar 16 '15 at 17:14
Gilles 'SO- stop being evil'
40.9k7 gold badges108 silver badges172 bronze badges
12
Hint: Use Lucas's theorem.
In general, any time a programming contest problem wants you to compute something mod $p$, check for opportunities to reduce everything mod $p$ before doing any further work.
Spoilers
Don't peek at any hint until you've spent a good amount of time thinking about the previous one!
A more in-depth hint if the previous wasn't ...
12
Addition is important enough to not have it wait for a carry bit to ripple through a 64-bit accumulator: the term for that is a carry-lookahead adder and they are basically part of 8-bit CPUs (and their ALUs) and upwards. Indeed, modern processors tend to need not much more execution time for a full multiplication either: carry-lookahead is actually a ...
11
I believe that NVidia GPUs they use a table lookup, followed by a quadratic interpolation. I think they are using an algorithm similar to the one described in: Oberman, Stuart F; Siu, Michael Y: "A High-Performance Area-Efficienct Mutlifunction Interpolator," _IEEE Int'l Symp Comp Arithmetic, (ARITH-17):272-279, 2005.
The table lookup is indexed with the $...
11
Since the factorial function grows so fast, your computer can only store $n!$ for relatively small $n$. For example, a double can store values up to $171!$. So if you want a really fast algorithm for computing $n!$, just use a table of size $171$.
The question becomes more interesting if you're interested in $\log(n!)$ or in the $\Gamma$ function (or in $\...
11
If you treat your vectors as over the field $GF(2)$ rather than over the set $\{0,1\}$, then what you ask is to find a basis for the span of a set of vectors. This is a well-studied problem in linear algebra, which you probably know the solution for. (One option is Gaussian elimination.)
11
Multiplying by 10 is the same as multiplying by $(1010)_2$. To multiply a binary number $x$ by 10, we thus just have to add $x0$ and $x000$. For example, $6 \times 10 = 60$ is implemented by
$$
\begin{array}{ccccccc}
&0&0&1&1&0&0 \\
+&1&1&0&0&0&0 \\\hline
&1&1&1&1&0&0
\end{array}
$$
...
10
This is a refactoring (Python 3) of Andrej's code. While in Andrej's code numbers are represented through a list of digits (scalars), in the following code numbers are represented through a list of arbitrary symbols taken from a custom string:
def v2r(n, base): # value to representation
"""Convert a positive number to its digit ...
10
For numbers that are small, the binary GCD algorithm is sufficient.
GMP, a well maintained and real-world tested library, will switch to a special half GCD algorithm after passing a special threshold, a generalization of Lehmer's Algorithm. Lehmer's uses matrix multiplication to improve upon the standard Euclidian algorithms. According to the docs, the ...
10
This can be proven, but you need some nontrivial tools to do it.
Start with the set S = {0,3,5,6, ...} of non-negative integers having an even number of 1's in their base-2 expansion.
It is well-known that this set is "2-automatic"; that is, there is a finite automaton accepting exactly the base-2 expansions of elements of S. Furthermore, it is well-...
10
I think you'd be hard pressed to find a processor that had addition taking more cycles than a bitwise operation. Partly because most processors must carry out at least one addition per instruction cycle simply to increment the program counter. Mere bitwise operations aren't all that useful.
(Instruction cycle, not clock cycle - e.g. the 6502 takes a minimum ...
10
One of the great advantages of two’s-complement math, which all modern architectures use, is that the addition and subtraction instructions are exactly the same for both signed and unsigned operands.
Many CPUs do not even have multiply, divide or modulus instructions. If they do, they must have separate signed and unsigned forms of the instruction, and the ...
Only top voted, non community-wiki answers of a minimum length are eligible