New answers tagged arithmetic
0
Any such algorithm requires exponential time. Here is a proof sketch (omitting technicalities).
Let $n$ be the input length. The input is $-2^n \lt x \lt 2^n$ and the algorithm determines $x \gt 0$. An algorithm for the problem can be represented as an infinite decision tree, where each node is either a leaf (termination) or a branch with "zero" ...
1
By using dynamic programming, we can solve this! Negative values also work.
Let's start off with the subproblems. We would like to know $OPT(i,j)$, the maximum value of a consecutive subsequence from index $i$ to index $j$.
Then the recurrence equation looks like this:
$$
\begin{equation}
OPT(i,j)=\begin{cases}
v_i
& \text{if $i=j$,}\\
\max \{ ...
0
Something went wrong in the addition. 1110 + 1110 is not 1000 (with carry), but 1100 (with carry). This is hopefully obvious in retrospect, after all two times 1110 had better shift that number one place to the left, by definition.
1100 plus the end-around carry is 1101 which corresponds to -2.
0
It's a recursive algorithm. Each time you call mul (through the use of p) you decrease the number of bits of 'a' by one. So the time complexity is the number of bit in 'a'. And since the number of bits equals the log of the value of 'a', so the recursion depth is Log(a).
In each step of the recursion you might perform an add operation of Max(Log(b),Log(a)) ...
Top 50 recent answers are included