GaeBlogX Arista Networks, Software-Defined Networking

• # Bit Hacks

2017-06-20
Yanxi Chen

### Find the minimum r of two integers x and y

r = r ^ ((x ^ y) & -(x < y));


Compute (x + y) mod n, assuming that 0 <= x < n and 0 <= y < n.

z = x + y;
r = z - (n & -(z >= n));


### Round up to a Power of 2

Compute $2^{\left \lceil{\log n}\right \rceil }$

// 64-bit integers
--n;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
++n;


Decrement and increment handles the case where n is already a power of 2.

2017-06-11
Yanxi Chen

# Introduction to Cache Oblivious Algorithms

Cache oblivious algorithms are the algorithms that performs well even when they are not aware of the caching model.

## The Cache Model

We assume two level memory: cache and main memory. The block size is $B$. The size of the cache is $M$. The size of main memory is assume infinte. If we want to access some data that is not in the cache, we need to pull the whole block that contains the data to the cache first. And we might kick something else and we need to write it back to memory.

1. Accesses to cache are free, but we still care about the computation time (work) of the algorithm itself.
2. If we have an array, it might not be aligned with the blocks. So it will be some extra things at the beginning and the end that doesn’t consume a whole block but we need the extra 2 blocks.
3. Count block memory transfers between cache and main memory. (number of block read/write) Memory Transfer $MT(N)$ is a function of $N$, but $B$, $M$ are parameters and does matter.

## Cache Oblivious Algorithm

• Algorithms don’t know $B$ and $M$
• Accessing memory automatically fetch block into memory & kick the block that will be used furthest in the future (idealized model)
• Memory is one big array and is divided into blocks of size $B$

Note: if the algorithm is cache oblivious and is efficient in the 2-level model, it will be efficient for k-level model (L1, L2, L3, … caches)

2017-06-10
Yanxi Chen

# Basic Quantum Computing with Least Physics Possible

## Classical Probability Bit

We will start by talking about classical probability bit. Here is the one bit representation $p_0$, $p_1$ are the probability of being $0$, $1$ respectively.

And here is the n-bits representation

So we can do some transformation to the bit:

Or if we have two bits

and want to do an XOR with two dependent bits

But it is not possible (physically) to do something like this, which kind of does XOR with two independent bits:

In other words, physically, in our universe, we can only do $l_1$ norm linear tranformation.

• # 赫炎前四章感想

2017-06-09
Yanxi Chen

打完四章多一些，先说说感想吧。赫炎描绘了一个破败，腐烂不堪的社会。 在这无可救药的社会里，生活着各式各样的人。卖鸦片的章鱼老鸨，情报屋的双子， 每天挖地洞的疯子，当然还有我们的男主一家。不得不说赫炎对人物的刻画实在是非常不错， 寥寥几句对话就能让你对每个人物的性格特征熟记于心，本命アティ！正也因为这人物刻画， 玩家能从这原本腐朽的社会看到了一丝丝光明。很多对话以及心理描写玩家看了能会心一笑， 实在是非常不容易。

总的来说，整个气氛用一个词来形容就是破败感，残缺不堪的社会以及人们。 这也衬托出了所谓人类的美丽。就算是生活在这最底层的异形的社会中，人类总是充满着耀眼的光辉。 作者的文笔以及BGM还是非常不错的。

当然最坑爹的就是战斗场面基本复制黏贴。。笔墨都用来写别的了，嘛倒也无可厚非。

2017-06-09
Yanxi Chen

# Some Notes about Fibonacci Heaps

### Operations:

• make_heap Return an empty heap
• insert(i,h) Add item $i$ to heap $h$.
• find_min(h) Return the smallest item in heap $h$
• delete_min(h) Delete min from heap $h$ and return it
• meld(h1, h2) Return the heap formed by putting all elements in $h_1$ with all the elements in $h_2$. $h_1$ and $h_2$ are destroyed.
• decrease_key(delta, i, h) Assume that position of $i$ is known. Decrease the value of item $i$ of delta (delta > 0)
• delete(i, h) Assume that position of $i$ is known. Delete $i$ from heap

2017-06-08
Yanxi Chen

# Some Notes of Introduction to Algorithm

## Fiboniacci Number

$Running\ Time = \theta(\log_2(n))$

## Order Statistics

Given n elements in an array, find $k^{th}$ smallest element.

• Quick Select
• Expected running time $\theta(n)$
• Worse case $\theta(n^2)$
• Worse-case linear time order statistics
Select(i, n)
1. Divide n elements into [n/5] groups of 5 elements each. Find the median of each
group. O(n)
2. Recurrsively select the medium x of the [n/5] group medians. T(n/5)
3. Partition with x as pivot, let k = rank(x). O(n)
4. if i==k then return x
if i<k then recurrsively select ith smallest element in left part
else then recurrsively select (i-k)th smallest element in upper part


Search
Categories