Fundamentals of Informatics

Positional number systems

In digital computers, data is generally represented as a sequence of binary digits, e.g. in the form of binary numbers. Since binary numbers are difficult to handle, we usually display them in the hexadecimal number system (i.e. in the positional number system with base 16) as hexadecimal numbers.
A number system (or number representation system) defines uniform rules which determine how we represent numbers by a series of digits.

The base of a number system is a natural number that is greater than 1 (for example, 2, 10, or 16). Based on this, we speak, for example, of binary, decimal or hexadecimal number systems or notations.
The idea of positional number systems is based on the concept of digits and their positional value.
For example,

in the binary number system, the set of digits is {0, 1}, and the positional values of digits are the powers of 2 whose exponents are natural numbers starting with 0;

the digits of the binary number system are called bits

in the decimal number system, the set of digits is {0, 1, 2, ..., 9}, and the positional values of digits are the powers of 10 whose exponents are natural numbers starting with 0;
in the hexadecimal number system, the set of digits is {0, 1, 2, ..., 9, A, B, ..., F}, and the positional values of digits are the powers of 16 whose exponents are natural numbers starting with 0. (Note that the digits A, B, ..., F correspond to the numbers 10, 11, ..., 15 in the decimal number system, respectively.)

In a positional number system, a given number is represented as a sequence of digits.

In the case of non-integer (rational, real) numbers, a dot ('.') separates the integer and the fractional parts of the numbers.

The value of a number is obtained by multiplying the value of each digit by its positional value and adding the resulting products. Performing the operations in the decimal number system, the final result of the addition will give the value of the number in decimal notation.

For example, in the decimal number system, from right to left,
– the first positional value is 10⁰=1 and so the corresponding digit represents the number of ones,
– the second positional value is 10¹=10 and so the corresponding digit represents the number of tens,
– the third positional value is 10²=100 and so the corresponding digit represents the number of hundreds etc.

In general, numbers in a number system with base 'b' can be described or represented by the following formula:

Examples:
(1) a real number in the decimal number system (b=10):
    314.6₁₀ = 3*10²+1*10¹+4*10⁰ + 6*10⁻¹
(2) an integer in the binary number system (b=2):
    101011₂ = 1*2⁵+1*2³+1*2¹+1*2⁰ = 43₁₀
(3) a real number in the binary number system (b=2):
    101011.101₂ = 1*2⁵+1*2³+1*2¹+1*2⁰ + 1*2⁻¹+1*2⁻³ = 43.625₁₀
(4) an integer in the hexadecimal number system (b=16):
    1C4₁₆ = 1*16²+12*16¹+4*16⁰ = 452₁₀
(5) a real number in the hexadecimal number system (b=16):
    1C4.4₁₆ = 1*16²+12*16¹+4*16⁰ + 4*16⁻¹ = 452.25₁₀

The concept of algorithm

In computer science, or in general, in the ubiquitous and rapidly evolving information and communication technology (IKT), the concept of algorithm is fundamental.
An algorithm is a prescribed set of instructions for the solution of a given problem (or a group of similar problems) in a finite number of steps. The instructions are executed one by one in a well-defined order. A well-known example of an algorithm is the performance of a calculation (e.g. an addition).

The algorithms that are important to us are those that can be described ("encoded") with the help of a computer program. In that case, the instructions of the algorithm are described with statements in a given programming language to perform specific actions or operations for each step of the algorithm.
In this chapter we will learn about several algorithms related to number systems. In addition, we will provide a number of programs for the formal description of those algorithms. The most important components of these programs are reviewed below.
The examples here are given in the JavaScript programming language. These programs use only the very basic statements of the JavaScript language. To get to know the language more thoroughly, it is strongly recommended to study the following materials which are ideal for self-study:
JavaScript Tutorial (2022-09-27)
JavaScript Algorithms and Data Structures (2022-10-02)

Note that the advanced features of the JavaScript language require the knowledge of the basics of the HTML language.

A simple example: Display the first 'n' natural numbers.^⇒

The simplest JavaScript programs are built from the following statements:

the declaration statements which are used to create variables. Variables are the most important components of programs that have a unique name and can store different types of values. For example

var n; // declaration of the variable named 'n'
var i=1; /* declaration of the variable named 'i' by assigning an initial value (i.e. 1) to it */

the assingment statements which are used to change the stored value of the given variables. They usually store the result of one or more operations in a variable. For example

i=i+1; /* adding 1 to the current value of the variable named 'i' and storing the result of the operation in the same variable (i.e. in the variable 'i'); note that the previous value of 'i' will be deleted */
circumference=2*r*3.14; /* multiplying the variable called 'r' first by 2, then by 3.14 (π) and storing calculated value of the product in the variable named 'circumference' */

I/O (input-output) statements that read or write the values of variables from or to an I/O device. In our case the calculated results provided by the programs will be displayed in the right panel of the JavaScript interpreter. For example

writeln("The value of the circumference of the circle: "+circumference); /* writing the variable named 'circumference' to the screen just after the text "The value of the circumference of the circle: "; note the '+' operator which connects the string literal to the current value of the specified variable */
writeln("____________"); /* writing the text "____________" to the screen (this is how the end of the program will be marked in the given example programs) */

control structures that determine the order of execution of the statements of programs. The most important control structures are sequence, selection and iteration. For example

{ a=2; b=3; c=a+b; writeln(c); }
/* let the value of the variable named 'a' be 2, then let the value of the variable named 'b' be 3, and then calculate the sum of 'a' and 'b' (a+b) and store it in the variable named 'c'; after that the sum of 'a' and 'b' ' will be written to the screen */
→ sequence or block (of statements)
function fact(n) {
    var f=1;
    for(var i=1;i<=n;i++) {
        f=f*i;
        }
    return f;
    }
...
writeln("5! = "+fact(5));
/* the function 'fact' calculates the factorial of the number given in the input parameter 'n'; the parameter 'n' gets its actual value when we call the function 'fact' */
→ function (i.e. named sequence or block of statements)
if(i==1) { writeln("true"); } else { writeln("false"); }
/* writing "true" (if 'i' is 1) or "false" (if 'i' is not 1) to the screen depending on the current value of the variable named 'i'; note that the 'else' branch can be omitted */
→ selection
switch(j) {
    case "1": writeln("fail"); break;
    case "2": writeln("satisfactory"); break;
    case "3": writeln("average"); break;
    case "4": writeln("good"); break;
    case "5": writeln("excellent"); break;
    default: writeln("???");
    }
/* if the value of the integer variable 'j' is '1', then write 'fail', in case '2' write 'satisfactory' etc., otherwise write "???" (because only the values 1, 2, ..., 5 are valid) */
→ selection
i=1; while(i<=n) { writeln(i); i=i+1; }
/* writing the value of the variable named 'i' on the screen until the value of 'i' is less than or equal to the current value of the variable 'n' */
→ iteration or repetition ('while' loop)
for(i=0;i<n;i=i+1) { writeln(i); }
/* writing the value of the cycle variable named 'i' on the screen until the value of 'i' is less than the current value of the variable 'n'; this form of loop (or cycle) is usually used to repeat the block of statements given in curly brackets ({...}) a fixed number of times (i.e. exactly 'n' times in our case) */
→ iteration or repetition ('for' loop)

The three most important control structures that determine the execution order of the statements are as follows:

sequence (of statements)
selection (conditional single or multiple branching statements; not to be confused with jump statements, like 'break', 'continue' or 'return')
iteration (cycle or loop)

The above control structures can be excellently illustrated with the help of flowcharts as follows: (cf. Essential Programming | Control Structures | by Diego Lopez Yse | Towards Data Science, 2022-10-09):

Another example: Converting a binary number to a decimal number.^⇒

In the following, we present specific algorithms related to number systems.^⇒
In most cases, the description of the algorithms is also presented with short JavaScript programs. An online JavaScript interpreter that can be used to try the example programs can be accessed as follows:
Online JavaScript Interpreter by Peter Jipsen, Chapman University (January 2013).
http://math.chapman.edu/~jipsen/js/ (2020-11-19)
Note: because the link above is currently not working, please use the link here.

The flowcharts illustrating the JavaScript programs can be displayed using the online web application below:
Live code editor. Created by Bogdan Lyashenko.
https://bogdan-lyashenko.github.io/js-code-to-svg-flowchart/docs/live-editor/index.html (2022-10-02)

Number systems; representation of numbers