import algds.IOUtils;
/**
 * AlgDs, WS99, Aufgabe 34.
 * Ganzzahlige Potenzfunktionen.
 *
 * Die Laufzeiten haengen nicht von a ab (die Laufzeitunterschiede bei den
 * Multiplikationen duerften minimal sein), sondern nur von n.
 * Die Zeiten T(n) fuer beliebige Exponenten n liegen zwischen T(2**log2ganz(n))
 * und T(2*2**log2ganz(n)-1), wobei log2ganz der ganze Anteil des dyadischen
 * Logarithmus von n und ** der Potenzoperator ist. Also reicht es,
 * nur die Exponenten 2**k und 2**(k+1)-1 zu betrachten.
 * Ich bewerte nur Multiplikationen und Unterfunktions-Aufruefe, und zwar je mit 1.
 *
 * a) pow1(a,n)
 * T( 1)=T(  2**0  ) = 0
 * T( 2)=T(  2**1  ) = 2*T( 1)+3 =  3 = 3*(2**1-1)
 * T( 4)=T(  2**2  ) = 2*T( 2)+3 =  9 = 3*(2**2-1)
 * T( 8)=T(  2**3  ) = 2*T( 4)+3 = 21 = 3*(2**3-1)
 *       T(  2**k  ) =                  3*(2**k-1)
 * T( 1)=T(2*2**0-1) = 0
 * T( 3)=T(2*2**1-1) = 2*T( 1)+4 =  4 = 4*(2**1-1)
 * T( 7)=T(2*2**2-1) = 2*T( 3)+4 = 12 = 4*(2**2-1)
 * T(15)=T(2*2**3-1) = 2*T( 7)+4 = 28 = 4*(2**3-1)
 *       T(2*2**k-1) =                  4*(2**k-1)
 *
 * T(n) prop. n ==> O(pow1(a,n)) = n
 *
 * b) pow2(a,n)
 * T( 1)=T(  2**0  ) = 0
 * T( 2)=T(  2**1  ) = T(1)+2 = 2*1
 * T( 4)=T(  2**2  ) = T(2)+2 = 2*2
 * T( 8)=T(  2**3  ) = T(4)+2 = 2*3
 *       T(  2**k  ) =          2*k
 * T( 1)=T(2*2**0-1) = 0
 * T( 3)=T(2*2**1-1) = T(1)+3 = 3*1
 * T( 7)=T(2*2**2-1) = T(3)+3 = 3*2
 * T(15)=T(2*2**3-1) = T(7)+3 = 3*3
 *       T(2*2**k-1) =          3*k
 *
 * T(n) prop. log2(n) ==> O(pow2(a,n)) = log(n)
 * 
 * @author Christian Semrau, 26.12.1999
 * <a href="mailto:Christian.Semrau@student.uni-magdeburg.de">
 * Christian.Semrau@student.uni-magdeburg.de</a>
 */
class ChS_Aufg34 {
	static int c = 0;

public static void main(java.lang.String[] args) {
  System.out.println("AlgDs WS99 Aufgabe 34, Christian Semrau 26.12.1999");
  System.out.println("Berechnet ganzzahlige Potenzen.");

  long a=1; int n;
  for (n = 1; n<129; n++){
	  c=0;
	  pow2(a, n);
	  System.out.println(n+" "+c);
  }
  /*
  do{
	System.out.print("Basis:   "); a = IOUtils.readLong();
	System.out.print("Exponent:"); n = IOUtils.readInt();
	System.out.println(a + " hoch " + n + " = " + pow2(a, n));
  }while(n >= 0);
  */
}

/**
 * Ganzzahlige Potenzfunktion a hoch n.
 * O(pow1(a,n)) = n
 */
public static long pow1(long a, int n) {
	if (n <= 1) {
		if (n < 0) return 0; else if (n == 0) return 1; else return a;
	} else
	if (n%2 == 0) {
		c+=3; return pow1(a, n/2)*pow1(a, n/2);   // 2F+M
	} else {
		c+=4; return pow1(a, n/2)*pow1(a, n/2)*a; // 2F+2M
	}
}

/**
 * Ganzzahlige Potenzfunktion a hoch n.
 * O(pow2(a,n)) = log(n)
 */
public static long pow2(long a, int n) {
	if (n <= 1) {
		if (n < 0) return 0; else if (n == 0) return 1; else return a;
	} else
	if (n%2 == 0) {
		c+=2; return pow2(a*a, n/2);     // F+M
	} else {
		c+=3; return pow2(a*a, n/2) * a; // F+2M
	}
}
/** Kurzversion von pow2. */
public static long pow2a(long a, int n) {
	return (n<=1 ? (n<0 ? 0 : n==0?1:a) : pow2(a*a, n/2)*(n%2==0?1:a));
}
} // class ChS_Aufg34