# Tag Info

9

Your problem is NP-complete, by reduction from Subset Sum (it is in NP since the fact that everything is non-negative bounds the coefficients of the solution sufficiently well). Given an instance $S = \{s_1,\ldots,s_n\}, T$ of Subset Sum (is there a subset of $S$ summing to $T$?), we construct an instance $v_1,\ldots,v_{2n},u$ of your problem as follows. For ...

9

I suggest you use a binary search tree, augmented so that leaves can contain an interval (a run of consecutive integers). Maintain the invariant that the intervals do not overlap and are in order (following the search tree invariant). (This can be considered a special case of an interval tree or a segment tree, for the special case where the intervals do ...

8

Division by a constant can always be recast as multiplication by a constant followed by a shift. The relevant papers are: Robert Alverson, "Integer Division Using Reciprocals," IEEE Int'l Symp Comp Arithmetic, (ISCA-10):186-190, 1991. Torbjörn Granlund and Peter L. Montgomery, "Division by Invariant Integers using Multiplication," ACM Conf on Prog Lang ...

8

There is no way to tell if 8 bits in memory are a signed integer, an unsigned integer, a character, or part of a bigger data. The knowledge is put in the instructions. As stated by David Richerby, two's complement makes signedness transparent in most operations (addition, substraction, multiplication), but some are different: the bitwise shift may preserve ...

8

Yes, this class of equations can be solved in polynomial time. In particular, there exists a solution if and only $\gcd(a_1,\dots,a_n)$ divides $k$. That condition can be tested in polynomial time, since there are polynomial-time algorithms to compute the gcd. In addition, if a solution exists, one can be found using the extended Euclidean algorithm.

8

The wikipedia article on Methods of computing square roots: base 2 presents a strikingly similar snippet of C-code [a], but the link to the source is dead. Let's try to do better. The snippets from both wikipedia and the question are very similar to Martin Guy's widely circulated C implementation [b]. which contains a comment: From a book on programming ...

7

Yes. For instance, sorting a million 5-bit integers is a lot easier: use counting sort. And sorting a million long strings is a different question than sorting a million 32-bit integers. In the case of this particular question, one crucial inference you can draw is that all million 32-bit integers would fit into RAM, so it would be appropriate to use an ...

7

Wikipedia has a nice page about the complexity of mathematical operations, and there is also a dedicated page about division. Asymptotically, division has the same complexity as multiplication. The fastest known algorithm, due to Harvey and van der Hoeven, runs in time $O(n\log n)$. However, this algorithm isn't practical (it is not fast in practice, since ...

6

For simple types, you can't tell by looking at the bits in memory. Because the source specifies that the data is of a particular type, the compiler generates code that interprets the bits in memory as representing data of that particular type. In particular, in cases where different CPU instructions are needed (e.g., integer vs floating point), the compiler ...

6

The Galois field $GF(2^{128})$ has many different "concrete" representations. One popular representation is using polynomials in $GF(2)[x]$ (i.e. with coefficients in $GF(2)$) modulo some irreducible polynomial of degree $128$, say $x^{128}+x^7+x^2+x^1+x^0$. The magic constants $7,2,1,0$ come from this particular irreducible polynomial. You don't see $0$ ...

6

For every $n$ there is a "busy beaver" machine (i.e., a Turing machine on the tape alphabet $\{0,1\}$ run on the empty tape) which outputs $1^n$ using $O(\log n/\log\log n)$ states, which is asymptotically optimal (up to constants). Here is how this machine works. For every $C$, we will construct such a machine having $O(\log n/C) + O(C2^C)$ states. The ...

6

Find the shortest path from $1$ to $n$ on an appropriate graph on vertices $\{1, \dots, n\}$. This approach will work whenever it's guaranteed that intermediate values in the calculations will lie within some bounded range.

6

Integer factorization (or rather, an appropriate decision version) is not known to be NP-complete. In fact, it is conjectured not to be NP-complete. However, any reasonable decision version of integer factorization is in NP, and so reducible to any NP-complete problem (by definition). There are specialized algorithms for integer factorization which are ...

6

Here is a general solution for the following problem: Given a positive integer $m$, find positive integers $a,b \geq 2$ such that $a^b$ is as close as possible to $m$. Let $n$ be the length of $m$ in bits (so $n = \Theta(\log m)$). If $2^b > m$ then there is no point to check any $b_0 > b$, hence we only need to check $O(\log m) = O(n)$ many ...

6

Since you know you're going to have to deal with all $2^{32}$ values eventually, you're going to need at least $2^{32}$ bits of memory, one for each value. The pigeonhole principle means that there's no possible way to store all the information you need with fewer bits than this. So I recommend a straightforward bitmap. In other words, a simple array of ...

6

It depends on the model of computation. In the transdichotomous model, which is the standard model in the analysis of algorithms, we assume that the word size is $w=O(\log n)$ bits, where $n$ is the size of input in bits. In this assumption, the sum of the input can be represented with 1 word, so the space complexity is $O(1)$ words. Measured in bits, the ...

5

This is called the "Interval Scheduling" problem in the book [1]. The greedy algorithm, along with an example, is as follows (please find the correctness proof in the book mentioned above): sort the intervals in increasing order of their finishing times, still denoted as $\mathcal{I}$. while ($\mathcal{I} \neq \emptyset$) choose the first $I \in \mathcal{I}... 5 Your operation is multiplication of polynomials over$GF(2)$, i.e., multiplication in the polynomial ring$GF(2)[x]$. For instance, if$p=101$and$q=1101$, you can represent them as$p(x)=x^2+1$,$q(x)=x^3+x^2+1$, and their product as polynomials is$p(x) \times q(x) = x^5+x^4+x^3+1$, so$p \otimes q = 111001$. If$p,q$are$r$bits long, this polynomial ... 5 First of all, your question is very poorly worded, if for no other reason because "quickly" doesn't mean much. You'll need to provide some metric of what "quick" means. Beyond that, when trying to come up with a design for a problem you need to first understand the problem very well and ask a lot of additional questions. Relevant questions in this case ... 5 Computation with large integers is one of the topics of Knuth's "Seminumerical Algorithms" (volume 2 of "The Art of Computer Programming"). Results in elementary number theory, like the properties of modular arithmetic, the Chinese Remainder Theorem, Fermat's little theorem/Euler's theorem are critical here. As commented, this operation is central in ... 5 In a nutshell: Printing a random non-computable real is a meaningless task, for precise technical reasons. The meaningful problem is to print non-computable numbers precisely identified by some unique property. But these cannot be printed by any program precisely because they are not computable. Using randomness in the hope of printing by chance the ... 5 Dynamic programming One approach is to use dynamic programming. If you have$n$numbers ($n$rows in the file), and each number is in the range$1..m$, then the obvious dynamic programming algorithm has running time about$8mn$. For your parameter size, this might be adequate. In particular, let$A[1..n]$be an array of your$n$numbers. Define$T[x,i,j]...

5

From the Wikipedia article on time complexity: In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input. (Wikipedia references Sipser, Introduction to the Theory of Computation, for the above sentence.) In your case, the "length of ...

5

For simplicity , assume the grid is a square $N \times N$ grid and $N$ is a prime. Its easy to see that from each row we can pick $\leq 2$ points only , so the maximum number of points we can chose is $2N$. Now consider the set of points $\{(i,i^2\ mod\ n)\ |\ 0\leq i \leq n-1 \}$. For any set of 3 points to be collinear (Lets call them $(x_1,y_1),(x_2,... 4 The standard algorithm for determining whether an integer$n$is a perfect power goes like this. We check whether it is a perfect$k$th power for$k \in \{2,\ldots,\log n\}$; as an optimization, it suffices to consider only prime$k$. Given$k$, we compute$\sqrt[k]{n}$using binary search or using some fixed-point iteration such as Newton's method. Either ... 4 For completeness, I'll flesh out Yuval's answer a bit more through an example of multiplication of two polynomials$A$and$B$in$\text{GF}(2^{16})$. Let $$A = [0001|1100|1110] = x^8 + x^7 + x^6 + x^3 + x^2 + x,$$ and $$B = [0100|0101|0111] = x^{10} + x^6 + x^4 + x^2 + x + 1.$$ The multiplication of$A$and$B$over$\text{GF}(2)$is then$$C = [0000|0000|... 4 Here is a different solution than the one I suggested in the comments. Compute the sequence of factorials$1!,2!,3!,4!,\ldots$until you get a number which is at least$n$. Since$(k+1)!/k! = O(\log (k!))$, you only compute numbers of magnitude$O(n\log n)$and so of length$(1+o(1))|n|$(here$|n|$is the length of$n$encoded in binary). Having found the ... 4 Here is the quickest way I can think. Assume first that$x$and$z$are coprime. Factor$z = \prod_i p_i^{a_i}$and calculate$\varphi(z) = \prod_i p_i^{a_i-1} (p_i-1)$. Compute$x' = x \pmod{z}$and$y' = y \pmod \varphi(z)$, so that$x^y \equiv x'^{y'} \pmod{z}$. Compute$x'^{y'} \pmod{z}\$ using repeated squaring. Here is what to do in the more general ...

Only top voted, non community-wiki answers of a minimum length are eligible