# Tag Info

49

in school you (probably) memorized the common operations (addition, subtraction, multiplication and division) for decimal 1 digit numbers. Then you learned how to do operations on larger numbers using those memorized operations by doing the computation part by part for example long multiplication and long division. A computer can do the same algorithms using ...

11

The x86 ISA, along with many (most?) other microprocessor architectures includes the instruction ADC (add with carry), among others, to support arbitrary-precision arithmetic. The basic idea is that instead of thinking of a number as a fixed 2, 4, 8-byte integer, you instead treat it as a variable-length "string" of 2, 4, or 8-byte integers (...

7

Larger precision numbers are simulated in software using arrays of fixed-width integers. The elements of these arrays are effectively super-sized digits, and are called limbs. The size of a limb is chosen based on considerations such as what are the available types; what, if any, special operations does the target processor have for going beyond the widest ...

5

Steele and Sussman's "LAMBDA The Ultimate Imperative", AI Memo 353, 1976 explains that a (tail) procedure call is just a goto statement and the name of the procedure is just a label. So the classic irreducible flow graph: (copy pasted from http://staff.cs.upt.ro/~chirila/teaching/upt/c51-pt/aamcij/7113/Fly0135.html) Can be written: procedure1(): ...

3

Issuing the ten requests in parallel is unlikely to give you a tenfold speedup, but will usually give you some speedup. It depends on where the bottleneck is. If the images are 5 MB each and your Ethernet/WiFi connection can only transfer data at 1 MB/s, then your network card will essentially be tied up for 5 seconds per image, and issuing the requests in ...

2

A literal is not a variable. See https://en.wikipedia.org/wiki/Literal_(computer_programming). I wouldn't consider a literal a "built-in", but I'm not familiar with a precise formal definition of "built-in".

1

We don't "require" loop invariants. They are a technique used when proving algorithm correctness. Lets take a look at a simple example of how loop invariants are useful: Consider the problem where we get an array $A$ and have to find the maximal value of it, i.e. compute $max(A)$. We created the following algorithm for the problem, and we want to ...

1

Loop invariants are crucial for showing an algorithm is correct (cf. proof by induction). For example, suppose you need to sort an array of distinct integers. One simple way to do it is by using selection sort. Why is selection sort correct, i.e., why does it actually solve the problem? If we understand intuitively why the algorithm works, we can also ...

1

An invariant is a statement that holds during the execution of a piece a code. For instance, you might often encounter loop invariants (statements that hold on every iteration of some loop) or class invariants (statements preserved by every method call). In particular, what I believe the article is referring to here is static type checking, i.e., statements ...

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