Gaussian elimination step by step

It’s easy to make small stupid mistakes when you do matrix calculations manually. I put together a simple tool in javascript that performs Gaussian elimination step by step.

gauss.elim

http://g.bonds.nu/gauss/

Enjoy 🙂

Annonser

Use Game of Life to Generate 256 bit Hash

game.of.life.256.bit.hash

One of the most fascinating aspects of Game of Life is that it illustrates so well how a completely deterministic process can be so unpredictable. Use a fixed starting pattern and run. Watch the result. Use the same starting pattern but change a single cell somewhere. The new result can be as different from the old as night and day.

Absolute determinism plus unpredictability are precisely the two things you look for in a hash algorithm. When you store passwords on a server you don’t store the passwords themselves but their hashes, calculated using some hash algorithm like for example MD5, SHA-256 or Whirlpool.

A user authenticating himself on the server inputs his password and the server hashes the password to see if the hash corresponds to the hash stored on the server.

For a hacker getting hold of the stored hashes, or for the system administrator, there is no way to run the hash algorithms backwards to retrieve the real passwords. The only way to break a hash is to systematically hash every possible password (out of zillions) and see if the hash matches.

I made this Javascript application to illustrate the idea of using Game of Life to generate hash values. The application is not using Conways standard B3/S23-rules but instead B23/S23-rules.

Try to hash different words or sentences differing only by a single letter adjacent in the alphabet and watch how the hash value changes. You can also try to hash some text but before you click on the ”Run 200 steps” click somewhere on the gird with the mouse pointer to change a single bit.

Game of Life with B345/S45 rules

A lot of people are familiar with British mathematician John Horton Conway’s ”Game of Life” – an algorithm to simulate cellular growth and decay, first published in Scientific American in 1970.

The concept is simple. Imagine an infinite grid of empty squares. Each of these squares can either be empty or occupied by a ”cell”. The are only two rules. One rule for empty squares (the birth rule) and one rule for squares occupied by a cell (the survival rule).

Birth: If an empty square has exactly three neighboring cells a new cell is born in that square.
Survival: An existing cell will only survive if it has either two or three neighbors.

These two rules implies a time axis along which the grid will project forward in discrete phases.

But why do we have these specific rules? Why is exactly three neighbors required to give birth to a new cell?

Conway’s classical rules are sometimes abbreviated to the code B3/S23.

The reason for these particular rules to have become so popular isn’t that strange. Anyone who has experimented with a simulation engine using these rules knows that they often create very complex and interesting situations.

But this being a fact doesn’t exclude the possibility of other rules also having the potential of creating complex and interesting scenarios.

Conway himself and others have explored a lot of other possible rules for Birth and Survival.

I played around two days ago with my own javascript-powered game of life engine where I can chose any set of rules for birth and survival. I wanted to explore an idea I had to use the game of life cellular automaton concept to create a cryptographic hashing algorithm. So, by a mere coincidence, I tried the B345/S45 rules and was fascinated by the way that an initial small colony of cells transformed during hundreds of phases only to later die out. This was almost always the fate that awaited small colonies occupying an initial eight times eight square. I tried out new random shaped colonies, one after another and very seldom a shape would pop up that wouldn’t die out but instead grow and grow and never stop growing. How come, I wondered?

I dealt with this question systematically and found out that there are only 36 symmetrical shapes out of a total of 37888 that will grow indefinitely. All the other symmetrical 8×8-shapes will eventually be either totally annihilated or get stuck in small for ever repeating loops of shapes (so called pulsars).

Here is the total set of miracle seeds – the smallest possible symmetrical shapes that I found that will grow forever. All the tens of thousands of others are destined to perish or stagnate.

smallest.possible.symmetrical

I have shown that there exist no smaller symmetrical shapes, for example 7×7-shapes or 6×6-shapes, that will grow indefinitely.

Add or remove a single pixel anywhere and they will die – that’s how sensitive they are (try it out for yourself).

So these are the symmetrical ones. What about the asymmetrical ones?

I don’t know, but I guess that you can’t find an asymmetrical shape smaller that 8×8 that will grow indefinitely.

It could be tested systematically but the number of all shapes that occupy a maximum space of 8 times 8 squares are much larger than just the symmetrical ones.

Click on this link or on the picture above to go to my B345/S45 simulation engine.

Update: July 28 2015

Amazing news. After seventeen hours of automatic testing of random shaped populations eight different asymmetric 8×7 indefinite growers presented themselves!

8x7 grower 8x7 grower 2 8x7 grower 3 8x7 grower 4 8x7 grower 5 8x7 grower 6 8x7 grower 7 8x7 grower 8

I  also found three shapes that lasted a long time but in the end didn’t quite make it.

8x7 lasted 539 8x7 lasted 542 8x7 lasted 716

They lasted 539, 542 and 716 (!) rounds respectively.

If you choose an answer to this question at random

If you choose an answer to this question at random, what is the chance you will be correct?

A) 25%
B) 50%
C) 60%
D) 25%


Answer:

The answer depends on how you distribute the probabilities when you do the random choice.

If you make the random choice by throwing a cubic die like the one you can construct from the sketch below the answer is 50%

guggebonds.wordpress.die

If you want to restrict the scenario so that you’re only allowed to use a randomization method where the results A to D are equiprobable, then the answer is 0% because none of the four answers can be correct.

If you make the random choice by throwing an octahedron shaped die like the one you can construct from the sketch below the answer is 25%

guggebonds.wordpress.die.2

Counting the days after Christmas

Does the Twelfth Night fall on January 5 or 6? And why is it called the Thirteenth Night (Trettondagsafton) in Sweden? The traditional answer is that it falls on the 5th and here is why?

counting.christmas.days

Here you can see why the Twelfth Day is not among the so called Twelve Days of Christmas.

Having spent some time during the holidays discussing this on Facebook I felt the need to clarify this.

The discrepancy between the English and Swedish way of naming the days after Christmas can easily lead to so called fence post errors, a common issue in computer programming.

Hur rasistisk är du?

rasism.flowchart.2

Äntligen en enkel matematisk formel för rasism…

Med den analytiska filsosofin och matematiken i min akademiska bana stör jag mig något fantastiskt på ord som används i media utan klar definition. Ord som rasism och rasist är sådana ord.

Journalister och debattörer i massmedia benämner gärna företeelser eller åsikter som rasistiska men väldigt få tycks ha något intresse av att reda ut vad ordet betyder.

Självklart har jag förståelse för att ord som används vardagligt inte måste ha definitioner lika exakta som inom matematiken. Ords betydelse ändras och utvecklas dessutom över tid. Det är naivt att tro att ord har sina betydelser huggna i sten för all evighet.

När det gäller begreppet rasism så framstår en sån här betydelseutveckling eller betydelseglidning som extra påtaglig. Studerar man hur ordet används idag i tidningsartiklar och i sociala nätverk så blir det ganska uppenbart att vi fjärmat oss från ordets traditionella betydelse. Rasism handlar inte längre om idén om olika rasers över- eller underlägsenhet. Rasism idag handlar istället nästan alltid om moralisk egoism.

En sån typiskt egoistisk ståndpunkt jag såg för några veckor sedan i ett socialt forum var denna:

Vi vill inte att invandrare ska komma hit och åderlåta våra socialförsäkringssystem

Att denna åsikt betecknas som rasistisk i media är inte ovanligt men den har ju knappast något med den traditionella betydelsen av rasism att göra. Självklart inser jag att många säkert vill bevara ordets äldre betydelse men samtidigt anser jag att man måste komma ihåg att vårt språk är dynamiskt.  Jag är nog inte ensam om att hävda att begreppet rasism har fått en ny och ganska väl etablerad betydelse. Rasism handlar allt oftare helt enkelt om ovilja att dela med sig till andra grupper av människor.

Att vi faktiskt noterar och erkänner att begreppet rasism fått denna nya betydelse av egoism ger flera positiva konsekvenser.

För det första så kan en samhällsdebatt aldrig förlora på att de begrepp som används kommer mer i linje med allmänt språkbruk. Många (jag skulle vilja hävda, de flesta) av de tillskrivningar av rasism som förekommer i massmedia idag skulle vara helt obegripliga om man tolkade rasism uteslutande i den äldre bemärkelsen.

Människor som t.ex. påstår att de inte vill ha hit invandrare för att de tror att det får negativa ekonomiska konsekvenser för skolor, vård och äldreomsorg uttrycker en åsikt som många journalister antagligen skulle kalla för rasistisk. Den tillskrivningen bygger ju på idén om rasism som egoism. Det har knappast med rasism som tron på en övermänniskoras att göra.

Något jag som matematiker uppskattar är möjligheten att kvantifiera begrepp för att på det viset göra dem tydligare och mer exakta.

Om rasism primärt har att göra med egoism, eller mer specifikt med en ovilja att dela med sig av resurser till människor från andra länder, då finns det en möjlighet att kvantifiera rasismen. Egoism går att jämföra mellan individer. Det går att sätta siffror på.

Följande konkreta formel är inspirerad av diskussioner jag haft med mina egna filosofistudenter. Den beräknar graden av rasism hos en person uttryckt som en procentsats.

rasism.formula.2

Där

I = Inkomst (månadslön brutto)
B = Antal barn du på egen hand försörjer
H = Antal kronor varje månad som du lägger på att hjälpa främmande människor som bor i eller kommer ifrån andra länder via t.ex. Rädda barnen, Amnesty, Läkare utan gränser, Fadderbarn, SOS barnbyar m.m.

Kalkylen bygger på att en person som precis ligger på marginalen till att vara medelinkomsttagare (årslön 229 000 kr enligt SCB ) bör kunna försörja sig själv och ett barn (kostnad för en nioåring 2500 kr/mån enligt SCB).

Tjänar en person däremot mer än denna årsinkomst och/eller saknar barn så har den personen mer ekonomiska resurser än vad som kan anses vara ett minimum för att täcka det grundläggande vad gäller mat och boendekostnader.

Rent moraliskt är det knappast försvarbart att spendera detta överskott på sig själv snarare än på människor som lever i djup misär.

Jag är väldigt nöjd över att här få presentera ett förslag på hur begreppet rasist ska kunna få en exakt kvantitativ definition som ligger helt i linje med hur det används i media. Det som jag dock är mindre nöjd med är att jag genomförde uträkningen för egen del och insåg att resultatet inte var särskilt smickrande.

Om någon hädanefter frågar mig om jag är rasist så kommer jag sanningsenligt svara:

Ja, tyvärr… 99,7% rasist.

Nu måste jag gå och trycka om mina visitkort…

The probability of finding a string of n characters

I tried to google this today but I only found a lot of unnecessarily complicated stuff. I wanted something simple but mathematically exact so I had to figure out this myself.

 // p(n,m,b) - the probability of finding at least one occurence of a string of n characters (or digits/symbols)
 // (not starting and ending with the same character) in a larger random string of m characters
 // b - is the number of different types of characters
 double p(int n, int m, int b) { return f(n,m,b) / Math.Pow(b,m); }
 double f(int n, int m, int b) { return m<n ? 0 : b * f(n,m-1,b) + Math.Pow(b,m-n) - f(n,m-n,b); }

Compare this with the standard function for calculating an approximate probability…

double pa(int n, int m, int b) { return 1 - Math.Pow((Math.Pow(b,n)-1) / Math.Pow(b,n), m-n+1); }

The f-function above calculates the total number of possible ways that the the sought for string can appear in the larger random string. Although it’s pretty short it’s not particularly fast. I made a much faster algorithm based on this idea…

formula

For example: Let’s say you want to calculate the probability of finding a particular 5 digit number in a random sequence of 18 digits. We first use the f-function to calculate the number of possible ways it can occur:

formula.sample

The the probability is given by:

ratio

Here’s my faster algorithm

double f(int n, int m, int b)
{
    int nn = n; int sg = 1; int p = 0;
    int q = 0; int a = 1; double sum = 0;
    do {
        q = m-nn;
        p = q+a;
        sum += sg * Combin(p,q) * Math.Pow(b,q);
        sg = -sg;
        a++;
        nn += n;
    } while (m-nn >= 0);
    return sum;
}

”Combin(p,q)” is of course the combination-function – ”p over q”.