Hot answers tagged

12 votes
Accepted

How are extremely large integers stored and implemented in programming languages?

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 ...
user avatar
  • 3,172
11 votes
Accepted

Where are C++ templates inside of the lambda cube?

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 ...
user avatar
  • 29.2k
9 votes
Accepted

Why are struct and class essentially the same in C++?

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 ...
user avatar
  • 2,977
5 votes
Accepted

numerically stable log1pexp calculation

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 ...
user avatar
5 votes

How do you find a hash function that respects a custom equality function?

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 ...
user avatar
  • 29.2k
4 votes

Halting problem in C++

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 ...
user avatar
4 votes

Linked list: advantages of preventing movement of nodes and invalidating iterators on add/remove

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 ...
user avatar
  • 14.2k
4 votes
Accepted

Why do we need value-returning functions?

"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 ...
user avatar
  • 13.7k
4 votes

How do compilers assure stability?

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 ...
user avatar
  • 25.4k
4 votes

Why is the address-of operator in C/C++ represented with the "&" symbol?

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 ...
user avatar
  • 13.3k
3 votes

How do you find a hash function that respects a custom equality function?

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 ...
user avatar
  • 25.4k
3 votes

Understanding memory leaks in C/C++

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 ...
user avatar
  • 25.4k
3 votes
Accepted

Complete the following table by specifying the scope of each declaration

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 ...
user avatar
  • 9,325
3 votes
Accepted

What type of function is main()?

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++ ...
user avatar
3 votes
Accepted

Why isn't deque implemented as a dynamic array?

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 ...
user avatar
  • 386
3 votes
Accepted

What is the difference between python list and c++ vector?

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 ...
user avatar
  • 1,188
3 votes

How do compilers assure stability?

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 ...
user avatar
  • 13.7k
3 votes

Time complexity of similar-looking functions

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 ...
user avatar
3 votes
Accepted

virtual machine based programming languages vs low level

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 ...
user avatar
3 votes
Accepted

Fast computing of a matrix power for large integer values in C++

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} + ...
user avatar
  • 23.9k
3 votes
Accepted

Retreive farthest value to the right of element

Based on your sample, I would assume that farthest from $x$, means the value $y$ on the right of $x$ that maximizes $|x-y|$. And that's what I am using in my answer. Observe that the farthest value is ...
user avatar
  • 1,475
2 votes
Accepted

Find Length of longest substring with all 1's in a binary string with k queries

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 ...
user avatar
2 votes

How do compilers implement symbolic (rather than textual) insertion?

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, ...
user avatar
  • 1,846
2 votes

How do compilers implement symbolic (rather than textual) insertion?

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 ...
user avatar
  • 5,910
2 votes
Accepted

Bytes from integer using bitwise operators

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 ...
user avatar
  • 4,381
2 votes
Accepted

How to count number of 1s of the first k positions in a bitset (bitmap)?

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 ...
user avatar
  • 6,940
2 votes

Is this a misleading or undesirable implementation of a hash map?

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 ...
user avatar
  • 19.1k
2 votes

Efficient way to reduce a binomial coefficient as a fraction

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 ...
user avatar
  • 25.4k
2 votes
Accepted

Efficient way to reduce a binomial coefficient as a fraction

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 ...
user avatar
  • 34.7k
2 votes

C++ STL: How does the distance() method work for a set/ multiset (stored internally as a self balancing tree)?

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 ...
user avatar
  • 23.9k

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