Share: Brisingr

You are capable of such a feat?

I am, but I do not know if I will be able to summon the magic I will need when I am standing before Isidar Mithrim. My ability to cast spells is not subject to my own desires. At times, it is as if I have gained a new sense and I can feel the pulse of energy within my own flesh, and by directing it with my will, I can reshape the world as I wish. The rest of my life, however, I can no more cast a spell than a fish can fly. If I could mend Isidar Mithrim, though, it would go a long way toward earning us the goodwill of all the dwarves, not just a select few who have the breadth of knowledge to appreciate the importance of their cooperation with us.

(Moon+ Reader Pro v2.6.5, Brisingr)

IP protocol — RFC study notes.

Here’s the original. (Recommended for the studious).

Scope limits:

<blockquote>
There are no mechanisms to augment end-to-end data
reliability, flow control, sequencing, or other services commonly
found in host-to-host protocols.
</blockquote>

Basic Functions:
1. Addressing:
a, Routing: Based on the addresses carried in the header, the datagrams are sent to destinations.
Which path they take is decided by routing.

2. Fragmentation:
The IP layer/module fragments the given data to it into datagrams for transmission through “small packet networks”.

Each Internet Datagram is an independant entity.
4 Mechanisms:
1. Type of Service:
Quality of service, as codified into parameter values defined by the layers above, and implemented/honoured by the gateways, to choose the transmission parameters.
2. Time to live:
Self-destruct time-limit for each datagram. Cool like self-destruct messages in Spy movies(mission impossible)
3. Options:
Used for control functions/commands
4. Header Checksum:
Like any other checksum, check to make sure the data transmitted is correct.

Addressing:
Addresses vs Names vs Routes:
address == Fixed length four octets
octet — eight bits.
Address starts with
1. Network Number
2. local address/rest field
# TODO: an example would help here.
types of local address:
a, highest order bit is zero, next 7 bits the network, last 24 the local address
b, high order two bits 10, next 14 bits the network, last 16 the local address
c, high order 3 bits 110, next 21 bits are the network, and last 8 the local address
Address Formats:
<blockquote>
Address Formats:

High Order Bits Format Class
————— ——————————- —–
0 7 bits of net, 24 bits of host a
10 14 bits of net, 16 bits of host b
110 21 bits of net, 8 bits of host c
111 escape to extended addressing mode
</blockquote>
Fragmentation:
— Used when a packet originates in a local net of higher packet size than the target local net
— packets can be flagged to never fragmented(but dropped if the case above happens)
— fragments have
identification field
offset field
more-fragments flag
Also have the same header as the original IP packet.

Gateways:
Forward datagrams between networks
<blockquote>
+——————————-+
| Internet Protocol & ICMP & GGP|
+——————————-+
| |
+—————+ +—————+
| Local Net | | Local Net |
+—————+ +—————+

Gateway Protocols
</blockquote>
Internet Header format:
<blockquote>
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version| IHL |Type of Service| Total Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Identification |Flags| Fragment Offset |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Time to Live | Protocol | Header Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Options | Padding |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Example Internet Datagram Header
</blockquote>

version: 4 bits
IHL : 4 bits, length of the header in 32 bit words
Type of Service: 8 bits
So the choices boil down to low-delay, high-reliability and high-thoroughput.
<blockquote>
Bits 0-2: Precedence.
Bit 3: 0 = Normal Delay, 1 = Low Delay.
Bits 4: 0 = Normal Throughput, 1 = High Throughput.
Bits 5: 0 = Normal Relibility, 1 = High Relibility.
Bit 6-7: Reserved for Future Use.
</blockquote>

Total Length: 16 bits
— length of the datagram measured in octets, Max 65535 octets.
— hosts are recommended to send > 576 octets.(576 heuristically arrive number, probably higher nowadays??)
Identification: 16 bits
— identification for fragmentation and re-assembling.
Flags: 3 bits
<blockquote>
Bit 0: reserved, must be zero
Bit 1: (DF) 0 = May Fragment, 1 = Don’t Fragment.
Bit 2: (MF) 0 = Last Fragment, 1 = More Fragments.

0 1 2
+—+—+—+
| | D | M |
| 0 | F | F |
+—+—+—+
</blockquote>

Fragment Offset: 13 bits
Time to live: 8 bits
Protocol: 8 bits
— Next level protocol used
Header Checksum: 16 bits
<blockquote>
The checksum field is the 16 bit one’s complement of the one’s
complement sum of all 16 bit words in the header. For purposes of
computing the checksum, the value of the checksum field is zero.
</blockquote>

Source Address: 32 bits
Destination Address: 32 bits
Options: variable
— transmission of options is optional.
2 formats:
a, Single octet of option-type
b, option-type octet + option-length octet + option-data octets
option-type octet:
1 bit — copied flag( whether to copy this option to each of the fragments)
2 bits — option class
option-classes:
<blockquote>
0 = control
1 = reserved for future use
2 = debugging and measurement
3 = reserved for future use
</blockquote>
5 bits — option number
Defined internet options.
<blockquote>
CLASS NUMBER LENGTH DESCRIPTION
—– —— —— ———–
0 0 – End of Option list. This option occupies only
1 octet; it has no length octet.
0 1 – No Operation. This option occupies only 1
octet; it has no length octet.
0 2 11 Security. Used to carry Security,
Compartmentation, User Group (TCC), and
Handling Restriction Codes compatible with DOD
requirements.
0 3 var. Loose Source Routing. Used to route the
internet datagram based on information
supplied by the source.
0 9 var. Strict Source Routing. Used to route the
internet datagram based on information
supplied by the source.
0 7 var. Record Route. Used to trace the route an
internet datagram takes.
0 8 4 Stream ID. Used to carry the stream
identifier.
2 4 var. Internet Timestamp.
</blockquote>

Each of these options then have more specifications about what they mean, and how they should work. That goes on for a couple of pages.
There are a couple more pages discussing some implementation requirements and some examples but this is as far a i go.

Urlshortener in python

I attempted this(url shortener) project as a kind of a dare. Over a lunch and beer one day, atul casually commented that a url shortener,

would be a ten minute work for someone like you and a blog about it would make a nice fit for my site.

I was not sure it’s a 10 minute work, but sounded like a small fun project for weekend attempts.

It took more than half a day, for me to be content(not happy, but just content) with the resulting work.

Nevertheless, it was time well spent. Here’s the link to the actual project.<a href=”https://github.com/emofeedback/urlshortener”>

 

Few clarifications about some choices(should i call it software engineering??):

  1. Redis because it’s extremely efficient, stays in RAM, and has some unconfirmed reports of being used to power china’s internal twitter clone.
  2. Used 5 chars, because, well the internet is big, and thought it’s a good number to cover most unique urls.(especially, when combined with the 78 chars allowed for url, i.e: 5^78) Thanks to a colleague’s suggestion for the idea, i was thinking about hashing/random before his suggestion. (Note to self: Fucking stop believing “outsourced magic is better” shit.)

3.A hash map of shortened url-> original url and original url -> shortened url was kinda against my idea. I still keep thinking this is too much memory, we should find a different way. I think if I take away the use-case of already shortened url, being submitted for new shortening, should return, I can eliminate the original url -> shortened url hash map.

  1. To check if a new original url has already been shortened, the hyperloglog comes to the rescue. Just pass it through the HLL algorithm and see if it returns True and False.
  2. From the UI point, well i just put up a minimal html form to take a original url and return a json.
  3. Yet to do, add a proper fabric script to setup virtualenv, python packages, redis install and nginx config and restart nginx.

You can see it live here.
 

 

Share: Brisingr

Never ask me to alter a weapon merely in order to improve its appearance,” admonished Rhunön. “A weapon is a tool, and if it is beautiful, then it is beautiful because it is useful. A sword that could not fulfill its function would be ugly to my eyes no matter how fair its shape, not even if it were adorned with the finest jewels and the most intricate engraving.”

(Moon+ Reader Pro v2.6.5, Brisingr)

10000 hr practice study.

Once again, as I was traipsing around the internet , I came across yet another reference to the 10,000 hrs of deliberate practice, paper quoted yet again.(Thankfully, it was arguing more for the deliberate practice part than the 10,000 hrs). Nevertheless, i got sick of reading and hearing about it, and for once and all decided read the actual damn paper and make up my mind. The following is notes, I used for the purpose cleaned up a little.

Here’s a Summary of what i found by reading the copy found here. http://www.mockingbirdeducation.net/uploads/5/4/0/7/5407628/ericsson_1993.pdf

I’ll skip most of the preface, and survey parts as they were too much, and too hard to actually form a opinion, without getting into a rabbit-hole search of references and many days trying to read and digest them.

Will just observe that this was a paper from 1993.
There were 2 studies, This is the first one:
Study I:
Experimental Method:
Subjects:
Student Musicians(Violinists): From some univ in Germany.
1. Professors recommended 14 of them to be potential professionals. 10 of those were studied.(4 excluded for bad German, and pregnancy)
(Tagged as best violinists)
2. Control group was another 10 students from a different university with lower admission standards.selected again from professors recommending as good violinists(Tagged as music teachers)
They matched sex and age across these two groups.
3. Another control group of 10 middle-aged violin professionals

Note: This seems to fall under what can be called stratified random sampling.

Data Collection:
1. 3 sessions of interviews with the subjects.
a, autobiographical + question to estimate the hours of practiceper year, since the subject started playing.
A pilot study had helped form a taxonomy of 12 music related activities and non-related activities. This taxonomy was presented and explained. Then they were asked to rate each of these activities/categories(some were non-violin players in the control group) on 3 Dimensions.
1. How relevant it was in terms of performance improvement.
2. How much effort was required to perform it?
3. How enjoyable it was regardless of the result.

b, Questions about practice and concentration, + previous days’ activities and subjective estimates.
Study II:

Results:
What I interpret from the graphs. best violinists vs teachers’ there is quit a bit of number of hours practicing almost no difference. No difference between best violinists vs good violinists(professional violinists).
When plotted from age since they started playing the solo playing time/practice Teachers fall behind everyone else very clearly, but not much difference between the others.

C Arch patterns

There are some patterns you can see in C code.
Mostly signs that give off indications of what are the data structures used.

For example, this is a code from cpython source(Include/object.h):(obfuscated for illustrative purposes)

typedef struct XXX {
struct XXX *nnn;
const char* string;
PyObject *object;
} XXX;

The sign here is that the struct name (XXX here) is used, within the
struct definition for another element. In this case, this element is a pointer to the self. This indicates this is a linked list.

It can be a circular linked list or singly linked list with the last node pointing to NULL. That distinction can be guessed with initial values. Given it’s not being initialized, I would guess this is a circular linked list, but to verify I will have to check parts of the code where this struct is initialized.

On the contrary, if I had needed this to be a doubly linked list instead, I would have defined it this way instead.

typedef struct XXX {
struct XXX *ppp;
struct XXX *nnn;
const char* string;
} XXX;

The point being two pointers to the same structure, but this does not necessarily mean there’s a doubly linked list implementation. If someone’s trying to write Obfuscated C code, they might use this struct but use it differently, on purpose to hinder code readability.

Oh, by the way, this could also be made into a binary-tree structure by manipulating the insertions into *ppp, *nnn, as new structs. In case of making this a binary tree, we would need a check to make sure no new object linked to *nnn(and *ppp) is already in the structure. Infact it would be more apt naming those *left and *right than *ppp, *nnn.

i.e:

typedef struct XXX {
struct XXX *left;
struct XXX *right;
const char* nodelabel;
} XXX;

Note purely in terms of the type of elements composing/constituting the struct, there’s no difference between this and the above doubly linked list. However, the difference will arise out of how these struct pointers are inserted.
#TODO: CODE SAMPLE HERE.

Now, I’ll graduate to the next data structure, I believe is logically next, (and is one of my favourite) data structure — Graphs.

Linked lists, are simply a very specific case of a graph(which can be called a specific case of sets).
Linked lists are simply graphs restricted to only one edge,(directed) between any two nodes.
Ofcourse, am assuming planar graph<link>,(i.e: one edge can only connect two nodes) and not hyper-graph<link>(think nodes in 3D, and edges that can connect more than “2 nodes”.)

So, Opencog<link> is a open-source attempt to create an Artificial General Intelligence system.
At the core of it is a hypergraph<link to why hypergraphs>(aka atomspace).
Note: this is a C++ project.

Here’s the code for defining an atom:

class Atom
: public std::enable_shared_from_this<Atom>
{
friend class ::AtomUTest; // Needs to call setFlag()
friend class AtomTable; // Needs to call MarkedForRemoval()
friend class ImportanceIndex; // Needs to call setFlag()
friend class Handle; // Needs to view _uuid
friend class SavingLoading; // Needs to set _uuid
friend class TLB; // Needs to view _uuid

private:
//! Sets the AtomTable in which this Atom is inserted.
void setAtomTable(AtomTable *);

//! Returns the AtomTable in which this Atom is inserted.
AtomTable *getAtomTable() const { return _atomTable; }

protected:
UUID _uuid;
AtomTable *_atomTable;

Type _type;
char _flags;

TruthValuePtr _truthValue;
AttentionValuePtr _attentionValue;

// Lock needed to serialize AV changes.
// Just right now, we will use a single shared mutex for all
// locking. If this causes too much contention, then we can
// fall back to a non-global lock, at the cost of 40 additional
// bytes per atom.
static std::mutex _avmtx;
static std::mutex _mtx;

/**
* Constructor for this class.
*
* @param The type of the atom.
* @param Outgoing set of the atom, that is, the set of atoms this
* atom references. It must be an empty vector if the atom is a node.
* @param The truthValue of the atom. note: This is not cloned as
* in setTruthValue.
*/
Atom(Type, TruthValuePtr = TruthValue::NULL_TV(),
AttentionValuePtr = AttentionValue::DEFAULT_AV());

struct InSet
{
// incoming set is not tracked by garbage collector,
// to avoid cyclic references.
// std::set<ptr> uses 48 bytes (per atom).
IncomingSet _iset;
// Some people want to know if the incoming set has changed...
AtomPairSignal _addAtomSignal;
AtomPairSignal _removeAtomSignal;
};
typedef std::shared_ptr<InSet> InSetPtr;
InSetPtr _incoming_set;
void keep_incoming_set();
void drop_incoming_set();

// Insert and remove links from the incoming set.
void insert_atom(LinkPtr);
void remove_atom(LinkPtr);

private:
/** Returns whether this atom is marked for removal.
*
* @return Whether this atom is marked for removal.
*/
bool isMarkedForRemoval() const;

/** Returns an atom flag.
* A byte represents all flags. Each bit is one of them.
*
* @param An int indicating which of the flags will be returned.
* @return A boolean indicating if that flag is set or not.
*/
bool getFlag(int) const;

/** Changes the value of the given flag.
*
* @param An int indicating which of the flags will be set.
* @param A boolean indicating the new value of the flag.
*/
void setFlag(int, bool);

//! Marks the atom for removal.
void markForRemoval();

//! Unsets removal flag.
void unsetRemovalFlag();

public:

virtual ~Atom();

/** Returns the type of the atom.
*
* @return The type of the atom.
*/
inline Type getType() const { return _type; }

/** Returns the handle of the atom.
*
* @return The handle of the atom.
*/
inline Handle getHandle() {
return Handle(shared_from_this());
}

/** Returns the AttentionValue object of the atom.
*
* @return The const reference to the AttentionValue object
* of the atom.
*/
AttentionValuePtr getAttentionValue() const { return _attentionValue; }

//! Sets the AttentionValue object of the atom.
void setAttentionValue(AttentionValuePtr) throw (RuntimeException);

/** Returns the TruthValue object of the atom.
*
* @return The const referent to the TruthValue object of the atom.
*/
TruthValuePtr getTruthValue() const { return _truthValue; }

//! Sets the TruthValue object of the atom.
void setTruthValue(TruthValuePtr);
void setTruthValue(CompositeTruthValuePtr ctv) {
setTruthValue(std::static_pointer_cast<TruthValue>(ctv));
}

//! Return the incoming set of this atom.
IncomingSet getIncomingSet() const;

/** Returns a string representation of the node.
*
* @return A string representation of the node.
*/
virtual std::string toString(std::string indent = "") const = 0;
virtual std::string toShortString(std::string indent = "") const = 0;

/** Returns whether two atoms are equal.
*
* @return true if the atoms are equal, false otherwise.
*/
virtual bool operator==(const Atom&) const = 0;

/** Returns whether two atoms are different.
*
* @return true if the atoms are different, false otherwise.
*/
virtual bool operator!=(const Atom&) const = 0;
};

Whoa, C++, reputation of being verbose and fearsome is justified, i think. Now let’s break this down.
# TODO: EXPLAIN THE STRUCT
Let’s now check one of my favourite project redis, And a data structure/algorithm that fascinates me. The hyperloglog, HLL


struct hllhdr {
char magic[4]; /* "HYLL" */
uint8_t encoding; /* HLL_DENSE or HLL_SPARSE. */
uint8_t notused[3]; /* Reserved for future use, must be zero. */
uint8_t card[8]; /* Cached cardinality, little endian. */
uint8_t registers[]; /* Data bytes. */
};

Now this looks simple, and some of you might think it’s deceptively simple.(Don’t it’s straight forward simple). The real magic is actually in how these values are computed. There’s a reason HLL is called an algorithm and not considered a data structure.
#TODO: MORE ELABORATION

Share: Brisingr

“Do you understand, Eragon? You are so dangerous, we are forced to acknowledge the danger to your face and hope that you are one of the few people able to resist the lure of power.”

(Moon+ Reader Pro v2.6.5, Brisingr)

Geometric Mean

There are more than one type of average(or mean). The most famous Euclid’s three are :
1. Arithmetic Mean
2. Geometric Mean
3. Harmonic Mean
Arithmetic Mean is what most of us are taught is schools and most used. i.e: adding up values and dividing by the number of values.

What exactly is geometric mean. and where and why is it useful.

The definition of what it is rather simple.
If you want to find geometric mean of n numbers (positive integers), you multiply them all and take the nth root of the resulting product. Now, why would it be useful, and what’s the point of doing this. The positive integers is not really big difficulty in real life, (as in the worst case we can just shift/translate the origin for the axis with negative numbers)

Ok, Now imagine you have standard graph with the axes having very different limits. i.e: x axis varies from 0-0.5 while y axis varies from 0-100.
Now suppose you want to compare two(or more) objects/distribution both of which have measures along x and y. You can plot points in different colours(for diff objects) on the x and y, and then try to make a decision, based on what you want to pick.

That sounds fine till you think there are very few(say 5-10) different objects to be compared. What if you have say (100 laptops and 10 features) you want to compare them across?.
Ah now we’re in real trouble. How do we know which ones are which among the 100 colours, on top of that you have 5 graphs(for 10 features).

What we need is a way to combine these axes into one axis. Then we can go back to simple bar charts.

Here comes geometric mean to the rescue. If you look at the definition it multiplies the feature values which gives us a area(if 2 features), volume (if 3) or a n-dimensional volume value.
We can’t simply use this because, at the moment this value is biased towards features that have a higher range of values.
i.e: in the previous example y axis which ranged from 0-100 will simply wash out any differences in x.

So we take the (2 or 3 or n)th root of this value. In effect we have found normalized the axis range itself.

Note: the cool part here is we don’t need to know anything about the actual range itself. The nature of the operations on the valiues (i.e: product and nth root) itself ensures the final geometric mean value is equalized.

For an example I’ll pick laptop CPU Speed, Hard disk size, and RAM here’s a link..
If you look at it closely, while in the examples i have picked, while all the three pythagorean means don’t change ordinality/ranking of the laptop being compared, the Arithmetic mean gets dominated/boosted simply by raising Hard Disk space.
On the other hand the geometric mean, doesn’t get raised (as much simply) by raising the attribute with higher values.

It’s not really surprising, since the geometric mean is a exponential function and arithmetic mean is a linear function.

You can ignore the Harmonic mean for now, as it’s not at all clear what’s common among the laptops. I’ll later make another post/update detailing how harmonic mean can be used for this case.

One case where it is used is in finding F-Score for comparing predictive algorithms, statistical tests etc.

Share: Brisingr

You will have to do better than that, Rider, if you want to change my mind.”

“I don’t want to change your mind,” said Eragon. “I only want to make sure you have given due consideration to the implications of your decision and that you are not being overly hasty.”

(Moon+ Reader Pro v2.6.5, Brisingr)