Pages

Sunday, December 21, 2014

First android app I worked on!

Together with a bro, Zach Lauzon, I made a cool app for Android devices called Flash Beat. It uses the strobe on your phone to produce light that goes well along the music. You can use it at a party, make a small disco at home, or impress your friends with beatbox skills like this. Also, you can make it flash on your friends' faces (you asshole).

Without further ado, the app:
                                                                                       Get it on Google Play

Preview on a song:

Internship at Google

Internship at Google is finished!

Just 2 days ago I finished my first internship. Even though there were bumps on the road throughout it, I had fun participating in it. I met lots of friends, visited many places, got to eat a lot ( :) ), and also had a cool project.
The project I was working on was about making a regression test for a service handling social relationships between users and documents. I made sure that builds do not break certain relationships that should always exist.
My project was also dependent on other people there, which made me also more efficient at working with a team.


Sunday, June 8, 2014

Illustrating the size of the universe in terms of memory space

Accidentally, I came over my friend's question "Are we alone in the universe?".
I started thinking. I knew the universe is big and I've read several times that the human mind can't even comprehend the size of it. As always, I thought that the solution lies in simplifying the problem and making things more abstract.

Being a computer scientist, I went for representing it in terms of data :)
Most estimations of the data volume we produced lie below 5 Zettabytes. So, let's assume that we have a hard drive of that size.

Furthermore, assuming every galaxy is of the same size as the Milky Way, we have approximately:
5.1 x 10^22 stars = 510 0000 0000 0000 0000 0000 stars
170 billion galaxies x 300 billion stars
= (number of galaxies in our universe) x (number of stars in our galaxy)

Summed up, we have:
5 Zettabyte = 5×10^21 bytes = 4 x 10^22 bits on our hard drive and 5.1 x 10^22 stars

Imagine we want to make a picture with tiny dots on it, separated by a white space of 1 bit, making each dot represent a star. With all the memory on Earth we couldn't store that image!

Something funny to think about too: every word ever spoken can be stored in 0.001 Zettabytes. If all we did our whole life was naming stars, we would still have to name 1000 times as much as we did.

With all that said, I believe that there is other intelligent life somewhere out there.

References:
http://en.wikipedia.org/wiki/Exabyte
http://en.wikipedia.org/wiki/Zettabyte
http://www.universetoday.com/102630/how-many-stars-are-there-in-the-universe/

Sunday, March 23, 2014

Leaving my room in Tennesseeallee, Karlsruhe

In 2 days I'll be leaving the room I used to live in for the last 2+ years. Many challenges have been won from this room out, but it's time to move on to the next chapter: bachelor's thesis at the CMU, Pittsburgh. Lastly, for the memories, an image of my workplace in this room:



 So long!

Saturday, March 15, 2014

A small journey with XNA and C#

There is something I've done a year ago, but never shared. Although it looks simple, it can produce some beautiful views. Here a preview:

To try it out: setup.zip (source code: source.zip).

As for the commands:
- C: creates one particle (holding down for more possible)
- A: makes a new spawn point for the particles
- D:  creates a "pull gravity" at the cursor's position
- P: creates a "push gravity" at the cursor's position
- V: creates a pull-point over the given location
- B: creates a push-point over the given location
- 1: increases gravity pull range
- shift+1: decreases gravity pull range
- 2: increases gravity push range
- shift+2: decreases gravity push range
- +: make the dots larger
- -: make them smaller
- ESC: toggles the command prompt (up-arrow may be used for history access). Following commands are possible:
                                                            - "SET COLOR x y z" where xxx,yyy,zzz are in [000,255] (leading zeroes are needed for 3 digits!)
                                                            - "ADD x" adds x new dots at random positions
                                                            - "REM x" removes x random dots
                                                            - "CLEAR" clears the everything
                                                            - "SAVE" saves the state and "LOAD" loads it

Have fun!

Song extractor for the Osu! game

I've used to play a bit a game called Osu!. It's about catching the beats alongside a song. Here a preview of the best player in the world (combo is given in the bottom-left corner):


.... watching this is always like "WTF, HOW?!".

To the reason I'm posting this. I've met some quite exciting songs while I've played the game and I wrote a program for extracting the songs out from the game. This is easy done by hand too, but it's quite tiresome.

Here it is: osu_extractor_win7.zip (readme from the zip).

Thursday, February 27, 2014

Primitive Roots modulo a prime number

Finding primitive roots

First off, it has to be noted that the constraint that the modulo value is a prime number is just for simplicity (hint: all values from 1 to p-1 are coprime to p for a prime number p).
Now, what EVEN is a primitive root modulo p you may ask. This is just a number g which generates all numbers from 1 to p-1 with \(g^{t} \: mod \: p\). That is, for every positive integer x < p there exists a t, so that \(g^{t} \equiv x \pmod{p}\).
Properties of primitive roots:
  • for a given p there are phi (phi(p))=phi(p-1) primitive roots
  • g is a primitive root \( \Leftrightarrow\) for every divisor d of \((p-1)=phi(p)\), \(g^{d} \not\equiv 1\pmod{p}\) holds \( \Leftrightarrow\) for every prime \(x\) from the prime factorization of \(p-1\), \(g^{(p-1)/x} \not\equiv 1\pmod{p}\) holds.
  • (comment: this is essentially there to check for repeating sequences in \(g^{t}\) for \(t \in {1,..,p-1} \pmod{p}\).
Some research: I've ran this code to look at the distribution of the primitive roots for primes between 100 and 1,000,000,000. By running the code we see this from the output:
  • the lower bound for the number of primitive roots is \(0.15 \cdot p\). Therefore, 15% of the numbers smaller than \(p\) are primitive roots for a given p (in worst case!). By selecting a random positive integer < p we have a 15% chance of selecting a primitive root!
  • given a random p, the chance of hitting a primitive root on random is even ~40%.

Therefore, in order to find a primitive root, we may simply pick up random numbers and check the above property which has to hold for primitive roots. Code which does that: link.

Now to the discrete logarithm (the index):

for a given x, how to find a \(y=ind_{g}(x)\) with \(g^{y} \equiv x \pmod{p}\). The answer is: you can't. Many encryption algorithms are based on this fact. Though, they have some nice properties as normal logarithms:
  • \(ind_{g}(ab) \equiv ind_{g}(a) + ind_{g}(b)\pmod{p-1} \)
  • \(ind_{g}(a^{k}) \equiv k \cdot ind_{g}(a)\pmod{p-1} \)
That should bundle the core things about this topic. One is advised to check the references for a better understanding.

Useful links:
- Wiki - Wiki(discrete logratihm) - Finding primitive roots - Index properties

Sunday, February 23, 2014

Linear diophantine equations: simplification of sums for reachability (enabled javascipt for latex is needed)

My first meaningful post shall be a mathy one. I wanted to understand the idea behind this, so I've decided to make a post explaining it :)
Assume we have a problem where we have to iterate over all \(x = \sum\limits_{i=1}^n c_{i} \cdot a_{i} \), where the \(c_{i}\) are freely selectable. In such problems a very easy simplification can be made: each such \(x\) can be represented in the form \(x = t \cdot q\), where \(t = gcd(a_{1},...,a_{n})\) and \(q \in \mathbb Z \).

To understand the above statement, we only need to think of the extended euclidean algorithm. Inside of it we find the integers \(x\) and \(y\) so that \(x \cdot a_{1} + y \cdot a_{2} = gcd(a_{1},a_{2}) \) holds. Additionally, we can easily imply that each number \(v\) written in the form \(v = c_{1} \cdot a_{1} + c_{2} \cdot a_{2} \) must be a multiple of \(g:=gcd(a_{1},a_{2})\) (as g divides \(a_{1}\)and \(a_{2}\) it must divide v for the equation to hold (!)).
We show now that the same holds for 3 variables. Let \(x = a_{1} \cdot c_{1} + a_{2} \cdot c_{2} + a_{3} \cdot c_{3} \) and \(g:=gcd(a_{1},a_{2},a_{3})\). We have to prove that \(x\) is a multiple of \(g\). Consider the first two variables and write: \(a_{1} \cdot c_{1} + a_{2} \cdot c_{2} = t_{1} \cdot gcd(a_{1},a_{2})\). This gives us \(x = a_{1} \cdot c_{1} + a_{2} \cdot c_{2} + a_{3} \cdot c_{3} = t_{1} \cdot gcd(a_{1},a_{2}) + a_{3} \cdot c_{3} \). Simply seen here: there are again two fixed numbers and two free! Smells like the extended euclidean again :)
We write: \(G := gcd( gcd(a_{1},a_{2}) , a_{3} ) = gcd(a_{1},a_{2},a_{3}) = g \) and get: \(x = t_{1} \cdot gcd(a_{1},a_{2}) + a_{3} \cdot c_{3} = t_{2} \cdot g \) - with this we're done! Inductively the statement follows for 4 and more variables.