New Keyboard & Mouse

I’ve been using A4TECH Comfort Key Rounded Keycaps for quite sometime and I love it. The keyboard feels really smooth and the keys are very easy to press. But recently, I’ve started to play games again (that’s a topic for another post). I think I played so much that it amounted to more than 350+ hours of gameplay within 1-2 months. Anyways, as I have been playing games on this keyboard, it has started to feel clunky and I can feel the keys not being pressed properly. Same goes for the mouse I was using. So, I thought its time for a change. Then I started researching various keyboards and their types. The most common are the membrane and mechanical ones. Mechanical keyboards are preferred by most gamers because of the feedback from the keys that they provide. As I started looking into different options for mechanical keyboards, I found that most of them are quite costly. Specially the ones which have Cherry MX switches. Compared to that, keyboards with Kailh switches are cheaper. However, I found a new type of switches. Optical switch. A4TECH (Bloody brand) creates keyboards with optical switches which they call Light Strike or LK for short. Obviously, I needed to know the difference between the optic switches and the currently available mechanical switches (note that, optical switches are also mechanical switches since they also have mechanical moving parts). I found that optical switches trigger key presses with the help of light. This helps to register key presses insanely fast (according to A4TECH its 0.2ms).

.alt(‘Optic switch’))

I thought, this is it! I’ll buy a keyboard with this type of switch. So, I got myself a A4TECH Bloody B820R keyboard. Honestly, I’m in love with how amazing this keyboard feels when I’m typing on it. Totally worth the money :D

Edit: Oh, I forgot to mention, I also bought the MSI Interceptor DS B1 Gaming Mouse. I found it at quite a cheap price (around $10). It supports 3 levels of DPI change (800, 1200 and 1600 I guess.)

Rabin Karp Algorithm

Rabin Karp algorithm is a string search algorithm with running time of O(|s|+|t|) where s is the pattern to search for and t is the text in which the pattern is to be searched. It utilises a so called rolling hash to compare the strings to find matching patterns.

The idea is, instead of comparing character by character which will take O(|s|*|t|) time, we utilise hashes to compare strings in O(|s|+|t|) time. For this, we need to precompute hashes of the prefixes of t and the hash of s and use the rolling hash property to compare the substrings of t.

Algorithm

1. Compute the hash of s. This will need O(|s|) time.
2. Compute the hash of all prefixes of t.
3. Now, all substrings of t of length |s| can be compared to s in O(1) time. So, compare each substring of length |s| to s which will take O(|t|) time.

Hence, the final time complexity is O(|s|+|t|) (step 1 and 2+3).

Implementation

#include <bits/stdc++.h>
using namespace std;

vector<int> rabin_karp(string const& s, string const& t) {
    const int p = 131;
    const int m = 1e9 + 9;
    const int S = s.size(), T = t.size();

    // Precompute all powers of P (mod m)
    vector<long long> p_pow(max(S, T));
    p_pow[0] = 1;
    for (int i = 1; i < (int)p_pow.size(); ++i)
        p_pow[i] = (p_pow[i-1] * p) % m;

    // Compute hash of all prefixes of t
    vector<long long> h(T + 1, 0);
    for (int i = 0; i < T; ++i)
        h[i+1] = (h[i] + t[i] * p_pow[i]) % m;

    // Compute hash of s
    long long h_s = 0;
    for (int i = 0; i < S; ++i)
        h_s = (h_s + s[i] * p_pow[i]) % m;

    // Match the hash of s (h_s) with the hash of substrings
    // of t (h[0..|S|]) and store the matches
    vector<int> occurences;
    for (int i = 0; i + S - 1 < T; ++i) {
        // Hash of substring of t from index i+1 to i+S inclusive
        long long cur_h = (h[i + S] + m - h[i]) % m;

        /*
        First index of cur_h is a multiple of p_pow[i], second
        index is a multiple of p_pow[i+1] and so on... like:
        t[i]*p_pow[i] + t[i+1]*p_pow[i+1] + t[i+2]*p_pow[i+2]...

        But, first index of h_s is a multiple of p_pow[0],
        second index is a multiple of p_pow[1] and so on...
        s[0]*p_pow[0] + s[1]*p_pow[1] + s[2]*p_pow[2] + ...

        Since, the multiples of both are different, we need to
        make the multiples same in order to get the same hash.
        So, we multiply h_s with p_pow[i] to change the multiples
        to p_pow[i], p_pow[i+1], ... from p_pow[0], p_pow[1]...

        h_s * p_pow[i] thus results to:
        s[0]*p_pow[i] + s[1]*p_pow[i+1] + s[2]*p_pow[i+2]...
        */
        if (cur_h == h_s * p_pow[i] % m)
            // if both hashes are same, we found a match and store it
            occurences.push_back(i);
    }

    return occurences;
}

int main() {
    vector<int> pos = rabin_karp("abc", "abcabcbcdabcabc");
    if (pos.size() > 0)
        for (int i : pos) cout << i << endl;
    else
        cout << "Pattern not found" << endl;

    return 0;
}

String Hashing

I’ve always wondered how c++ std::map works. Turns out its typically implemented as a Binary Search Tree (BST for short). Why a BST? The most probable answer I can come up with, is how hashing is implemented. How? Let’s see.

I’ll just go over string hashing as I don’t know the specifics about how other data types are hashed. Basically, string hashing is a process of turning any string into a unique integer that identifies only that particular string. So, for example hash(a) != hash(b) for any two strings a and b if a != b. In pactice, generating a completely unique integer is not possible in c++ because of limitations in integer sizes.

Generating a string hash is quite easy. Here’s how we’ll do it. There are other ways to generate a hash.

Formula

hash(s) = { s[0] + s[1].p + s[2].p^2 + … + s[n-1].p^(n-1) } % MOD m

s is the target string, p is represents power (we’ll use the powers of a prime number) and, m denotes a number to MOD with (this should be as large as possible) and n denotes the length of the string.

Code

#include <bits/stdc++.h>
using namespace std;

// NOTE: hashing only for lowercase letters
// In case of uppercase or other letters, set p = 53 and
// change the c-'a'+1 line to something suitable if necessary
long long compute_hash(string const& s) {
    const int p = 31;
    const int m = 1e9 + 9;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}

int main() {
    cout << compute_hash("a") << endl;
    cout << compute_hash("b") << endl;
    cout << compute_hash("c") << endl;
    cout << compute_hash("abc") << endl;
    cout << compute_hash("abcd") << endl;
    cout << compute_hash("sadfasdfasdfadsfasdfasdfasdfasdfas") << endl;
    cout << compute_hash("sadfasdfasdfadsfasdfasdfasdfasdfaa") << endl;

    return 0;
}

Output

1
2
3
2946
122110
377376292
787694314

As can be seen, we’re doing mod with a certain integer m which is a prime number. Selecting a prime for both p and m is important for avoiding collisions (same hash for different strings) as much as possible. If we didn’t mod with 10^9 + 9, it would be modded when the multiplications overflowed the max integer size.

Now, coming to why std::map is implemented as a BST. It’s because we can’t necessarily take an array of size 10^9 + 9 to store the hashes for mapping as it will take a lot of memory and the compiler will also complain about it. We need to come up with a data structure which can store arbitrary integers and this is where BST comes in handy. A simple implementation might look like this:

Code

struct node {
    long long key;
    string value;
};

node BST[100];

long long compute_hash(string const& s);

string search(node *n, string k) {
    long long hash_of_k = compute_hash(k);
    if (hash_of_k exists in BST) return node->value;
    else return "";
}

void insert(node *n, string val) {
    long long hash_of_val = compute_hash(val);
    if (hash_of_val exists in BST) {
        n->value = val;
    } else {
        node new_node;
        new_node->k = compute_hash(val);
        new_node->value = val;
    }
}

int main() {
    node *root = new node;

    insert(root, "abc");
    insert(root, "test");

    cout << search(root, "abc") << endl;
    cout << search(root, "hello") << endl;
}

Obviously, the std::map is implemented in a more sophisticated way. I’ve just thought about how it might be represented in a very simple way.

Newton Raphson

Suddenly I had the urge to learn the basics of Go (lang) and see what’s so special about it. So, I went to golang and from there I started the “A Tour of Go” short tutorial. It’s kind of like an interactive tutorial. As I progressed through the tutorial, I found a very interesting algorithm for finding the square root of a number. It’s the Newton-Raphson root-finding algorithm. I literally forgot about it, but I learnt about this in my 5th semester’s math course.

I should quote one important part from the tour:

If you are interested in the details of the algorithm, the z² − x above is how far away z² is from where it needs to be (x), and the division by 2z is the derivative of z², to scale how much we adjust z by how quickly z² is changing. This general approach is called Newton’s method. It works well for many functions but especially well for square root.

Code

package main

import (
    "fmt"
    "math"
)

func Sqrt(x float64) float64 {
    z := 1.0

    for i := 1; i <= 15; i++ {
        z -= (z*z - x) / (2*z)
    }

    return z
}

func main() {
    for i := 1; i <= 20; i++ {
        fmt.Println(i, math.Sqrt(float64(i)), Sqrt(float64(i)))
    }
}

Output

1 1 1
2 1.4142135623730951 1.4142135623730951
3 1.7320508075688772 1.7320508075688772
4 2 2
5 2.23606797749979 2.23606797749979
6 2.449489742783178 2.449489742783178
7 2.6457513110645907 2.6457513110645907
8 2.8284271247461903 2.82842712474619
9 3 3
10 3.1622776601683795 3.162277660168379
11 3.3166247903554 3.3166247903554
12 3.4641016151377544 3.4641016151377544
13 3.605551275463989 3.605551275463989
14 3.7416573867739413 3.7416573867739413
15 3.872983346207417 3.872983346207417
16 4 4
17 4.123105625617661 4.123105625617661
18 4.242640687119285 4.242640687119286
19 4.358898943540674 4.358898943540673
20 4.47213595499958 4.47213595499958

Note: the left most numbers indicate line numbers, not output values. First column indicates i, second column indicates standard library’s math.Sqrt() function and the third column indicates my hand-written Sqrt() function using the Newton-Raphson root finding algorithm.

As seen from the output results, the algorithm is quite accurate even for just 10-15 iterations it gives us almost the same accuracy as the standard library’s square root function. I think, I might start using it for my own code instead of the C/C++ builtin sqrt() function.