This is a tetranacci algorithm in JAVA version.


It compares two algorithms.


import java.io.PrintWriter;

public class Assignment1 {

    long tetranacci1(int index){
        // index start from 0,  index >= 0

        if(index<3){
            return  0;
        }else if(index==3){
            return  1;
        }
        else return tetranacci1(index-1) + tetranacci1(index-2)+ tetranacci1(index-3) + tetranacci1(index-4);
    }

    long tetranacci2(int index){
        // index start from 0, index >= 0
        long[] result = teranacci2Helper(index);
        if(index< 4){
            return result[index];
        }else return result[3];
    }

    long [] teranacci2Helper(int index){
        long[] baseArr = {0,0,0,1};
        if (index < 4){
            return  baseArr;
        }
        else{
            long[] preArr = teranacci2Helper(index-1);
            long s = 0;
            for (int i=0;i<4;i++ ){
                s+=preArr[i];
            }
            for(int i=0;i<3;i++){
                baseArr[i] = preArr[i+1];
            }
            baseArr[3] = s;
            return baseArr;
        }
    }
    double countTime1(int index){
           double t0 = System.currentTimeMillis();
           System.out.println("Tetranacci1 ("+index+") = "+tetranacci1(index));
           double t1 = System.currentTimeMillis();
           return  t1 - t0;
    }
    double countTime2(int index){
        double t0 = System.currentTimeMillis();
        System.out.println("Tetranacci2 ("+index+") = "+tetranacci2(index));
        double t1 = System.currentTimeMillis();
        return t1-t0;
    }

    public static void main(String [] args){

        int num = 8;
        double time[][] = new double[num][2];
        Assignment1 ass1 = new Assignment1();
        for(int i=1;i<=num; i++){
            time[i-1][0] = ass1.countTime1(5*i);
            time[i-1][1] = ass1.countTime2(5*i);
        }
        PrintWriter writer;
        try {
            writer = new PrintWriter("out.txt", "utf-8");
            for(int i=0; i<num; i++){
                writer.println(time[i][0] + " " + time[i][1]);
            }
            writer.close();
        }catch (Exception e){
            e.printStackTrace();
        }
    }
}