103
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'...
47
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
This seems a very basic question to me, so excuse me if I lecture you a bit. The most important point for you to learn here is that a number is not its digit representation. A number is an abstract mathematical object, whereas its digit representation is a concrete thing, namely a sequence of symbols on a paper (or a sequence of bits in compute memory, or a ...
42
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,...
39
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 ...
37
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.
23
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
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.
21
Your two algorithms are equivalent (at least for positive integers, what happens with negative integers in the imperative version depends on Java's semantics for % which I don't know by heart). In the recursive version, let $a_i$ and $b_i$ be the argument of the $i$th recursive call:
$$\begin{gather*}
a_{i+1} = b_i \\
b_{i+1} = a_i \mathbin{\mathrm{mod}...
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
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 $...
18
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 ...
17
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,...
14
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 ...
13
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 ...
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 ...
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
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
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
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
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 ...
9
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 $\...
9
This is just a refactoring (Python 3) of Andrej's code. In Andrej's code numbers are represented through a list of digits (scalars), while in the following code numbers are represented through a list of symbols taken from a custom string:
def v2r(n, base): # value to representation
"""Convert a positive number to its digit representation in a custom ...
9
To divide $b$ by $a$, you follow two steps: first you find $u$ such that $au \equiv 1 \pmod{p}$, and then you compute $bu \pmod{p}$. To find $u$, you run the extended GCD algorithm on $a$ and $p$. If it is indeed the case that $a \not\equiv 0 \pmod{p}$, then since $p$ is prime $(a,p) = 1$. So the GCD algorithm will come up with numbers $u,v$ such that $$ au +...
9
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
