DEV Community: Matthew Gong

Why can a float represent 3,000,000,000 and also 3,000,000,256, but nothing in between?

Matthew Gong — Sun, 21 Feb 2021 09:48:07 +0000

I read a statement in the book Programming C# 8.0 which I can't understand at first. I quoted it here:

As floating-point numbers get larger, the values that can be represented get farther apart—a float can represent 3,000,000,000 and also 3,000,001,024, but nothing in between.

We all know that integer data types such as int can store consecutive numbers. Float can not only store integers but also numbers with a fraction. Why can't float represent any in-between number, e.g. 3,000,000,001?

First, let's look how float represents 3,000,000,000 in the memory. A float consists of 4 bytes. The whole bits are divided into three sections.

Bit No	Size	Field Name
31	1 bit	Sign (S)
23-30	8 bits	Exponent (E)
0-22	23 bits	Mantissa (M)

The formula to calculate the value is: (-1)^S × (1.0 + 0.M) × 2^E-bias
The bias used in the formula is defined as 127 for the float data type.

A piece of C# code is used to find out the bytes:

using System;

namespace FundamentalDataTypes
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(BitConverter.IsLittleEndian); // get the endianness

            byte[] bytes = BitConverter.GetBytes(3_000_000_000F);
            foreach (byte b in bytes)
            {
                Console.WriteLine(Convert.ToString(b, 2).PadLeft(8, '0'));
            }

        }
    }
}

The output is:
True
01011110
11010000
00110010
01001111

I need to know the endianness so that I can assemble the bytes in a correct order. The True in the first line of the output means that the endianness is Little Endian so the first byte in the second line of the output is the least-significant byte of the value.

S = 0 (This number is a positive number)
E = 158
M = 0.01100101101000001011110
By using the formula (-1)⁰ × (1.01100101101000001011110) × 2³¹, we can get the final bits 1011 0010 1101 0000 0101 1110 0000 0000 which are exactly the same as the ones stored in an unsigned int.

Let's analyze the above bits in the unsigned int. The first bit in position 31 is 1 which is implicit in the float. The bits from the position 30 to 8 which sums to 23 bits compose the Mantissa in the float. Any in-between number uses the bits from the position 7 to 0. However, these last 8 bits can't be represented by the float because float needs to set aside 8 bits to accommodate the Exponent. That's the reason why float can't accurately represent 3,000,000,001.

The next number after 3,000,000,000 that can be accurately represented by a float is obtained by setting the bit in position 8 of the above bits to 1. It is
3,000,000,256.

Any in-between number is approximated to either 3,000,000,000 or 3,000,000,256 (not 3,000,001,024, an error in the book).

References

https://en.wikipedia.org/wiki/Endianness
https://www.doc.ic.ac.uk/~eedwards/compsys/float

Get started with using TypeScript and TDD to solve LeetCode problems in VS Code

Matthew Gong — Sat, 23 Jan 2021 22:51:25 +0000

Introduction
Install the LeetCode Extension in VS Code
Configure the LeetCode Extension
Add Jest-based TDD Support
Select a Problem
Anatomy of the Generated File
The Initial Attempt
- Algorithm
- Test Cases
- Implementation
- Result
The Second Attempt
- Algorithm
- Test Cases
- Implementation
- Result
The Final Attempt
- Algorithm
- Test Cases
- Implementation
- Result
Conclusion

Introduction

Recently I attended an in-person interview. In the coding challenge part I was asked to solve the Anagram problem. Although the problem doesn't look tricky, I was under the self-imposed pressure of needing to solve it quickly. I intuitively chose an algorithm which checks whether every character in the first word also appears in the second one and vice versa. I did realize it has bugs. I tried to save it but failed because at the moment was I in a state of panic. When I got back home, suddenly I thought shouldn't sort-and-match be a solution? What a shame! I could have performed better.

The root cause of my failure is that I didn't catch the essentials of the problem. I need to practice. It's well-known that the leetcode.com is a platform where developers can learn and practice variety of algorithms. What's more, the leetcode.com provides an extension for VS Code so that we can solve LeetCode problems without leaving VS Code. From now on I am going to talk about the experience of using TypeScript and TDD to solve a LeetCode problem in VS Code.

Install the LeetCode Extension in VS Code

Open the Extensions panel in VS Code, find the LeetCode extension and install it. After installation, open the LeetCode panel, login to leetcode.com with our own account. We will see a navigation tree in the panel that helps us select a problem. Right clicking on a problem brings a context menu through which we can preview the problem and create a file to work on the problem.

At present, there is a technical problem that prevents users from logging into the leetcode.com. However, the workaround is given in the extension's home page.

Configure the LeetCode Extension

The LeetCode extension guides user to configure the default language and the workspace folder. These two settings can also be changed in LeetCode extension's settings page (On Mac: Code > Preferences > settings, input LeetCode in the search box to see the settings). Make sure typescript is selected as the default language.

Add Jest-based TDD Support

Run yarn init in the LeetCode workspace folder to initialize the project.
Run yarn add -D @types/jest jest typescript ts-jest to install the dependencies. The ts-jest is A TypeScript preprocessor with source map support for Jest that lets you use Jest to test projects written in TypeScript.

Add the jest.config.js file in the LeetCode workspace folder with the following content:

  module.exports = {
    preset: 'ts-jest',
    testEnvironment: 'node',
  };

Add "test:watch": "jest --watchAll" to the scripts filed in the package.json file.

Select a Problem

As you know, I just started to work on LeetCode. So, following the predefined order makes sense. I selected the [2] Add Two Numbers problem. Its difficulty level is medium. Operating on linked lists is its key point.

Anatomy of the Generated File

Let's have a look at the content of the generated file for the selected problem:

/*
 * @lc app=leetcode id=2 lang=typescript
 *
 * [2] Add Two Numbers
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {

};
// @lc code=end

After a few trials, the following features about the file are found:

The file is not a node or ES6 module because there are no statements to import modules and export values in it.
The name of the file can be changed, however, the id in the comment is immutable.
The leetcode.com runtime only cares about the content in the section demarcated by // @lc code=start and // @lc code=end. The main(addTwoNumbers) and helper functions must be put in this section. The import and export statements, types and classes coming from leetcode.com runtime should be put outside of the section. If these rules are not followed, the leetcode.com runtime will report compilation errors when the file is submitted.
The ListNode class used in the main function's parameters comes from the leetcode.com runtime. Our local environment doesn't have it. However, its definition is shown in the comment of the main function.

In order to use this file in our local environment, we need to do the following things:

Export the addTwoNumbers function, so the file turns to a ES6 module.
Extract the ListNode class from the comment and export it.

The adjusted file looks like:

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}
/*
 * @lc app=leetcode id=2 lang=typescript
 *
 * [2] Add Two Numbers
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function addTwoNumbers(
    l1: ListNode | null,
    l2: ListNode | null
): ListNode | null {

}
// @lc code=end
export default addTwoNumbers;

Now we can use TDD to drive our implementation.

The Initial Attempt

Algorithm

Convert the two linked lists to two numbers, add the numbers to get a sum, convert the sum back to a linked list.

Test cases

toNumber: a function that converts a linked list to a number.
fromNumber: a function that converts a number to a linked list.

import addTwoNumbers, {
    ListNode,
    toNumber,
    fromNumber,
} from "./2.add-two-numbers";

describe("convert a number to a linked list", () => {
    test("0 to 0", () => {
        const l: ListNode = fromNumber(0);
        expect(l.val).toBe(0);
        expect(l.next).toBeNull();
    });
    test("123 to 3 > 2 > 1", () => {
        const l: ListNode = fromNumber(123);
        expect(l.val).toBe(3);
        expect(l.next.val).toBe(2);
        expect(l.next.next.val).toBe(1);
        expect(l.next.next.next).toBeNull();
    });
});

describe("Convert a linked list to a number", () => {
    test("0 to 0", () => {
        const l: ListNode = new ListNode(0, null);
        expect(toNumber(l)).toBe(0);
    });
    test("3 > 2 > 1 to 123", () => {
        const l: ListNode = new ListNode(
            3,
            new ListNode(2, new ListNode(1, null))
        );
        expect(toNumber(l)).toBe(123);
    });
});

describe("Add two numbers", () => {
    test("Example 1", () => {
        const l1 = new ListNode(2, new ListNode(4, new ListNode(3, null)));
        const l2 = new ListNode(5, new ListNode(6, new ListNode(4, null)));
        const s = addTwoNumbers(l1, l2);
        expect(toNumber(s)).toBe(807);
    });
    test("Example 2", () => {
        const l1 = new ListNode(0, null);
        const l2 = new ListNode(0, null);
        const s = addTwoNumbers(l1, l2);
        expect(toNumber(s)).toBe(0);
    });

    test("Example 3", () => {
        const l1 = new ListNode(
            9,
            new ListNode(
                9,
                new ListNode(
                    9,
                    new ListNode(
                        9,
                        new ListNode(9, new ListNode(9, new ListNode(9, null)))
                    )
                )
            )
        );
        const l2 = new ListNode(
            9,
            new ListNode(9, new ListNode(9, new ListNode(9, null)))
        );
        const s = addTwoNumbers(l1, l2);
        expect(toNumber(s)).toBe(10009998);
    });
});

Implementation

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}
/*
 * @lc app=leetcode id=2 lang=typescript
 *
 * [2] Add Two Numbers
 */

// @lc code=start
function toNumber(l: ListNode): number {
    let num = 0;
    let currentNode = l;
    let exponent = 0;
    while (currentNode) {
        num += currentNode.val * Math.pow(10, exponent++);
        currentNode = currentNode.next;
    }
    return num;
}

function fromNumber(num: number): ListNode {
    const numStr = String(num);
    let headNode: ListNode = null;
    for (let i = 0; i < numStr.length; i++) {
        const digit = parseInt(numStr.charAt(i), 10);
        const node = new ListNode(digit);
        node.next = headNode;
        headNode = node;
    }
    return headNode;
}
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function addTwoNumbers(
    l1: ListNode | null,
    l2: ListNode | null
): ListNode | null {
    const num1 = toNumber(l1);
    const num2 = toNumber(l2);
    const s = num1 + num2;
    return fromNumber(s);
}
// @lc code=end
export default addTwoNumbers;
export { toNumber, fromNumber };

Result

Run yarn run test:watch. All local test cases passed. So far so good. How will leetcode.com evaluate this solution? Let's submit it. Gotchas! The 1565 of 1568 test cases passed. 3 test cases failed!

Obviously the number represented by the first linked list is too big to be handled by the algorithm. A possible solution could be using BigInt instead of Number in the toNumber and fromNumber functions. However, BigInt is a feature of ES2020, using it in leetcode.com runtime could bring other problems. A more flexible algorithm is required.

The Second Attempt

Algorithm

Convert the two linked lists to two arrays, calculate the the array for the sum by iteratively adding the digits from the two arrays in the same position, convert the array for the sum to a linked list.

Test cases

fromArray: a function that converts an array of number to a linked list.
toArray: a function that converts a linked list to an array of number.
Because of fromArray and toArray, writing test cases becomes easier.
The failed test case in the initial attempt has been added.

import addTwoNumbers, {
    ListNode,
    fromArray,
    toArray,
} from "./2.add-two-numbers";

describe("convert an array to a linked list", () => {
    test("[0] to 0", () => {
        const l: ListNode = fromArray([0]);
        expect(l.val).toBe(0);
        expect(l.next).toBeNull();
    });

    test("[2, 4, 3] to 2 > 4 > 3", () => {
        const l: ListNode = fromArray([2, 4, 3]);
        expect(l.val).toBe(2);
        expect(l.next.val).toBe(4);
        expect(l.next.next.val).toBe(3);
        expect(l.next.next.next).toBeNull();
    });
});

describe("convert a linked list to an array", () => {
    test("0 to [0]", () => {
        const array = [0];
        const l: ListNode = fromArray(array);
        expect(toArray(l)).toEqual(array);
    });
    test("2 > 4 > 3 to [2, 4, 3]", () => {
        const array = [2, 4, 3];
        const l: ListNode = fromArray(array);
        expect(toArray(l)).toEqual(array);
    });
});

describe("Add two numbers", () => {
    test("Example 1", () => {
        const l1 = fromArray([2, 4, 3]);
        const l2 = fromArray([5, 6, 4]);
        const s = addTwoNumbers(l1, l2);
        expect(toArray(s)).toEqual([7, 0, 8]);
    });
    test("Example 2", () => {
        const l1 = new ListNode(0, null);
        const l2 = new ListNode(0, null);
        const s = addTwoNumbers(l1, l2);
        expect(toArray(s)).toEqual([0]);
    });

    test("Example 3", () => {
        const l1 = fromArray([9, 9, 9, 9, 9, 9, 9]);
        const l2 = fromArray([9, 9, 9, 9]);
        const s = addTwoNumbers(l1, l2);
        expect(toArray(s)).toEqual([8, 9, 9, 9, 0, 0, 0, 1]);
    });

    test("case 1566", () => {
        const l1 = fromArray([
            1,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            1,
        ]);
        const l2 = fromArray([5, 6, 4]);
        const s = addTwoNumbers(l1, l2);
        expect(toArray(s)).toEqual([
            6,
            6,
            4,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            0,
            1,
        ]);
    });
});

Implementation

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}
/*
 * @lc app=leetcode id=2 lang=typescript
 *
 * [2] Add Two Numbers
 */
// @lc code=start
function fromArray(array: number[]): ListNode {
    let headNode: ListNode = null;
    for (let i = array.length - 1; i > -1; i--) {
        const node = new ListNode(array[i], headNode);
        headNode = node;
    }
    return headNode;
}

function toArray(l: ListNode): number[] {
    const array = [];
    let currentNode = l;
    while (currentNode) {
        array.push(currentNode.val);
        currentNode = currentNode.next;
    }
    return array;
}
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function addTwoNumbers(
    l1: ListNode | null,
    l2: ListNode | null
): ListNode | null {
    const array1 = toArray(l1);
    const array2 = toArray(l2);
    const augend = array1.length >= array2.length ? array1 : array2;
    const addend = array1.length >= array2.length ? array2 : array1;
    const sum = [];
    let carry = 0;
    for (let i = 0; i < augend.length; i++) {
        const augendDigit = augend[i];
        const addendDigit = i in addend ? addend[i] : 0;
        const digitSum = augendDigit + addendDigit + carry;
        const sumDigit = digitSum % 10;
        carry = Math.floor(digitSum / 10);
        sum.push(sumDigit);
    }
    if (carry !== 0) {
        sum.push(carry);
    }

    return fromArray(sum);
}
// @lc code=end
export default addTwoNumbers;
export { fromArray, toArray };

Result

Run yarn run test:watch. All local test cases passed. So far so good. How will leetcode.com evaluate this solution? Let's submit it. All remote test cases passed. Hooray!

Usually I will stop here because the algorithm seems to work well. However, the performance indicators show that the algorithm doesn't perform well in terms of the memory usage. Yes, I think it is caused by converting the linked lists into arrays and vice versa. How about accessing the digit in the list node directly?

The Final Attempt

Algorithm

Basically, the algorithm is the same as the one used in the second attempt, the only difference is that the list nodes are accessed directly.

Test cases

We didn't add any new functionalities in this attempt. So, the test cases keep the same as the ones used in the second attempt.

Implementation

Although the toArray and fromArray functions are not used in the algorithm, the are convenient for writing test cases, so they are retained but moved outside of the LeetCode code section.

export class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}
/*
 * @lc app=leetcode id=2 lang=typescript
 *
 * [2] Add Two Numbers
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
type Pointer = {
    l1CurrentNode: ListNode;
    l2CurrentNode: ListNode;
    carry: number;
};
function addTwoNumbers(
    l1: ListNode | null,
    l2: ListNode | null
): ListNode | null {
    const p: Pointer = {
        l1CurrentNode: l1,
        l2CurrentNode: l2,
        carry: 0,
    };
    const sumList = new ListNode();
    let slCurrentNode: ListNode = null;
    while (p.l1CurrentNode || p.l2CurrentNode) {
        if (!slCurrentNode) {
            slCurrentNode = sumList;
        } else {
            slCurrentNode.next = new ListNode();
            slCurrentNode = slCurrentNode.next;
        }
        const augendDigit = p.l1CurrentNode?.val ?? 0;
        const addendDigit = p.l2CurrentNode?.val ?? 0;
        const digitSum = augendDigit + addendDigit + p.carry;
        const sumDigit = digitSum % 10;
        slCurrentNode.val = sumDigit;

        p.l1CurrentNode = p.l1CurrentNode?.next;
        p.l2CurrentNode = p.l2CurrentNode?.next;
        p.carry = Math.floor(digitSum / 10);
    }
    if (p.carry !== 0) {
        slCurrentNode.next = new ListNode(p.carry);
        slCurrentNode = slCurrentNode.next;
    }

    return sumList;
}
// @lc code=end
export default addTwoNumbers;
export function fromArray(array: number[]): ListNode {
    let headNode: ListNode = null;
    for (let i = array.length - 1; i > -1; i--) {
        const node = new ListNode(array[i], headNode);
        headNode = node;
    }
    return headNode;
}

export function toArray(l: ListNode): number[] {
    const array = [];
    let currentNode = l;
    while (currentNode) {
        array.push(currentNode.val);
        currentNode = currentNode.next;
    }
    return array;
}

Result

The performance in terms of the memory usage improved a lot!

Conclusion

There are 1700+ problems on leetcode.com. The number is intimidating. The process of seeking the most suitable solution to a specific problem is both time-consuming and brain-consuming. However, the good result from the submission is encouraging. LeetCode extension for VS Code is a productivity tool, however, with the help of TDD, the experience can be better.

As to the performance indictors, don't take "Your runtime beats *% of typescript submissions" seriously. Sometimes the percentage is high, sometimes it is low. I think it may be affected by the load of the leetcode.com runtime. Try to submit code several times, if it keeps being low then the algorithm may need to be improved. The memory usage indicator is relatively stable and can be used to assess the level of memory usage of the algorithm.

TypeScript: Use Mapped Type to implement a Proxy

Matthew Gong — Fri, 08 Jan 2021 22:39:55 +0000

There is a piece of code in TypeScript's document about Mapped Types which illustrates how to use mapped type to implement a proxy. It clearly defines what the type of a proxy for a value is, i.e. Proxy<T> and what the type of a proxified object is, i.e. Proxify<T>. However, the implementation of the proxify function is left empty. In order to strengthen my understanding of the mapped type, I decided to implement it.

type Proxy<T> = {
    get(): T;
    set(value: T): void;
};

type Proxify<T> = {
    [K in keyof T]: Proxy<T[K]>;
};

function proxify<T extends object>(o: T): Proxify<T> {
    const result = {} as Proxify<T>;
    for (let key in o) {
        let rawValue = o[key];
        result[key] = {
            get: () => rawValue,
            set: (value) => {
                rawValue = value;
            },
        };
    }
    return result;
}

let props = { rooms: 4 };
let proxifiedProps = proxify(props);
proxifiedProps.rooms.set(5);
console.log(proxifiedProps.rooms.get()); // output 5

As you see, it's not difficult however it can help learners like me to get a better understanding of the concept.

DEV Community: Matthew Gong

Why can a float represent 3,000,000,000 and also 3,000,000,256, but nothing in between?

References

Get started with using TypeScript and TDD to solve LeetCode problems in VS Code

Table Of Contents

Introduction

Install the LeetCode Extension in VS Code

Configure the LeetCode Extension

Add Jest-based TDD Support

Select a Problem

Anatomy of the Generated File

The Initial Attempt

Algorithm

Test cases

Implementation

Result

The Second Attempt

Algorithm

Test cases

Implementation

Result

The Final Attempt

Algorithm

Test cases

Implementation

Result

Conclusion

TypeScript: Use Mapped Type to implement a Proxy