Hot answers tagged

38

In C, void is used for multiple unrelated things. Depending on what it's used for, its meaning may be a unit type, an empty type, or something else. When void is used by itself (as opposed to void*, a pointer to void), it's a unit type, i.e. a type with a single value. Functions that return void are said to “return nothing”, but what this really means is ...


37

I'm not sure but I think the answer is no, for rather subtle reasons. I asked on Theoretical Computer Science a few years ago and didn't get an answer that goes beyond what I'll present here. In most programming languages, you can simulate a Turing machine by: simulating the finite automaton with a program that uses a finite amount of memory; simulating ...


25

Integers are just binary strings and, to determine equality, both languages will compare the strings bit-by-bit. Not quite. C ints are machine-word-sized and compared with a single machine instruction; Python ints are represented in base $2^{30}$ (see e.g. https://rushter.com/blog/python-integer-implementation/) and compared digit-by-digit in that base. So ...


16

Complexity is defined relative to a computation model. P and NP, for example, are defined in terms of Turing machines. For comparison, consider the word RAM model. In this model, memory is divided into words, words can be accessed in constant time, and the size of the problem can be represented using $O(1)$ words. So, for example, when analysing a comparison-...


13

The C language has typing rules. For example, you can't divide two pointers, and when you call a procedure accepting a pointer, you can't use a double. A C compiler analyzes its source in several phases: first there is lexical analysis, then the source is parsed, and so on. These phases are abstraction, and in fact additional information is passed from phase ...


11

The name “empty type” is perhaps confusing. What this means is, as you say yourself, the type contains no values. The “empty” refers not to any individual values of the type, it refers to the type as a whole, considered as a ~set of possible values. So this does not say something like “a function returning void returns no information”, but “there exists no ...


11

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 ...


10

C99's addition of va_copy to the variadic argument API may give us a back door to Turing-completeness. Since it becomes possible to iterate through a variadic arguments list more than once in a function other than the one that originally received the arguments, va_args can be used to implement a pointerless pointer. Of course, a real implementation of the ...


9

Is this correct? I haven't seen anyone else claim that Python compares ints in log time. No (and a little yes). Consider the following thought-provoking (but not really true) claim: A computer can only have a finite amount of memory (bounded by the number of atoms in the universe), so the Python version is also $O(1)$. The problem is that we are trying to ...


6

Although this may seem like a trivial point, your first sentence is incorrect. The functions are not equivalent. To make them equivalent, the C function should use GMP (or similar) to implement arbitary-precision arithmetic. Now, the reason this observation is not trivial, is that the extent to which it's reasonable to say that the two are equivalent, is ...


4

A standard for a programming language is a document defining the syntax and semantics for that language. Usually, for real-world languages, this document involves a (hopefully) precise description in intuitive terms, rather than a formal semantics, written in mathematical terms. Still, this document acts as a contract between the programmer and the language ...


4

It's not equivalent, and I suspect there will be a loss of statistical randomization/mixing. The core step that offers mixing of the bits is multiplication by FNV_PRIME modulo $2^{32}$. The original version (operating on bytes) does this once for each byte of the input. The alternative version (operating on integers) does this once for each integer, i.e., ...


4

Nonstandard arithmetic, maybe? So, it seems that the issue is the finite size of sizeof(t). However, I think I know a work around. As far as I know, C does not require an implementation to use the standard integers for its integer type. Therefore, we could use a non-standard model of arithmetic. Then, we would set sizeof(t) to some nonstandard number, and ...


4

By simply looking at the structure of the loop, we know that if the while loop terminates after going into the loop (I'll assume this for simplicity as it's the interesting case) that $y=\frac{m}{x}$ (last instruction) and that $x-y<\epsilon$ (exit condition). Combining the two gives you $x< \sqrt{m+x\dot\epsilon}$. If you manage to notice that $x\geq ...


4

No, in C unterminated strings are not tokens. The C language definition precisely describes what a token is; among other things, they include (complete) string literals and a fallback category of "single non-whitespace characters" which are not otherwise matched by the lexical grammar. This latter category does not, however, include " and ' characters; if ...


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 ...


4

The “C programming language“ is defined by a document that defines the syntax and the semantics of programs, and the C standard library. So both are part of the “C programming language”. However, in CS the term “language” is used in a different way, as a set of strings. You can define a language based purely on the syntax In the C Standard document - that ...


4

I'm not sure if this is in topic here. Anyway, (*a) in (*a)=(*b) denotes a lvalue referring to the object in a. On the right side of the assignment, (*b) also denotes an lvalue, but this lvalue undergoes lvalue conversion and is converted to the actual value stored in the object pointed by $b$ (i.e., to 20). In the end, the value 20 is assigned to the object ...


3

You don't need books. You need to write lots of programs. Since you are interested in cryptography, you should practice writing programs that involve mathematics. A good way to do so is to join Project Euler and just go down the list. Good luck!


3

One can use such a feature to write memory allocation methods that access memory directly. One such use is to check the previous memory block using a negative array index to determine if the two blocks can be merged. I've used this feature when I develop a non-volatile memory manager.


3

The C language standard has provisions for hosted and freestanding runtime environments and makes clear which language features are required for each. Hosted environments are required to provide the standard C library, freestanding environments are not. Operating system kernels and embedded systems are typically built for freestanding environments and so ...


3

The kernel of the system doesn't use the C library (at least not it's I/O facilities). The kernel does offer system calls like read(3) and write(3) in Unix, and translates them into whatever magic the underlying hardware requires to do this. For example, as a very rough description of how this goes, to write to a serial port, the kernel copies the ...


3

To declare a class (or a function) a friend allows the friend to access private members [the naming in C++ is not my fault!] (data or function) directly. They aren't "inherited" in any meaningful way. Yes, it creates a interdependency, but very different and a lot weaker than inheritance does.


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

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

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

Today, you can definitely write an OS in C because you have compilers readily available on some OSes. You just have to decide with what executable format you are going to go and then parse it from a bootloader like a UEFI bootloader which has to be written in C as well. Linux is compiled to an ELF executable which is then compressed. Linux follows the ...


3

There's a lot to unpack here, but I'll try to keep it as Computer Science as I can. Am I right in thinking that fork, malloc, etc. are wrapper methods that call the Kernel? Yes and no, respectively. In a typical POSIX-like operating system, fork is a system call. This means that there is usually a very thin wrapper, often written in assembly language, which ...


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. (...


2

As noted by Tom van der Zanden in a comment, and given you already know what's wrong with the code, think of an input that will cause the program to fail, just run the program with that input and you have your instance. Does it make more sense if you think of the phrase, "for instance"? You may be overthinking it (a good sign actually), if this is just a ...


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