/* 専門コア情報処理演習教材 test5.c */

/* べき乗計算 */

/* コンパイル命令は
gcc -o t5 test5.c 
実行コマンドは
./t5
*/

#include<stdio.h>	// ヘッダ・ファイルを読み込みます。
#include<stdlib.h>
#include<math.h>
#include<time.h>

main()
{
  int a,e,n,t1,t2,i,x,f,b;

  printf("べき乗計算のサンプルプログラムです。\n\n");
  
  a = 2;
  e = 12345678;
  n = 10007;
  printf("a = %d\n",a);
  printf("e = %d\n",e);
  printf("n = %d\n",n);
  printf("a^e mod n を計算します。\n\n");

  printf("単純に１回ずつ掛ける :\n");
  t1 = clock(); // 開始時刻 
  x = 1;
  for(i=1; i<=e; i++) x = (x*a) % n;
  t2 = clock(); // 終了時刻
  printf("%d^%d mod %d = %d\n",a,e,n,x); 
  printf("所要時間 = %d マイクロ秒\n\n",t2-t1); // マイクロ秒は 1/10^6 秒


  printf("反復２乗法を用いる :\n");
  t1 = clock(); // 開始時刻
  x = 1;
  b = a;
  f = e;
  while(f > 0){
    if(f%2 == 1) x = (x*b) %n;
    f /= 2;
    b = (b*b) %n;
  }
  t2 = clock(); // 終了時刻
  printf("%d^%d mod %d = %d\n",a,e,n,x); 
  printf("所要時間 = %d マイクロ秒\n\n",t2-t1);
}