Random stuff on informatics, computer science, physics, etc.

## Category: Informatics

### Implementing mod function in C

Something some people don’t realize is that C and several other programming languages don’t offer you the standard modulo operation but simply a remainder operation (this issue has been in any case discussed countless times, e.g. see, although most of the times without offering a solution).

The problem arises when people try to use the remainder operator, % or $\text{rem}$, for the modulo without realizing the implications of doing so.
I recall when a programmer I knew tried to write C code for a steering angle sensor system using the % operator for the mod operation (which was needed by the algorithm), leading to erratic and difficult to debug results (in this case, a function that was supposed to be smooth exhibited erratic jumps), leaving me the job to understand the algorithm and then find the bug.
Note that the C standard defines the remainder of an integer division via the % operator for positive integers. For negative integers the operation is implementation dependent and only fixed by the C99 standard or newer. Note that the remainder can be negative but the modulo can’t, and that $\mod(a,b)$ is contained in $[0,b[$:

Modulo vs remainder operation for fixed divisor.

The question is then, if the remainder operation, % here also denoted as rem is available, how to leverage this to calculate the modulo operation? And here’s one way of doing it:

$\mod (a,b) = \begin{cases} 0, & a = 0 \vee b = 0\\ b - \text{rem}(-a -1, b) -1, &a<0 \\ \text{rem} (a,b), &a>0\end{cases}$.
Note that this is only valid for a non-negative divisor $b$, however the generalization is rather trivial and as is common practice to say, left as an exercise for the reader :).

### Video game collisions – pixel perfect

Collisions abound in video games. If not, how would you know whether you’ve hit a wall, your enemy, or if that bullet shot you or not? Here we will look at collisions in 2D games, which tend to use sprites (alternatively you can have 3D models projected onto a 2D plane, which is becoming increasingly common).

By virtue of how graphics are stored in computers, the full sprites are rectangular (and some pixels are either alpha pixels or have a special color defined to be transparent – alternatively one can use masks).

Let us then look at collision between rectangles.

Box collision

Consider a rectangle A defined by its vertices $\lbrace (x_{1}^{\text{A}}, y_{1}^{\text{A}}), (x_{1}^{\text{A}}, y_{2}^{\text{A}}), (x_{2}^{\text{A}}, y_{1}^{\text{A}}), (x_{2}^{\text{A}}, y_{2}^{\text{A}}) \rbrace$ and a second rectangle B, also defined by its vertices $\lbrace (x_{1}^{\text{B}}, y_{1}^{\text{B}}), (x_{1}^{\text{B}}, y_{2}^{\text{B}}), (x_{2}^{\text{B}}, y_{1}^{\text{B}}), (x_{2}^{\text{B}}, y_{2}^{\text{B}}) \rbrace$:

Box collision

It is a simple exercise to calculate the overlap in the x and y directions between the two rectangles to be given by:

$x_\text{overlap} = \max(0, \min(x_{2}^{\text{A}}, x_{2}^{\text{B}}) - \max(x_{1}^{\text{A}}, x_{1}^{\text{B}}) )$
$y_\text{overlap} = \max(0, \min(y_{2}^{\text{A}}, y_{2}^{\text{B}}) - \max(y_{1}^{\text{A}}, y_{1}^{\text{B}}) )$

where $\max(a,b)$, $\min(a,b)$ are the function that return the largest/smallest of the two values, $a$ or $b$.

Then for our purposes, there is a collision between the rectangles whenever both $x_\text{overlap} \geq 0$ and $y_\text{overlap} \geq 0$.

Pixel perfect

So what about pixel perfect collisions, i.e. when we detect exactly whether or not two sprites have collided?

boxes_objects

Sprites and bounding boxes – in this case the two objects do not intersect, although looking only at the bounding box they appear to intersect.

Well, here’s a possible algorithm:

• Detect collisions as in the box collision algorithm above
• If a collision is detected, extract coordinates of collision rectangle
• Iterate over pixels in the collision rectangle: look if there’s any pixel where the sprites have both a non-alpha pixel (or where both masks have the same value, if using masking)
• If any such pixel is found there’s a collision, if none is found, there’s no collision

At most we would have to iterate over the size of one sprite. Let’s estimate that as 300 x 300 = 90.000 pixel, which is still quite a lot, specially if we have to detect a lot of such collisions. But if we look only, for example, at every 10 pixels, in every direction, that would mean iterating at most through 900 pixels, which is 2 orders of magnitude better, considerably faster and nobody can detect that! Although not a pixel perfect collision, it’s much better than box collision and much faster than pixel perfect collisions.

### Configuring Unison

Unison is a file syncronization software, using the rsync algorithm.
Unlike rsync, Unison makes two-way file synchronization very simple.
Unison also allows you to syncronize files across different platforms and filesystems.
There are official Unison releases for several platforms, including Linux and Windows, although in my Windows machine I use Linux’s version through Cygwin.
You can actually also install a GUI for Unison (which probably come by default with some pre-compiled binaries, such as the Windows version).

It allows you to perform local syncronizations, for example between your main hard drive and an external hard drive, or with a remote host by using ssh.

If you want to sync two roots regularly, you should create a prefences file (.prf) file. Here’s an example of the file I use for mirroring my working directory in my SD card (FAT32) with my external hard drive (NTSF) in Windows (using Cygwin). In Linux this file should go in your .unison directory located in your home folder.

 # Unison preferences file

 # roots root=/cygdrive/f/Documents root=/cygdrive/g/DocumentsBackup # for mirroring force=/cygdrive/f/Documents # to sync fat32 perms=0 fastcheck=true 

# prevent unison from prompting the user batch=true 
Here I am mirroring my /cygdrive/f/Documents directory.
Note how I name the directories in the two roots in a different way. In this case, if by any chance the drive name changes, I am not mirroring things in the opposite direction! (an alternative is to completely disable mirroring)
Note that since I store my data in an SD card using the FAT32 filesystem which does not support the same set of permissions as NTFS or EXT , I set “perms=0” (otherwise Unison will complain about permissions).

And here’s the .prf file I use for synching my working directory with my server (via ssh):

 # Unison preferences file # roots root=/cygdrive/f/Documents root=ssh://alex@myserver/backupDirectory # for mirroring force=/cygdrive/f/Documents # to sync fat32 perms=0 fastcheck=true # prevent unison from prompting the user batch=true 

# to prevent the ssh connection from hanging sshargs = -o ServerAliveInterval=120 

One more thing that is wort mentioning, is that, even with ServerAliveInterval set to a large value, the synchronization may fail whenever there are many files or these a very large due to connection reset by peer.
In this case, what works for me is to synchronize smaller subsets of files before synchronizing the full roots.
This can be achieved via the path variable. Imagine you have a folder /cygdrive/f/Documents/foo/bar that you want to synchronize, using the roots above.
Then, by setting,

 path = foo/bar 
Unison will synchronize only that folder.

Please note that this aims to be a small introduction to Unison and not a comprehensive one. In case you need more information, you should always consult the user manual.

You can obviously schedule automatic synchronizations in Linux using crontab or identical tools in Windows, and using public key authentication but that is material for another post…

### Making PyQuante work with Libint

Pyquante is a very nice “open-source suite of programs for developing quantum chemistry methods” developed by Richard Muller. Although not as fast as comercial software, I can atest that the code is very simple to understand and to modify. And in case you need to implement your own Quantum Chemistry routines, PyQuante takes you off the burden of having to write everything from scratch.

Libint is a software stack for computing integrals found in Quantum Chemistry created by Edward Valeev. I certainly cannot say much about libint as I haven’t had enough time to fiddle around with it. What I can say is that Gabriele Lanaro wrote some bindings that allow PyQuante to use libint and that make the calculation of the integrals faster (I cannot give you exact figures, since I never did any rigorous runtime tests, but I can attest that for the situations I tested, it did indeed run faster – also the ground state energy was indeed the same).

My problem was that I did not find any instructions on how to make PyQuante work with libint.
So here are my own (they works for PyQuante 1.6.4 and libint-1.1.4)


./configure --enable-shared
make



If using Ubuntu (and possibly other Linux distros) you may get an error similar to:


/bin/sh ./libtool --mode=compile g++ -DHAVE_CONFIG_H -D_ISOC99_SOURCE=1
-I./include -I/data/development/libint-2.0.3-stable/./include -O2 -c src/HRRPart1bra0ket0gf.cc -o src/HRRPart1bra0ket0gf.lo
libtool: compile: you must specify a compilation command
libtool: compile: Try libtool --help --mode=compile' for more information.
make: *** [src/HRRPart1bra0ket0gf.lo] Error 1



This is due to the fact that in Ubuntu 6.10, the default system shell, /bin/sh, was changed to dash.
Changing the shell to bash by adding

SHELL = /bin/bash

to the Makefile should solve the problem.
Now download PyQuante 1.6.4 and copy the folder libint-1.1-4 to PyQuante’s folder and install PyQuante with libint support by running

sudo python install --enable-libint

.

Everything should be working now, and the integrations should now be now faster than before!

### Installing and properly configuring Cygwin

Cygwin is a Linux-like interface for Microsoft Windows. It’s very neat. In my case I have a Lenovo X230 tablet and it’s just less of a nuisance and more functional to use MS Windows. Also, even though Wine works very well, it’s still not perfect. That way I have Windows installed and simply use Cygwin to easily access to my Linux server and have that Linux feel in Windows.

Cygwin is very easy to install and can be downloaded from here. There is a 64-bit version, but at the moment it is lacking some useful packages like rxvt. During install you will be prompted to choose a mirror (most work well) and which packages to install. Be sure to install wget, because we will need it for customizing cygwin later.

Now, if you need to install some packages on Cygwin, the usual procedure is to re-run the setup executable. This is not very convenient. Fortunately there’s a better way. Stephen Jungels has written a command line installer for Cygwin which works just like apt-get. You should visit apt-cyg webpage here and install it.

Now, in Cygwin to access VI Improved, which comes selected for install by default, you should type vi and not vim (as you may be used to) .

The problem is that if you try to run vim, it enters in compatibility mode, and some stuff simply won’t work. You may notice that you cannot see in the bottom in which mode you are, backspace won’t probably work, etc… This is because it is lacking a .virc file in your home folder.
Simply creating an empty .virc file using touch .virc in your home folder should be enough.

Now, something I strongly recommend, is to install rxvt. It is, in my opinion, a better shell than the standard Cygwin one.
If you have installed apt-cyg, simply issuing apt-cyg rxvt should be enough to install it (mind you, that the 64-bits version of Cygwin is, at the moment I am writing this post, lacking rxvt!)

You may notice that once you start rxvt the background, foreground, and font are quite different from the usual shell. To configure this, as well as the appearance of the window, you need to create in your home directory a file named .Xdefaults.
Then add the following to this file:


Rxvt*geometry: 100x30        ! WxH
Rxvt*background: #000000
Rxvt*foreground: #ffffbf
Rxvt*scrollBar: True
Rxvt*scrollBar_right: True
Rxvt*font: Lucida Console-12
Rxvt*SaveLines: 2000
! VIM-like colors
Rxvt*color0:    #000000      ! pure black
Rxvt*color1:    #FFFFFF      ! pure white
Rxvt*color2:    #00A800
Rxvt*color3:    #FFFF00
Rxvt*color4:    #6495ED      ! cornflower blue
Rxvt*color5:    #A800A8
Rxvt*color6:    #00A8A8
Rxvt*color7:    #D8D8D8
Rxvt*color8:    #000000
Rxvt*color9:    #FFFFFF      ! pure white
Rxvt*color10:   #00A800
Rxvt*color11:   #FFFF00
Rxvt*color12:   #6495ED      ! cornflower blue
Rxvt*color13:   #A800A8
Rxvt*color14:   #00A8A8
Rxvt*color15:   #D8D8D8



We are still not done. You it may happen that if you SSH into a Linux machine and try to use some programs such as less, man or top they will fail with errors such as “unknown terminal type”. The problem is the TERM variable which rxvt sets to rxvt-cygwin which is unrecognized by your remote machine.


case "\$TERM" in
rxvt-cygwin)
TERM=rxvt
;;



to the .bashrc file in the home folder of your remote machine and things should work flawlessly.
An alternative, in case you are using a shortcut to run rxvt, is to add the flag -tn xterm.

If you are planing on using X, you should install the package xinit in Cygwin.
You can then run the Xserver and open an X terminal by running:

startxwin

or

startx

XWin.exe`