aioug conference Sangam 2011

Last year I visited Bangalore with the intention of presenting at the aioug conference Sangam 2011. The turnout was poor but my slides were posted here. It is about concurrency.

Visualizing algorithm growth rates

I have been singing paeans about ‘R’, the statistics language, in this blog because it helps one understand and code statistical programs which are the key to various calculations in the fields of project management and capacity planning.
I have also been mulling about how I can generate graphs of algorithm growth rates when input sizes vary. This is child’s play when we use ‘R’.

I could reproduce the graph from Jones and Bartlett’s ‘Analysis of Algorithms’ quite easily. Visualizing these growth rates easily like this is helpful.

The code is general. Nothing specific to algorithm analysis. Immensely useful.

png("funcgrowth.png")
curve(x*x/8,xlab="",ylab="",col="blue",ylim=c(0,200),xlim=c(2,38))
par(new=TRUE)
curve(3*x-2,lwd=3,ylim=c(0,200),xlab="",ylab="",xlim=c(2,38),lty="dashed")
par(new=TRUE)
curve(x+10,lty="dashed",lwd=1,ylim=c(0,200),xlab="",ylab="",xlim=c(2,38))
par(new=TRUE)
curve(2*log(x),col="blue",lty="dashed",lwd=1,ylim=c(0,200),xlab="",ylab="",xlim=c(2,38))
legend(20,180, c("x*x/8","3*x-2","x+10","2*log(x)"), lty=c(1,2,2,2), lwd=c(2.5,2.5,1,1),col=c("blue","black","black","blue"))
dev.off()

‘atoi’ function code kata

I recently coded the ‘atoi’ function in Java as part of an assignment while I was reading ‘Hacker’s delight’, a delightful book full of bit twiddling tricks and techniques.
These ideas reduce the number of instructions used to execute code and should be followed by Java coders who work on critical transaction processing applications to increase throughput.

package com.atoi;

import java.math.BigInteger;

import static junit.framework.Assert.assertEquals;

/**
 * User: Mohan Radhakrishnan
 * Date: 10/21/12
 * Time: 1:19 PM
 */
public class Atoi {

    /**
     * Convert 'char' to 'int'.
     * @param chars
     * @return result final result or result till an ASCII space
     *         if encountered.
     */
    public int atoi( char[] chars ) {

        assert( chars != null && chars.length != 0 );
        int i = 0;
        int result = 0;
        char temp = 0;

        while( i < chars.length ){
            if( (chars[ i ] ^ 0x20)  == 0 ){
                return result;//Stop at the first ASCII space
            }else if ( isBetween0And9( chars[ i ] - '0')){
                //calculate
                result = ( result * 10 ) + ( chars[ i ] - '0');
            }
            i++;
        }
        return result;

    }

    /**
     * Referred 'Hacker's delight' which
     * has bit techniques that helps in reducing
     * instructions.
     * If the result of this bit twiddling is 0x80808080
     * then the input is less than 9
     * The advantage is that a extensible function to find
     * any range can be coded with slight modification.
     * @param input
     * @return result of the check
     */

    public boolean isBetween0And9(int input){
        System.out.println(  "isBetween0And9 [" + Integer.toBinaryString( input ) + "]");
        int y = ( input & 0x7F7F7F7F ) + 0x76767676;
        y = y | input;
        y = y | 0x7F7F7F7F;
        y = ~y;
        System.out.println( "~y [" + Integer.toBinaryString( y ) + "]");
        return( 0x80808080 == y );

    }
}

I also coded JUnit tests mainly to test the logic from “Hacker’s Delight’ that checks for a overflow before it occurs. That was interesting because I could check if an ‘int’ exceeds Integer.MAX_INT or underflows without using the Java libraries or checked exceptions. Since this code is not simple to understand I coded it and tested it but didn’t copy it into this entry. Later.

public class AtoiTest {
    
    @Test
    public void testAtoi() throws Exception {
        Atoi atoi = new Atoi();
        try{
            assertEquals( 5, atoi.atoi( new char[] {'5'}));
            assertEquals( 0, atoi.atoi( new char[] {'A'}));
            assertEquals( 5, atoi.atoi( new char[] {'5','A'}));
            assertEquals( 5, atoi.atoi( new char[] {'A','5'}));
            assertEquals( 0, atoi.atoi( new char[] {' ','5'}));
            assertEquals( 56, atoi.atoi( new char[] {'5','6',' ','5'}));
            assertEquals( 506, atoi.atoi( new char[] {'5','0','6',' ','5'}));
        }catch ( Exception e){
            fail();
        }
    }
}