Selection, Revisited.

February 2, 2016

When we think of searching, we generally think of searching a value in a sorted collection of some sort. For a simple array, this implies the array is sorted and that we use binary search or a variant. But what if we want to search by rank? In a sorted array, that’s not very hard: the kth item is in slot k. But what if the array is not sorted?

Read the rest of this entry »


LaTeXify C/C++ code snippets

January 26, 2016

So I’m still writing lecture notes. This time, I need to include kind of larger pieces of C or C++ code, and \LaTeX environments do not really help me a lot. Some are better than others, but you still have to escape and fancify text yourself. This is laborious and error-prone, and is an obvious target for automation. A script of some sort. The task isn’t overly complicated: highlight keywords, and escape symbols like { } _ and & that make \LaTeX unhappy. This looks like a job for
sed.

Read the rest of this entry »


The Cutest Littlest Forkbomb

February 24, 2015

In one of his last tweets @levans posted the cutest Rust-lang fork bomb:

fn main(){std::thread::spawn(main);main()}

at 42 characters longs, which he sees like a sign. Excluding headers, you can do even shorter in C++:

main(){boost::thread x(main);main();}

It’s not really a terrifying forkbomb (as Linux, for e.g., kills everything after a while because processes run out of memory), and we could have done much worse with a process-level (rather than a thread-level) forkbomb:

main() { fork(); main(); }

This variant creates separate processes… none of which individualy can exhaust its memory! Don’t try this one on your main box (but it could be fun in a virtual machine).

bobomb


Stirling’s series

December 2, 2014

Last week, we had a look at how g++ handles tail-recursion. Turns out it does a great job. One of the example used for testing the compiler was the factorial function, n!.

fibolapin-bw

We haven’t pointed it out, but the factorial function in last week’s example computed the factorial modulo the machine-size (unsigned) integer. But what if we want to have the best possible estimation?

Read the rest of this entry »


Of tails.

November 25, 2014

In a previous post, I explored the effect of pruning on a recursive function, namely, the Collatz function. Richard (see comment) asked “does your compiler know about tail recursion?”. Well, I didn’t know for sure. Let’s find out.

tail-recursion-small

Read the rest of this entry »


Perfect Hashing (part I)

September 9, 2014

A few days ago, a friend asked me how to write, if even possible, a hash function that had no collisions. Of course, it’s relatively easy to get a reasonably good hash function that will give the expected amount of collisions (especially when used as usual, modulo the size of the table). But what if we do not want collisions at all? What can we do?

7e4156dfac4d82e9a5cab4987ecc3a15

There are some hash functions, known as perfect hash function, that will yield a different hash for every key from a a priori known set of keys, say K. Are they hard to build? Fortunately, not really. Can we exploit the uniqueness of the hashed value to speed look-ups up? Yes, but it’s a bit more complicated.

Read the rest of this entry »


Yet Another Square Root Algorithm (part II)

May 6, 2014

last week, we saw that we could use a (supposed) efficient machine-specific instruction to derive good bounds (but not very tight) to help binary search-based and Newton-based square root extraction algorithms go faster. Last week, we saw that the technique did lead to fewer iterations in both algorithms.

malevich-square

Now, does the reduced number of iterations translate into actual, machine speed-up?

Read the rest of this entry »


Follow

Get every new post delivered to your Inbox.

Join 98 other followers