JavaScript Numbers

This chapter will focus on JavaScript number operations, number representation, Number objects, common number algorithms, and random number generation. By the end of this chapter, you will understand how to work with numbers in JavaScript as well as how to implement prime factorization, which is fundamental for encryption.

Number operations of a programming language allow you to compute numerical values. Here are the number operators in JavaScript:

+ : addition

- : subtraction

/ : division

* : multiplication

% : modulus

These operators are universally used in other programming languages and are not specific to JavaScript.

Number System

JavaScript uses a 32-bit floating-point representation for numbers, as shown in Figure 3-1. In this example, the value is 0.15625. The sign bit (the 31st bit) indicates that the number is negative if the sign bit is 1. The next 8 bits (the 30th to 23rd bits) indicate the exponent value, e. Finally, the remaining 23 bits represent the fraction value.

../images/465726_1_En_3_Chapter/465726_1_En_3_Fig1_HTML.jpg — Figure 3-1
The 32-bit floating-point number system

With the 32 bits, the value is computed by this esoteric formula:

$\mathrm{value}={\left(-1\right)}^{\mathrm{sign}}\times {2}^{\mathrm{e}-127}\times \left(1+\sum \limits_{t=1}^{23}{b}_{23-t}{2}^{-t}\right)$

Figure 3-1 shows the following break down of the 32 bits:

sign = 0

e = (0111100)₂ = 124 (in base 10)

$1+\sum \limits_{i=1}^{23}{b}_{23-i}{2}^{-i}=1+0+0.25+0$

This results in the following:

value = 1 x 2^124-127 x 1.25 = 1 x 2^-3 x 1.25 = 0.15625

With decimal fractions, this floating-point number system causes some rounding errors in JavaScript. For example, 0.1 and 0.2 cannot be represented precisely.

Hence, 0.1 + 0.2 === 0.3 yields false.

1 0.1 + 0.2 === 0.3; // prints 'false'

To really understand why 0.1 cannot be represented properly as a 32-bit floating-point number, you must understand binary. Representing many decimals in binary requires an infinite number of digits. This because binary numbers are represented by 2ⁿ where n is an integer.

While trying to calculate 0.1, long division will go on forever. As shown in Figure 3-2, 1010 represents 10 in binary. Trying to calculate 0.1 (1/10) results in an indefinite number of decimal points.

../images/465726_1_En_3_Chapter/465726_1_En_3_Fig2_HTML.jpg — Figure 3-2
Long division for 0.1

JavaScript Number Object

Luckily, there are some built-in properties of the Number object in JavaScript that help work around this.

Integer Rounding

Since JavaScript uses floating point to represent all numbers, integer division does not work.

Integer division in programming languages like Java simply evaluates division expressions to their quotient.

For example, 5/4 is 1 in Java because the quotient is 1 (although there is a remainder of 1 left). However, in JavaScript, it is a floating point.

1 5/4; // 1.25

This is because Java requires you to explicitly type the integer as an integer. Hence, the result cannot be a floating point. However, if JavaScript developers want to implement integer division, they can do one of the following:

Math.floor - rounds down to nearest integer

Math.round - rounds to nearest integer

Math.ceil - rounds up to nearest integer

Math.floor(0.9); // 0

Math.floor(1.1); // 1

Math.round(0.49); // 0

Math.round(0.5); // 1

Math.round(2.9); // 3

Math.ceil(0.1); // 1 Math.ceil(0.9); // 1 Math.ceil(21); // 21 Math.ceil(21.01); // 22

Number.EPSILON

Number.EPSILON returns the smallest interval between two representable numbers. This is useful for the problem with floating-point approximation.

1 function numberEquals(x, y) {

2 return Math.abs(x - y) < Number.EPSILON;

3 }

5 numberEquals(0.1 + 0.2, 0.3); // true

This function works by checking whether the difference between the two numbers are smaller than Number.EPSILON. Remember that Number.EPSILON is the smallest difference between two representable numbers. The difference between 0.1+0.2 and 0.3 will be smaller than Number.EPSILON.

Maximums

Number.MAX_SAFE_INTEGER returns the largest integer.

1 Number.MAX_SAFE_INTEGER + 1 === Number.MAX_SAFE_INTEGER + 2; // true

This returns true because it cannot go any higher. However, it does not work for floating-point decimals.

1 Number.MAX_SAFE_INTEGER + 1.111 === Number.MAX_SAFE_INTEGER + 2.022; // false

Number.MAX_VALUE returns the largest floating-point number possible.

Number.MAX_VALUE is equal to 1.7976931348623157e+308.

1 Number.MAX_VALUE + 1 === Number.MAX_VALUE + 2; // true

Unlike like Number.MAX_SAFE_INTEGER, this uses double-precision floating-point representation and works for floating points as well.

1 Number.MAX_VALUE + 1.111 === Number.MAX_VALUE + 2.022; // true

Minimums

Number.MIN_SAFE_INTEGER returns the smallest integer.

Number.MIN_SAFE_INTEGER is equal to -9007199254740991.

1 Number.MIN_SAFE_INTEGER - 1 === Number.MIN_SAFE_INTEGER - 2; // true

This returns true because it cannot get any smaller. However, it does not work for floating-point decimals.

1 Number.MIN_SAFE_INTEGER - 1.111 === Number.MIN_SAFE_INTEGER - 2.022; // false

Number.MIN_VALUE returns the smallest floating-point number possible.

Number.MIN_VALUE is equal to 5e-324. This is not a negative number since it is the smallest floating-point number possible and means that Number.MIN_VALUE is actually bigger than Number.MIN_- SAFE_INTEGER.

Number.MIN_VALUE is also the closest floating point to zero.

1 Number.MIN_VALUE - 1 == -1; // true

This is because this is similar to writing 0 - 1 == -1.

Infinity

The only thing greater than Number.MAX_VALUE is Infinity , and the only thing smaller than Number.MAX_SAFE_INTEGER is -Infinity.

1 Infinity > Number.MAX_SAFE_INTEGER; // true

2 -Infinity < Number.MAX_SAFE_INTEGER // true;

3 -Infinity -32323323 == -Infinity -1; // true

This evaluates to true because nothing can go smaller than -Infinity.

Size Summary

This inequality summarizes the size of JavaScript numbers from smallest (left) to largest (right):

-Infinity < Number.MIN_SAFE_INTEGER < Number.MIN_VALUE < 0 < Number.MAX_SAFE_IN- TEGER < Number.MAX_VALUE < Infinity

Number Algorithms

One of the most discussed algorithms involving numbers is for testing whether a number is a prime number. Let’s review this now.

Primality Test

A primality test can be done by iterating from 2 to n, checking whether modulus division (remainder) is equal to zero.

1 function isPrime(n){

2 if (n <= 1) {

3 return false;

4 }

6 // check from 2 to n-1

7 for (var i=2; i<n; i++) {

8 if (n%i == 0) {

9 return false;

10 }

11 }

13 return true;

14 }

Time Complexity: O(n)

The time complexity is O(n) because this algorithm checks all numbers from 0 to n.

This is an example of an algorithm that can be easily improved. Think about how this method iterates through 2 to n. Is it possible to find a pattern and make the algorithm faster? First, any multiple of 2s can be ignored, but there is more optimization possible.

Let’s list some prime numbers.

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

This is difficult to notice, but all primes are of the form 6k ± 1, with the exception of 2 and 3 where k is some integer. Here’s an example:

5 = (6-1) , 7 = ((1*6) + 1), 13 = ((2*6) + 1) etc

Also realize that for testing the prime number n, the loop only has to test until the square root of n. This is because if the square root of n is not a prime number, n is not a prime number by mathematical definition.

1 function isPrime(n){

2 if (n <= 1) return false;

3 if (n <= 3) return true;

5 // This is checked so that we can skip

6 // middle five numbers in below loop

7 if (n%2 == 0 || n%3 == 0) return false;

9 for (var i=5; i*i<=n; i=i+6){

10 if (n%i == 0 || n%(i+2) == 0)

11 return false;

12 }

14 return true;

15 }

Time Complexity: O(sqrt(n))

This improved solution cuts the time complexity down significantly.

Prime Factorization

Another useful algorithm to understand is for determining prime factorization of a number. Prime numbers are the basis of encryption (covered in Chapter 4) and hashing (covered in Chapter 11), and prime factorization is the process of determining which prime numbers multiply to a given number. Given 10, it would print 5 and 2.

1 function primeFactors(n){

2 // Print the number of 2s that divide n

3 while (n%2 == 0) {

4 console.log(2);

5 n = n/2;

6 }

8 // n must be odd at this point. So we can skip one element (Note i = i +2)

9 for (var i = 3; i*i <= n; i = i+2) {

10 // While i divides n, print i and divide n

11 while (n%i == 0) {

12 console.log(i);

13 n = n/i;

14 }

15 }

16 // This condition is to handle the case when n is a prime number

17 // greater than 2

18 if (n > 2) {

19 console.log(n);

20 }

21 }

22 primeFactors(10); // prints '5' and '2'

Time Complexity: O(sqrt(n))

This algorithm works by printing any number that is divisible by i without a remainder. In the case that a prime number is passed into this function, it would be handled by printing whether n is greater than 2.

Random Number Generator

Random number generation is important to simulate conditions. JavaScript has a built-in function for generating numbers: Math.random().

Math.random() returns a float between 0 and 1.

You may wonder how you get random integers or numbers greater than 1.

To get floating points higher than 1, simply multiply Math.random() by the range. Add or subtract from it to set the base.

Math.random() * 100; // floats between 0 and 100

Math.random() * 25 + 5; // floats between 5 and 30

Math.random() * 10 - 100; // floats between -100 and -90

To get random integers, simply use Math.floor(), Math.round(), or Math.ceil() to round to an integer.

Math.floor(Math.random() * 100); // integer between 0 and 99

Math.round(Math.random() * 25) + 5; // integer between 5 and 30

Math.ceil(Math.random() * 10) - 100; // integer between -100 and -90

Exercises

1.
Given three numbers x, y, and p, compute (xˆy) % p. (This is modular exponentiation.)
Here, x is the base, y is exponent, and p is the modulus.
Modular exponentiation is a type of exponentiation performed over a modulus, which is useful in computer science and used in the field of public-key encryption algorithms.
At first, this problem seems simple. Calculating this is a one-line solution, as shown here:
1  function modularExponentiation ( base, exponent, modulus ) {
2          return Math.pow(base,exponent) % modulus;
3  }
This does exactly what the question asks. However, it cannot handle large exponents.
Remember that this is implemented with encryption algorithms. In strong cryptography, the base is often at least 256 bit (78 digits).
Consider this case, for example:
Base: 6x10⁷⁷, Exponent: 27, Modulus: 497
In this case, (6x10⁷⁷)²⁷ is a very large number and cannot be stored in a 32-bit floating point.
There is another approach, which involves some math. One must observe the following mathematical property:
For arbitrary a and b,
c % m = (a  b) % m
c % m = [(a % m)  (b % m)] % m
Using this mathematical property, you can iterate 1 to the exponent, recalculating each time by multiplying the current modulus value with the last.
Here is the pseudocode:
1  Set value = 1, current exponent = 0.
2  Increment current exponent by 1.
3  Set value = (base  value) mod modulus until current exponent is reached exponent
Example: Base: 4, Exponent: 3, Modulus: 5
4ˆ3 % 5 = 64 % 5 = 4
value = (lastValue x base ) % modulus:
value = (1 x 4) % 5 = 4 % 5 = 4
value = (4 x 4) % 5 = 16 % 5 = 1
value = (1 x 4) % 5 = 4 % 5 = 4
Finally, here is the code:
1  function modularExponentiation ( base, exponent, modulus ) {
2          if (modulus == 1) return 0;
3
4          var value = 1;
5
6          for ( var i=0; i<exponent; i++ ){
7                  value = (value * base) % modulus;
8          }
9          return value;
10  }
Time Complexity: O(n)
The time complexity is O(n) where n is equal to the exponent value.
2.
Print all primes less than n.
To do this, use the isPrime function covered in this chapter. Simply iterate from 0 to n and print any prime numbers where isPrime() evaluates to true.
1  function allPrimesLessThanN(n){
2          for (var i=0; i<n; i++) {
3                  if (isPrime(i)){
4                          console.log(i);
5                  }
6          }
7  }
8
9  function isPrime(n){
10      if (n <= 1) return false;
11      if (n <= 3) return true;
12
13      // This is checked so that we can skip
14      // middle five numbers in below loop
15      if (n%2 == 0 || n%3 == 0) return false;
16
17      for (var i=5; i*i<=n; i=i+6){
18          if (n%i == 0 || n%(i+2) == 0)
19             return false;
20      }
21
22      return true;
23  }
24
25  allPrimesLessThanN(15);
26
27  // prints 2, 3, 5, 7, 11, 13
Time Complexity: O(nsqrt(n))
This is because isPrime (covered earlier in this chapter) with a time complexity of O(sqrt(n)) is run n times.
3.
Check for a set of prime factors.
Let’s define ugly numbers as those whose only prime factors are 2, 3, or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … shows the first 11 ugly numbers. By convention, 1 is included.
To do this, divide the number by the divisors (2, 3, 5) until it cannot be divided without a remainder. If the number can be divided by all the divisors, it should be 1 after dividing everything.
1  function maxDivide (number, divisor) {
2          while (number % divisor == 0) {
3                  number /= divisor;
4          }
5          return number;
6  }
7
8  function isUgly (number){
9          number = maxDivide(number, 2);
10          number = maxDivide(number, 3);
11          number = maxDivide(number, 5);
12          return number === 1;
13  }
Iterate this over n, and now the list of ugly numbers can be returned.
1  function arrayNUglyNumbers (n) {
2          var counter = 0, currentNumber = 1, uglyNumbers = [];
3
4          while ( counter != n ) {
5
6                  if ( isUgly(currentNumber) ) {
7                          counter++;
8                          uglyNumbers.push(currentNumber);
9                  }
10
11                  currentNumber++;
12          }
13
14          return uglyNumbers;
15  }

Time Complexity for maxDivide(number, divisor): O(log_divisor(number))
The time complexity of maxDivide is a logarithmic function which depends on divisor and the number. When testing primes of 2, 3, and 5, the logarithmic of 2 (log₂ (n)) yields the highest time complexity.
Time Complexity for isUgly: O(log₂(n))
Time Complexity for arrayNUglyNumbers: O(n(log₂(n)))

The isUgly function is limited by the time complexity of maxDivide(number, 2). Hence, arrayNUglyNumbers has n times that time complexity.

Summary

Recall that all numbers in JavaScript are in 32-bit floating point format. To get the smallest possible floating point increment, you should use Number.EPILSON. The maximum and minimum numbers of JavaScript can be summarized by the following inequality:

-Infinity < Number.MIN_SAFE_INTEGER < Number.MIN_VALUE < 0

< Number.MAX_SAFE_INTEGER < Number.MAX_VALUE < Infinity

Prime number validation and prime factorization are concepts used in various computer science applications such as encryption, as covered in Chapter 4. Finally, random number generation in JavaScript works via Math.random().

3. JavaScript Numbers