// JH 01.2013
//
// Løsningsforslag til Oppgave 4, uke 2
//
// Et program som tester hvor lang tid maskinen bruker for å utføre hhv.
// n log(n), n^2, n^3, n^5, 2^n og n! addisjoner for n = 10, 20, 30, .., 100.
//
// Programmet bruker altfor lang tid for n! når n > 10, dette testes ikke.
// For n=10 brukes på min Linuxboks ca. 0.1 sek. kjøretid for 10! addisjoner,
// d.v.s. at vi for n=15 ville ha brukt 11*12*13*14*15 = 360360 ganger så
// lang tid, m.a.o. ville vi ha brukt ca. 36000 sek = 10 timer for å gjøre
// 15! addisjoner.
//
// For 2^n blir kjøretiden for stor for n > 30
//
// For de tilfellene der antall addisjoner blir lite bruker
// maskinen så lite kjøretid at vi ikke klarer å måle det, og det vil bli
// skrevet ut at tiden er 0.0.

import java.io.*;
import java.util.*;

public class uke_2_4
{

   public static void main(String args[])
   {
       int n_min = 10, n_max = 100, n_step = 10; 
       double n, i;
       double n_log_n, n_i_annen, n_i_tredje, n_i_femte;
       double to_i_nte = 1.0, n_fak = 1.0;
       long T;
        
       System.out.println("--------------------------------------------------------------------------");
       System.out.println(" n  n·logn T     n² T       n³ T       n⁵     T      2^n    T        n!  T");
       System.out.println("--------------------------------------------------------------------------");

       
       for (n = n_min; n <= n_max; n += n_step)
       {
	   System.out.printf("%3.0f    ", n);

	   // Beregner de forskjellige funksjonene av n

	   n_log_n = n * Math.log(n);
	   n_i_annen = n * n;
	   n_i_tredje = n * n * n;
	   n_i_femte = n_i_annen * n_i_annen * n;

	   for (i = 0; i < n_step; i++)
	   {
	       to_i_nte *= 2;
	       n_fak *= (n - i);
	   }

	   // Utfører det antall addisjoner som er gitt av 
	   // funksjonsverdiene og tar tiden. Egentlig tar vi 
	   // her tiden på alt som skjer i hver iterasjon
	   // i for-løkkene

	   System.out.printf("%3.0f ", n_log_n);
	   T = System.currentTimeMillis();
	   for (i = 0; i < n_log_n; i++);
	   T = System.currentTimeMillis() - T;
	   System.out.printf("%1d  ", T);

	   System.out.printf("%5.0f ", n_i_annen);
	   T = System.currentTimeMillis();
	   for (i = 0; i < n_i_annen; i++);
	   T = System.currentTimeMillis() - T;
	   System.out.printf("%1d  ", T);

	   System.out.printf("%7.0f ", n_i_tredje);
	   T = System.currentTimeMillis();
	   for (i = 0; i < n_i_tredje; i++);
	   T = System.currentTimeMillis() - T;
	   System.out.printf("%1d  ", T);

	   System.out.printf("%6.1e ", n_i_femte);
	   T = System.currentTimeMillis();
	   for (i = 0; i < n_i_femte; i++);
	   T = System.currentTimeMillis() - T;
	   System.out.printf("%5d  ", T);

	   System.out.printf("%6.1e ", to_i_nte);
	   if (n <= 30)
	   {
	       T = System.currentTimeMillis();
	       for (i = 0; i < to_i_nte; i++);
	       T = System.currentTimeMillis() - T;
	       System.out.printf("%4d  ", T);
	   }
	   else
	       System.out.printf("   *  ");

	   System.out.printf("%8.1e ", n_fak);
	   if (n <= 10)
	   {
	       T = System.currentTimeMillis();
	       for (i = 0; i < n_fak; i++);
	       T = System.currentTimeMillis() - T;
	       System.out.printf("%2d", T);
	   }
	   else
	       System.out.printf(" *");
	   
	   System.out.println();
       }
       System.out.println("--------------------------------------------------------------------------");
   }
}