# Tag Info

12

MPI stands for Multiple Precision Integer. Multiple precision arithmetic is what you need when you work with integer types that go beyond the machine width $w$. The basic idea is simple, you represent a large integer with multiple fixed-width words where the i-th word is the i-th "digit" in base B where $B = 2^w$. For example, most current machines ...

11

But is that exactly where they are located in the lambda cube? The lambda cube is not a giant spectrum on which all programming languages can be classified. It is precisely eight languages, which combine a lambda calculus (values abstracted over values) with all possible combinations of three features: Values abstracted over types (parametric polymorphism) ...

9

Bjarne Stroustrup writes in his The Design and Evolution of C++ book (item 3.5.1): At this point, the object model becomes real in the sense that an object is more than the simple aggregation of the data members of a class. An object of a C++ class with a virtual function is a fundamentally different beast from a simple C struct. Then why did I not ...

5

Let us denote the arrays by $A_1,\ldots,A_k$, their sizes by $|A_1|,\ldots,|A_k|$, their medians by $m_1,\ldots,m_k$, and their union by $\mathbf{A}$. We will try to solve the following more general problem: given $t$, determine the $t$'th smallest element in $\mathbf{A}$. Let $m_r = \min(m_1,\ldots,m_k)$ and $m_s = \max(m_1,\ldots,m_k)$. Define  N = \sum_{...

5

The way I can think of to do this is by some sort of normalization: that is, you need to find a function $f$ such that, if $\equiv$ is your custom equality and $==$ is the normal C++ (or whatever language you use) equality, for all $x,y$, we have $x \equiv y$ if and only if $f(x)==f(y)$. We call $f(x)$ the normal form of $x$. Then, the trick is, instead of ...

4

If you want to prove that the halting problem for C++ programs can't be decided by a C++ program, just copy the proof of the Halting problem but replace every use of a universal Turing machine with a C++ interpreter/compiler that's written in C++.

4

Let $0 < \varepsilon \lll 1$ be the relative error bound of the floating-point system—$2^{-53}$ in IEEE 754 binary64 arithmetic. First, the naive formula log1p(exp(x)) always gives a good approximation unless exp(x) overflows: If exp(x) computes $(1 + \delta_1) e^x$, and if log1p(y) computes $(1 + \delta_2) \log(1 + y)$, where $|\delta_1|, |\delta_2| \... 4 I think this is due to the differences in the philosophy underlying the design of both programming languages. The C++ philosophy allows data structures to cause undefined behavior as soon as the user violates an invariant, while Java wants to avoid that in all cases. Java aims to raise exceptions when invariants are broken, or, when that can not be detected, ... 4 "Need" as such, no. There you are right, all the work can be done using void functions, by passing pointers to variables to modify instead, or changing global variables. In fact, everything is compiled down to assembly language, and no such language I know of has "functions" that return values. On the other hand, we are accustomed (by mathematics, and by ... 4 It happens that compilers contain subtle errors. No blatant errors, because blatant errors would be detected and fixed. A compiler that is itself compiled by a compiler with subtle errors will tend to have blatant errors. They will be easy to detect because they are so blatant. They will be hard to fix because these blatant errors will be produced by ... 3 If you don’t know the equality function then you let hash(x) = 0. Seriously. All your algorithms will work, but slowly because of collisions. All the other suggestions will make your hashing slow instead so you lose nothing. Actually, if you have multiple dictionaries containing these keys, operations are quadratic in the size of each dictionary, instead of ... 3 In your second example, you allocate space for a PrimeSet object and initialise it, then you call the countPrimeNumbers function. The PrimeSet object still exists, it still occupies memory, it probably allocated more memory, and all that memory is still occupied but not accessible. That’s a memory leak: Memory that is occupied but unusable. 3 Your first answer is good (assuming the scope to assign is in order as declarations go). Each declaration is in the scope, where it is declared. In inner scope (say B2) variable$b$is declared shadowing previous declaration. Now you cannot use outer scope variable (read, write) as is by name without scope resolution operator. Your second table suggests ... 3 Library functions are functions that somebody else coded, and are available for use. User-defined functions are functions that the user defines. This is the case of the C/C++ main(). You can think of main() as a placeholder or hook. The user supplies it, but the standard library knows to call it after initializing itself. 3 The reason why std::deque is implemented as a sequence of non-contiguous blocks is to guarantee different complexity bounds (and different concrete performance) for operations with regards to std::vector. You already partially said it: changing the capacity of an std::vector requires reallocating the memory and copying the entire content to the new memory. ... 3 One answer is testing, testing, testing. E.g. GCC comes with an ever growing set of tests that are checked each time the compiler is built. Many compilers are required to pass the so-called triple test: Compile code for your compiler C using compiler A, giving C_1; compile C with C_1 giving C_2, compile C with C_2 giving C_3. Now C_2 and C_3 were compiled ... 3 The answer is actually subtler than it looks. Let us first consider a naive compiler. This naive compiler will implement the recursive case of$g$by actually running$g(n-1)twice. The recurrences for the running time will be \begin{align*} T_f(n) &= T_f(n-1) + O(1) & T_f(1) &= O(1), \\ T_g(n) &= 2T_g(n-1) + O(1) & T_g(1) &= O(1), \... 3 Because B did! A user on software engineering.sx contacted Ken Thompson: From: Ken Thompson c copied from b so & and * are same there. b got * from earlier languages - some assembly, bcpl and i think pl/1. i think that i used & because the name (ampersand) sounds like "address." b was designed to be run with a teletype model 33 teletype. (... 3 It is impossible for one language to be faster than another language, period. A programming language is a set of abstract mathematical rules and restrictions. It is an idea. A piece of paper. You cannot run a language, therefore, you cannot measure its performance. What you can do is run a particular piece of code written in one language using a particular ... 3 Since your matrices are small(50 \times 50)$, you can probably just compute$M^t$through repeated exponentiation where the exponents are powers of$2$. Write$t$in binary so that$t = 2^{k_1} + 2^{k_2} + \dots + 2^{k_\ell}$. Then$M^t = \prod_{i=1}^\ell M^{2^{k_i}}$. Moreover, for$k_i \ge 1$you have$M^{2^{k_i}} = \left( M^{2^{k_i - 1}} \right)^2$, ... 2 Observation: Type 2 query can only make the longest substring of 1 longer. Let's call a substring of 1's a component. For example, there are 3 components in this string 1 1 1 0 0 1 0 1 1 1 1 0 When a 0 is changed to 1, only the components to its immediate left and right will be affected. The length of the other components remains the same. string: 1 1 1 ... 2 I can't wrap my head around how the compiler accomplishes this. The compiler processes the source files in multiple passes. In the first pass, it gathers information about types and their members, effectively producing the information that would be contained in a header file in C++. In the second pass, it looks at method bodies and uses information from ... 2 The Java compiler reads the files you listed with the import statements to see the definitions. For historical reasons C compiler doesn't do this and prefers to get everything in one file, hence the preprocessor. In the end, there is no magic. If you want to make sure at compiletime that the functions that you're calling exist, then the compiler has to see ... 2 Contrary to what you think, extracing bytes by shifting and masking is completely unrelated to the storage order (both little-endian and big-endian storage schemes exist and don't influence the results). An int variable is represented by 32 bits. The least significant byte is made of the eight least significant bits and you obtain them by i & 0xFF 0b ... 2 Popcount is going to be your best option here. As j_random_hacker mentions in a comment, popcount on a single word can be done in$O(\log W)$time if implemented by hand, or$O(1)$if the machine provides a dedicated opcode for it (which should take a constant number of clock cycles—but then again,$W$should also be a constant for any given machine). (Note:... 2 As others have indicated, this code example doesn't do resizing, and this is an important part of a "real" dynamic hash table. Whether or not it's "bad" depends on what it's trying to achieve as an example, but it's certainly not code that you should deploy. Linear probing isn't necessarily a bad idea. After all, it has excellent locality. But since you ... 2 You store the numbers n-k+1 to n in an array. Then for each prime number p ≤ k: Find which power of p is a factor of k! (Thats k/p + k/p^2 + k/p^3 ... ) Then remove that power from the array: Find the first number divisible by p (that would be the number at index 0 if n-k+1 is divisible by p, otherwise at index p - ((n-k+1) modulo p)). That number is ... 2 The formula$\varphi(a)=a \prod_{p|a}(1-\frac{1}{p})$tells us to approach the problem by the prime factors. Here is another useful formula. Legendre's formula. For any prime number$p$and any positive integer$n$, let$\nu _{p}(n)$be the exponent of the largest power of$p$that divides$n!$, i.e,$p^{\nu_{p}(n)}$divides$n!$but$p^{\nu _{p}(n)+1}\$ does ...

2

The complexity of the distance function depends on the type of the iterators supplied: in general it only required to take linear time in the distance but, in the special case in which the input iterators are random access iterators, the worst-case running time is linear. (I believe this is accounting for the time spent in the function in itself, and assumes ...

2

Both python list and c++ vector are implemented as dynamic arrays (https://en.wikipedia.org/wiki/Dynamic_array). (Essentially arrays that get reallocated when they are too small.) Now the important difference between the python and c++ version don't come from the data structures themselves, but rather from the language. In c++ you can store structs, ...

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