# Tag Info

18

First encode natural numbers and pairs, as described by jmad. Represent an integer $k$ as a pair of natural numbers $(a,b)$ such that $k = a - b$. Then you can define the usual operations on integers as (using Haskell notation for $\lambda$-calculus): neg = \k -> (snd k, fst k) add = \k m -> (fst k + fst m, snd k + snd m) sub = \k m -> add k (neg ...

13

Lambda-calculus can encode most data structures and basic types. For example, you can encode a pair of existing terms in the lambda calculus, using the same Church encoding that you usually see to encode nonnegative integers and boolean: $$\mbox{pair}= λxyz.zxy$$ $$\mbox{fst} = λp.p(λxy.x)$$ $$\mbox{snd} = λp.p(λxy.y)$$ Then the pair $(a,b)$ is $p=(\mbox{... 12 By using the fast Fourier transform, multiplications on$k$-bit numbers can be done in time$\tilde{O}(k)$(where the tilde signifies that we're ignoring polylogarithmic factors). By repeated squaring, we can compute$n^{n^2}$with$O(\log n)$multiplications, and each multiplication involves no number larger than$n^{n^2}$, which has roughly$n^2 \log_2 n$... 11 (This answer was initially posted by the asker jonaprieto inside the question.) I remember Wilson's theorem, and I noticed little things: In the above program, it is better if I write:$\begin{align} (p-1)! &\equiv -1 &\pmod p\\ (p-2)! &\equiv (p-1)! (p-1)^ {-1} \equiv \bf{1} &\pmod p\\ (p-3)! &\equiv (p-2)! (p-2)^ {-1} \equiv \bf{(p-2)... 11 From the comment above: Before processing the stream, allocate\lceil \log_2 n \rceil$bits, in which you write$x:= \bigoplus_{i=1}^n \mathrm{bin}(i)$($\mathrm{bin}(i)$is the binary representation of$i$and$\oplus$is pointwise exclusive-or). Naively, this takes$\mathcal{O}(n)$time. Upon processing the stream, whenever one reads a number$j$, ... 10 Strategy The following linear-time algorithm adopts the strategy of hovering around$0$, by choosing either positive or negative numbers based on the sign of the partial sum. It preprocesses the list of numbers; it computes the permutation of the input on-the-fly, while performing the addition. Algorithm Partition$a_1, \ldots, a_n$into a two lists, ... 9 Very simple: Suppose numbers are written in decimal (other bases are handled by a trivial modification). Build a DFA, with$a$states 0, 1, ...,$a - 1$. Start state is 0, and from state$q$on input the digit$d$go to state$(10 q + d) \bmod a$. Accepting state is$b \bmod a$(might need a tweak if$b > a$). 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 ... 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 ... 8 It is regular. Let's first work in binary, which will generalize to any base > 1. Let$M_{a,b}$be the language in question. For a = 1, b = 0 we get$M_{1,0} = \{1, 10, 11, 100, 101, ...\}$which is all strings over$\{0,1\}$without leading zeroes, which is regular (construct a regular expression for it). Now for any$a$, with b still 0 we get$M_{a,0}...

8

Hint #1: first solve the more popular problem "write a automaton that recognizes the decimal/binary representations of numbers divisible by 3" when the least signigicant bit appears first. Intermediate question: prove that $\{ \overline{a\,x+b}\mid a\,x+b≥0 \quad x\in\mathbb{Z}\}$ is regular. Hint #2: The graph of the function $(n \mapsto 10n+d)$ "modulo $... 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 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. 7 Here's an efficient solution based on BDDs Find$n$such that$k,a,b < 2^n$. Create$n$boolean variables, one for each position in an$n-bit$number Write out a boolean formula representing every number in that interval. For example, if$n=4$(so that we are only considering possible inputs in$[0..15]$), then the interval$[2..4]$can be written as$\...

7

Notations: I'll use the C notations for bitwise operations: $a \mathbin\& b$ (bitwise and), $a \mathbin| b$ (bitwise or), $a \mathbin\ll b$ (shift left), $a \mathbin\gg b$ (shift right). The shift operators are left-associative (e.g. $x \mathbin\gg m \mathbin\gg n = (x \mathbin\gg m) \mathbin\gg n$). The shift operations put zeroes in newly created bit ...

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

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 ...

7

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

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

This is related to the well-known change-making problem. So well-studied, in fact, that this question has been investigated for $m \leq 7$  using brute force. As of 2003, the hardness of finding optimal denominations appears to be an open problem. If you check the articles citing Shallit, it seems as if denominations enabling greedy change-making ...

6

Hint: $53 \cdot 100000010000000000 + 4 = 5300000530000000004$. Sketch:

6

There is an $O(n \log n)$ time algorithm (which in some models is optimal, because of the bounds for the element distinctness problem). We first sort the intervals by their right end point. Suppose the sorted order is $I_1, I_2, \ldots, I_n$. Now for each interval, we try to compute the size of the largest possible non-intersecting set, with that interval ...

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

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

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 ...

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