Skip to main content
13 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 ...
Vincenzo's user avatar
  • 3,317
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 ...
Joey Eremondi's user avatar
11 votes
Accepted

How does the linker know where to look for a function implementation in C++?

The compiler compiles from a .cpp file to an object file (.o) with the binary code. The linker combines all of the object files together into a single binary. So, the linker doesn't need to know which ...
D.W.'s user avatar
  • 161k
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 ...
HEKTO's user avatar
  • 3,098
9 votes

How does the linker know where to look for a function implementation in C++?

It is the linker's job to link the function declaration to its implementation This is not true. This is the compiler's job. Essentially the declaration (I'm assuming you mean the prototype, as in <...
slebetman's user avatar
  • 699
6 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 ...
Пафнутий Чебышев's user avatar
5 votes
Accepted

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 ...
David Richerby's 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 ...
Joey Eremondi's user avatar
5 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 ...
Pål GD's user avatar
  • 16.7k
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 ...
chi's user avatar
  • 14.6k
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 ...
vonbrand's user avatar
  • 14.1k
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 ...
gnasher729's user avatar
  • 30.5k
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 ...
gnasher729's user avatar
  • 30.5k
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 ...
gnasher729's user avatar
  • 30.5k
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 ...
Evil's user avatar
  • 9,465
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++ ...
Yuval Filmus's 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 ...
Nicola Gigante's user avatar
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 ...
plshelp's user avatar
  • 1,629
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 ...
vonbrand's user avatar
  • 14.1k
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 ...
Yuval Filmus's 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 ...
Jörg W Mittag's 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} + ...
Steven's user avatar
  • 29.5k
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 ...
Russel's user avatar
  • 2,780
3 votes

How does the linker know where to look for a function implementation in C++?

For C and C++, the linker's job is the same, ignoring template classes/functions. The .o / .obj files are split into Sections, each of which has a Symbol Table. The Symbol Table has the offset into ...
CSM's user avatar
  • 179
3 votes

Is there an elegant algorithm for applying multiple simultaneous search-and-replace operations to a string?

You can build an Aho-Corasick automata for the before words, run your string through it, and whenever you find a match go back in the string and replace it with the after value, and then reset the ...
Command Master's user avatar
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 ...
Christopher Boo's 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, ...
svick's user avatar
  • 1,866
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 ...
adrianN's user avatar
  • 5,951

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