Counting large numbers of events in small registers

“What does the logarithm do?”, asked a Professor a bunch of us back in 1990. “It is the inverse of $e^{x}$ “, I said. “No” he replied, “I ask again, what does the logartihm do?”. A friend started to say something along the lines of the Wikipedia definition. “You tell me how it is calculated, but not what it stands for; why do we need it?”. He then proceeded asking us the value of the logarithm of some numbers:

x	$log_{10}(x)$
1	0
10	1
100	2
1000	3
10000	4

– Do you see a pattern now?

“The length of the number is $\lfloor log_{10}(x) \rfloor +1$ “, one of us observed.

– Exactly!

I was reminded of this discussion when stumbling on “Counting large numbers of events in small registers“ written by Robert Morris (father of the Robert T. Morris). Basically, what Morris observes in this paper is that with n bits available, one can count up to $2^{n}-1$ . He had 8 bit registers available only, so this limited counting up to 255 which did not suite the application he had at hand. So he began by simply having the value of a register representing $v(n) = log_{2}(1+n)$ and reached to a generalized result of $v(n) = \frac{log(1+\frac{n}{a})}{log(1+\frac{1}{a})}$ where a controls both the maximum count that can be held in the register and the expected error.

The maximum number is $n_{v} = a((1+\frac{1}{a})^{v}-1)$ . The expected error of n after n counts can be calculated from the formula $\sigma^{2} = \frac{n(n-1)}{2a}$ .

This is a really nice hack if you need to count large numbers of events and where accuracy is not a must. It maybe helpful to people working with embedded systems or otherwise deprived environments.

(Triggered-By:)

from zero to hero (and back again)

G.A.P. (↑) and K.A.K. (↓)

It only took them two year.

2-0

Το πρωί στη δουλειά:

– Έλα ρε! Αυτοί δεν έχουν τέρμα.
– Εμείς έχουμε μόνο τέρμα.

(ref)

“But how do I find out?”

“But how do I find out what I search for?”, a friend asked the other day, “Google cannot help me find information that I need”. This friend is in the process of completing a thesis on social networks.

Google, Yahoo! Search, Bing and the rest are tools that help us search information already available. Unfortunately they are not mind readers, plus vast though it may be, indexed information on the web is not all available information. Years ago, when put in the same situation, my post started with “I have a silly question” and got back two answers, the answer to my question and that “Silly questions are the ones never asked; there are no silly questions”. So whenever in trouble, when your favorite search engine (or your ability to ask it) seems limited, ask the ultimate search engine:

People

The best answers I have ever got for questions that troubled me were from humans, be it in person, telephone, the USENET or even mailing lists. My advice to her was to locate and subscribe to a mailing list relevant to her subject (in her case SOCNET) and ask people there. Impressive things happen when you ask people instead of machines. Ideas spring and flourish and (human) networks form. Just do not ask anyone to do your homework for you.

Δεν είμαστε υπηρέτες

Από μια λίστα staff που διαβάζω:

“Το καλώδιο δικτύου μου τα είχε παίξει και επειδή δεν βρήκα κανένα άλλο πρόχειρο (έψαξα και στη ντουλάπα σου) πήρα του Σ*****. Χρειάζομαι όμως ένα πιο μακρύ. Οπότε μπορέσεις σε παρακαλώ φτιάξε μου ένα.”

Για όποιον βιάζεται και μπαίνει στον κόπο (α) να ψάξει στη ντουλάπα κάποιου άλλου και (β) να πάρει το καλώδιο του διπλανού του, το Πλαίσιο για παράδειγμα έχει τα 15m UTP cat 5 στα €5,77 και τα 10m στα €3,99.

Εάν πάλι το συγκεκριμένο μήκος δεν βολεύει και υπάρχει κουλούρα διαθέσιμη, υπάρχουν και οδηγίες.

Δεν είμαστε σκλάβοι.

Studies in the Economics of Transportation

While reading Nagurney‘s “Comment on Catching the Network Science Bug“, I was fascinated that “Studies in the Economics of Transportation”, which was written in 1956 was mentioned. After all, Network Science is supposed to be “newer” than that.

For anyone interested the book is available from the RAND classics section. A more readable PDF is located here.

I will not claim that I have given the book anything more than a brief look. However I read “A Retrospective on Beckmann, McGuire and Winsten’s Studies in the Economics of Transportation“.

This was not the first time that I saw this book being cited: It is also cited in Preface to “On a Paradox of Traffic Planning” (a preface to the English translation of Braess‘s “On a Paradox of Traffic Planning“ which introduces Braess’s Paradox).

Sometimes the titles stick to your head, I guess.

10

Από το εξώφυλλο του Πρωταθλητή:

Έτσι όπως είναι προπονημένη η ομάδα, ο Zico άνετα φοράει στολή και παίζει. Να δούμε και καμιά “μπανάνα”.

– Μόνο για την ομάδα μας γυρίζει στο ποδόσφαιρο ο Πελέ!

Εμείς έχουμε μέλος τον Πελέ και προπονητή τον Λευκό Πελέ. Για να δούμε.

Με την ευκαιρία, αλίευμα από το twitter, χάρη στον @Jimbo77:

OneWebDay

For this year’s OneWebDay, I simply quote from “Doctor for Two Decades“:

“I’ve seen the Internet go from E-mail to Twitter. I’ve seen fax machines and CDs go from amazing technologies to has beens. And computers got much faster and smaller. I no longer have time for a restroom break when I LaTeX a paper.”

And like the author notes: “I got to watch it all in real time“

(previous) (next)