Tag: Algorithm
-
A puzzle from Donald Knuth
Recently I had to write some code to generate a pseudorandom number in a system with very limited sources of entropy. So, of course I turned to Donald Knuth and, in particular, Volume 2 – Seminumerical Algorithms – in the magisterial The Art of Computer Programming. Reading through the questions/exercises I then came across this…
-
The Reingold-Tilford algorithm revisited
A while ago, as part of early research into what became my MSc project, I wrote code to create and then draw red-black trees using C++. To draw the trees I used the venerable Reingold-Tilford algorithm, which is more or less the standard approach. I wrote some blogs about it and pages here seem to…
-
Even if P=NP we might see no benefit
Inspired by an article in the New Scientist I am returning to a favourite subject – whether P = NP and what the implications would be in the (unlikely) case that this were so. Here’s a crude but quick explanation of P and NP: P problems are those that can be solve in a known…
-
Convolutional coding
Convolutional coding is form of error-correction widely used in mobile communications and is another area of life where discrete mathematics is hard at work for us, even though we are unlikely ever to think about it. The basic idea in convolutional coding are that a stream of bits of length is converted to a different…
-
Have we reached “peak silicon” and what can we do about it?
Moore’s Law states that the number of transistors that can be squeezed into a given slice of silicon doubles every two years (or 18 months) – something I wrote about recently and where I declared “More transistors means greater speed, more and cheaper memory and so on … ” Except, maybe not. As the graph…
-
Better algorithms, not better hardware are what make your computer faster, faster
Many people have heard of Moore’s Law – which states that the number of transistors that can be packed into a piece of silicon doubles every two years (or 18 months in another formulation). More transistors means greater speed, more and cheaper memory and so on … so in the thirty two years since I…
-
“Let’s enhance that” might work after all
This video has amused and fascinated many because it displays a fundamental ignorance of a basic rule of the – universe – a consequence of the second law of thermodynamics – that one cannot extract more information out of a picture than went into it at the time of creation: But, according to the “Communications…
-
A further thought on MD5
The main use of MD5 – at least if my computer is any guide – is to check that a file you have downloaded from the internet or elsewhere is what it says it is. In fact in this general use MD5 is not being used to encrypt anything – instead it produces a “message…
-
More proof that algorithms matter
In my piece on Programming Pearls a few days ago, I said I had been inspired to try a different, and hopefully faster, algorithm to manage a linked list. Well, I did, and then I improved on it a second time by not deleting the array between scans of the memory map of a program…
cartesian product ... stuff about computing mostly 