2020.11.30 QA プログラム関連

時間の計測をしても 0 としか表示されない

計算量の評価は最悪の場合でやってます. たとえば prime_factorization では素数の入力で最悪の振る舞いとなります. 合成数の場合は大きい数を入力しても比較的高速に完了する場合もあります. 
def prime_factorization(N) {
  K = 2;
  while (N>=2) {
    if (N % K == 0) {
      N = idiv(N,K);
      print(K,0); print(", ",0);
    }else{
      K = K+1;
    }
  }
  print(" ");
}

T0=time();
A=pari(nextprime,10^6);
B=pari(nextprime,10^7);
printf("A*B=%aを分解\n",A*B);
prime_factorization(A*B);
T1=time();
printf("時間: %a\n",T1[0]-T0[0]);

end$
このプログラムを実行すると 
[0.59375,0,42036064,56.196]
1000003
10000019
A*B=10000049000057を分解
0
1000003, 10000019,  
0
[4.45312,0,442038928,60.0633]
時間: 3.85938
ちなみに pari(factor,C) は組み込みの素因数分解函数で, 上記の問題は一瞬で答えを 戻します. 

[1900] pari(factor,A*B);
[ 1000003 1 ]
[ 10000019 1 ]
しかし 50 桁くらいの数になると gcd の計算は一瞬でおわりますが, 素因数分解はなかなか戻らないので abort (計算の中断) をしました. 
[1901] C=pari(nextprime,10^50);
100000000040153319296670738688678203676948648951808
[1902] pari(factor,C*C);
  C-c C-cinterrupt ?(q/t/c/d/u/w/?) t
Abort this computation? (y or n) y
return to toplevel
[1903] igcd(C*C,C);
100000000040153319296670738688678203676948648951808

リストの共通部分を求める函数

base_intersection(A,B)

cons とは 

[1883] A=cons(3,[5,1]);   // 3 を リスト [5,1] の最初にくっつける.
[3,5,1]
[1884] B=cons(3,[]);
[3]
[1885] car(A);   // リストAの最初を取り出す.
3
cons などのマニュアル
参考: car, cons は LISP 言語由来の関数名です. 詳しい説明

type 函数とは type(A) は変数 A に格納されているオブジェクト(データ)の型を 数字で戻します. このデータ型をあらわす数字の意味は このページ を参照.