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 ...
- 3,252
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 ...
- 29.7k
10
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.♦
- 156k
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 ...
- 3,048
7
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 <...
- 669
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 ...
- 29.7k
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 ...
- 81.4k
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 ...
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 ...
- 15.5k
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 ...
- 14.4k
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 ...
- 13.9k
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 ...
- 28.4k
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 ...
- 28.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 ...
- 28.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 ...
- 9,425
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++ ...
- 275k
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 ...
- 448
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 ...
- 1,589
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 ...
- 13.9k
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 ...
- 275k
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 ...
- 5,850
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} + ...
- 28.4k
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 ...
- 2,610
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 ...
- 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 ...
- 509
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
...
- 474
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, ...
- 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 ...
- 5,931
Only top scored, non community-wiki answers of a minimum length are eligible