c – nullteilerfrei

Binary Determinantal Complexity

rattle code, mathematics 2014-11-11

My good friend and colleague Christian Ikenmeyer and I wrote this cute preprint about polynomials and how they can be written as the determinant of a matrix with entries equal to zero, one and indeterminantes. Go ahead and read it if you know even just a little math, it's quite straightforward. The algorithm described in section 3 has been implemented and you can download the code from my website at the TU Berlin. Compilation instructions are in ptest.c, but you will need to get nauty to perform the entire computerized proof.

AVR programming with Ralf

born code, technology 2012-03-31

Just a checklist for programming the microncontroller Ralf gave me yesterday ((Also check out this useful article)) * you need a functional eclipse installation * Install WinAVR and be sure that it is in the PATH by executing avr-gcc from a command prompt * Install the AVR-Interface into eclipse via Help → Install New Software → Add. Then paste the following link in the URL Box:

http://avr-eclipse.sourceforge.net/updatesite/

* When I create a new project, I need to adjust the following settings in the project properties: * AVR → AVRDude Programmer click on New, Name: USBASP, Programmer Hardware (-c) USBasp, http://www.fischl.de/usbasp/ * AVR → AVRDude, Advance be sure the check Disable device signature check * AVR → Target Hardware MCU Type select ATmega168 and set the MCU Clock Frequency to 12000000 (that's $12\cdot10^6$) * C/C++-Build → Settings unter Tool Settings check Generate HEX file for Flash memory * C/C++-Build → Settings unter Tool Settings, AVR Compiler → Optimization set the Optimization Level to Size Optimizations (-Os).

Zero out large blocks of memory

rattle code 2012-03-16

After a couple of tests, it turns out that the very simple

#include <limits.h>

inline void memzap(void *dest, unsigned long count) {
    asm( "cld"
#   if ULONG_MAX == 0xffffffff
    "\n" "andl $3, %%ecx"
    "\n" "rep  stosb"
    "\n" "movl %%ebx, %%ecx"
    "\n" "shrl $2, %%ecx"
    "\n" "rep  stosl"
#   else
    "\n" "andq $7, %%rcx"
    "\n" "rep  stosb"
    "\n" "movq %%rbx, %%rcx"
    "\n" "shrq $3, %%rcx"
    "\n" "rep  stosq"
#   endif
      : "=c" (count), "=D" (dest), "=b" (count)
      :  "c" (count),  "D" (dest),  "b" (count), "a" (0)
    );
}

is the fastest way to zero out a large block of memory, which is not very surprising. It is about 4 to 5 times faster than memset and about as fast as new [], if I can trust @tobi on that matter. I tried using MMX registers, but anything that involves actually looping over the memory region will be about as fast as memset. The only way to get a bit of speed is using the rep opcode. Tiny Edit: The above code is much more safe to compile on both 64 and 32 bit computers.