階乗、組み合わせ、順列、絶対値

プログラムでの階乗、組み合わせ、順列の求め方について。 階上はそのままですが、組み合わせや順列は公式通りに階乗から計算しようとすると、計算途中にオーバーフローする可能性が高くなり、あまり好ましくないです。そのため、漸化式を用いて記述することが多いです。以下Cでのサンプルコード。

long kai(int n){//nの階乗
    long p=1;
    int i;
    for(i=2;i<=n;i++){
        p=p*i;
    }
    return p;
}

long pof(int n, int r){//nのr乗
    int i;
    long p=1;
    
    for (i=0 ; i < r ; i++){
        p=p*n;
    }
    return p;
}

long combi(int n, int r){//nCr
    int i;
    long p=1;
    
    for (i=1;i <= r;i++){
        p=p*(n-i+1)/i;
    }
    return p;
}

long perm(int n, int r){//nPr
    int i;
    long p=1;
    
    for (i=1;i<=r;i++){
        p=p*(n-i+1);
    }
    return p;
}

再帰関数を使っても実装できるかもしれませんが、こちらのほうがわかりやすいので。これより高速なコードは存在しますが、簡単なのを書きました。

べき乗については、繰り返し2乗法というアルゴリズムが存在します。nのr乗を、n, nの2乗, 4乗, 8乗, ……に分解して高速化する方法です。



ところで、絶対値について、絶対値を求める関数absは標準で用意されています。 普通人間が絶対値を計算したいとき、ifで場合分けして〜というコードを書きそうですが、実は、２進数のビット演算のみで、三行で構成されています。高速にできている… Cなどの言語はコンパイル作業によって最適化されます。DebugをReleaseにすると更に最適化されます。 アーキテクチャまで考えられたプログラムを書けるようになりたい・・・