Miscellaneous

Here I include a few random scripts and LaTeX packages I've written. They have saved me time in several opportunities, perhaps they will be useful to you as well.

Binary Search Script

I wrote a bash script that performs a binary search. I needed a script like this to automate my debugging process. The scripts shows progress using a bar in the terminal that is updated in place as the script runs.

Example/snapshots: find_lowest should return 20035, but using binary search from 0 to 100000 to find this value.

This is how it looks when the script has determined that the value is between 12499 and 24999, and it is testing whether the solution is higher or lower than 18749:

This is how it looks when the script finishes:

The script source code includes some documentation and the above example to illustrate how it can be used. Basically all you need to do is to convert your problem into a monotonic function that takes values between 0 and N and returns either 0 or 1. Because your function is monotonic, there is some value of i between 0 and N such that, your function returns 0 for values between 0..i-1, and 1 for values between i..N. The script will find the value of i automatically using binary search.

I'd be happy to provide more complex uses of this script, if you are interested. For example, I've use it to determine the minimum amount of memory necessary to run a program in Java. I've also use this for debugging a compiler: finding from a list of instructions added by a compiler, which is the first function to cause a problem in the compiled program.

LaTeX packages

Please contact me if you have any suggestions to improve these packages.

symbols.sty: Write "==>" instead of \Rightarrow

I wrote this package that allows you to write symbols using a format close to an ASCII format. For example, you could write

 `A x . x ">=" 0 "<=>" - x "<=" 0  

Instead of

 \forall  x . x \geq 0 \Leftrightarrow - x \leq 0.

See more examples in the documentation. Try it out!

Tip: Change the syntax highlighting in your editor to make the quotes " lighter and make the symbol's text stronger. Here is how to do it in VIM.

For those interested in the package internals:

The current version is based on the TeX commands \@namedef and \@nameuse. The previous version was implemented using an association list. Implementing a list with TeX macros was quite interesting. You can take a look at the old version here. The new version is a bit more robust.

indcode.sty: simple code environment with line number references.

This package contains a simple environment to manually indent code, put line numbers in the code, and add references to line numbers using the standard \label and \ref commands.