Some of the things I've learned every day since Oct 10, 2016
As might be obvious, I’m no longer making posts in this series.
A few months ago I went from being a full-time student to my first full-time software engineering position, and while I’m still learning something new every day, the major differences with respect to this project are that the things I’m now learning are 1) proprietary more often than not, prohibiting me from posting them without a considerable amount of abstraction, and 2) of a concrete and not very general nature, which doesn’t make for good/useful posting material on it’s own and also doesn’t work well with the first point.
Effectively, I’m taking a hiatus from focusing exclusively on learning abstract principles in order to focus on getting more comfortable with their implementation, and more effective in the ‘applied’ side of applied mathematics.
Even thought this project was never really meant to have an audience other than myself, thanks to anyone who bothered to read this stuff. I hope you found it useful in some sense of the word.
While looking over the sequence representing the number of bit flips required in a sequence of increment operations, I saw that there’s an alternative and very easy way of producing 
where 
The reason for this pattern should be pretty obvious, and from these it’s easy to show the amortized runtime of increment in essentially the same way as in my previous post.
I’m not sure what the term is for this form of iterative sequence generation is, but it’s vaguely reminiscent of Lindenmayer systems.
The Hamming weight (commonly known as population count or popcount)of a string is simply the number of non-‘zero’ symbols in that string. For instance, the Hamming weight of the base-10 string 0108303809 is 6.
Most commonly, though, Hamming weight is taken over binary strings (or bit ‘vectors’ or some other representation of the same thing). In this context the weight is simply the number of 1’s present. Note this is equivalent to both the 
Note that it also follows immediately, almost by definition, that the Hamming distance of 2 binary strings 
Popcount has a lot of different applications, ranging from picking public keys within the RSA scheme to efficient evaluation of game states in board games using ‘bitboard’ representations. As a result, how to efficiently perform the operation has been subject to substantial research, which I’ll hopefully be able to write a post about later.
Naive division (schoolbook “long division”) runs in 
One of these — the Newton-Raphson algorithm — runs in 
I’ll try to write a more detailed post later once I fully understand the details, but a high level overview is that the algorithm, given numbers 
of (by using Newton’s method to find the root of the equation 
(by performing the multiplicative iteration 
)).
by .What’s the runtime of incrementing a binary number? When writing my last post I learned that the amortized runtime of 
(Below I make the assumption that in performing
The most obvious upper bound one can find on the number of operations (checking bits, flipping bits) to increment a number 
resulting in an amortized runtime of 
Looking closer, we see that the number of bits we need to look at or modify in an incrementation is in general less than the number of bits representing the number, because the ‘carry’ operation will usually not go all the way through to the leftmost bit. In fact, exactly half the time the rightmost bit will be 0, meaning incrementation will require looking at and modifying only that single bit.
Looking more generally at this pattern, we also see that the next bit (from the right) gets looked at and swapped exactly every 2 incrementations, the next every 4 incrementations, and so on:
k | swap bit0 | bit1 | bit2 | bit3 | bit4 1 | 1 2 | 1 | 1 3 | 1 4 | 1 | 1 | 1 5 | 1 6 | 1 | 1 7 | 1 8 | 1 | 1 | 1 | 1 9 | 1 10| 1 | 1 11| 1 12| 1 | 1 | 1 13| 1 14| 1 | 1 15| 1 16| 1 | 1 | 1 | 1 | 1
Summing the total number of operations over columns (the different bits on which they can be done) we find the the actual bound to be
This gives us what we want: an amortized per-operation runtime of
Following up on the post on binomial trees, here’s an overview of binomial heaps and the mechanisms behind their various operations.
A binomial heap is merely a collection of binomial trees, each of which satisfy the heap invariant, having either 0 or 1 tree for each order 
Recall that a binomial tree of order 
Source: https://en.wikipedia.org/wiki/Binomial_heap
Note that this also implies that a heap with 
The
The crucial aspect of how the merge operation works is that merging two binomial trees of order 
Source: https://en.wikipedia.org/wiki/Binomial_heap
Because of this, one can merge 2 binomial heaps with 
Source: https://en.wikipedia.org/wiki/Binomial_heap
The analogous binary addition would be adding the numbers 1011 and 0011 to get 1110.
Insertion of a new element into a heap can be simply accomplished by creating a new heap with just the one tree/element and merging it with the original. This takes
Since there are at most 
However, removing the minimum element takes
Setting/modifying the value of an element takes
To delete an element (again assuming you know where it is), you can simply set its priority to 
A Binomial Tree is an abstract data structure which is useful for including making heap-like data structures (binomial heaps) which are easily mergeable. For 
is a tree with a single root node and no children. has a root with its children being 
.To illustrate, below are the binomial trees of orders 0, 1, 2, and 3:
Source: https://en.wikipedia.org/wiki/Binomial_heap
A few properties of this structure that are fairly self-evident are that
Related to this last property is the fact that you can alternatively form 
As a final note, the name binomial tree results from the fact that 
The typedef keyword in C is (from what I can tell; I may be off) used to create an alias for a given type. The general syntax is
typedef <previously-defined type> <alias>;
For instance, the line
typedef int size;
simply lets the compiler know that the word size refers to the type already defined as int. You can then compile the code
typedef int size;
size k = 10;
printf("The size is %d\n", k);
printf("The size of the size datatype is %lu\n", sizeof(size));
which will print out
The size is 10 The size of the size datatype is 4
In the context of C structs, typedefs can be used to simplify syntax in a way that’s a bit more reminiscent of Java syntax for classes and objects. For instance, if you had a struct defined as
struct person {
char * name;
int age;
}
To declare a variable of this type you would have to say
struct person p;
which is a little bit awkward. With typedefs, you have the opportunity to trade that off with a more awkward struct declaration
typedef struct {
char * name;
int age;
} person;
which then gives you the option to simply declare your variable with
person me;
Before today I’d been loosely familiar with the use of the dereferencing operator * in the C language, but today as I’ve begun a refresher (really a primer) in C I find myself actually understanding this operator and its counterpart & for the first time.
When a pointer variable p is assigned with int *p; p = &x;, where x is a previously declared integer variable, p itself becomes a new 8-byte variable which has as its value the address of the variable x it points to. The declaration and assignment say, respectively, “p is a variable which has as its value the address of an integer” and “take the address of the variable x (which the program has to keep track of anyway) and assign it as the value of p.”
You can have pointers-to-pointers-to-pointers, if you want to, since pointers are themselves variables and have their own addresses. Thus the following code
int main()
{
int x = 5;
int *p;
int **q;
int ***r;
p = &x;
q = &p;
r = &q;
printf(x == *p ? "true\n" : "false\n");
printf(x == **q ? "true\n" : "false\n");
printf(p == **r ? "true\n" : "false\n");
return 0;
}
will print
true true true
However, while you can dereference a pointer multiple times (e.g. r***), if you try to evaluate the expression
&&x
it will throw an error. This is just because `&x` will give you the literal value of the address of `x` (which has no address), and trying to get the address of a literal is nonsensical.
Today I learned how to implement a Min Heap using a dynamically-sized array and the typical representation of a complete binary tree as an array where the children of index 
Specifically, I used Python’s List data structure for an impromptu implementation of a basic min heap which uses its items’ values themselves for comparisons. Below is my code (which I wrote in like 5 minutes so it’s not super pretty):
class MyMinHeap(object):
"""
Implementation of Min Heap using dynamic array
"""
def __init__(self):
self.heap = []
self.size = 0
def peek(self):
if self.size == 0:
return None
return self.heap[0]
def push(self, val):
self.heap.append(val)
self.size += 1
# float up
curr = self.size - 1
while curr != 0:
parent = (curr - 1) // 2
# if min heap invariant violated, swap with parent
if self.heap[curr] < self.heap[parent]:
self.heap[curr], self.heap[parent] = (self.heap[parent], self.heap[curr])
curr = parent
else:
break
def pop(self):
if self.size == 0:
return None
# replace root of tree with last child, maintaining completeness
return_val = self.heap[0]
self.heap[0] = self.heap[-1]
del self.heap[-1]
self.size -= 1
# sink down
curr = 0
while 2 * curr + 1 <= self.size:
left = 2 * curr + 1
right = 2 * curr + 2
# pick which child has smallest value
if right <= self.size and self.heap[right] < self.heap[left]:
child = right
else:
child = left
#swap with child if necessary to maintain min heap invariant
if self.heap[child] < self.heap[curr]:
self.heap[curr], self.heap[child] = (self.heap[child], self.heap[curr])
curr = child
else:
break
return return_val
Today I Learned 