アルゴリズム プログラム 積

multiplication.cpp

//
//  multiplication.cpp
//  CplusplusPractice
//
//  Created by masai on 2015/06/27.
//  Copyright (c) 2015年 masai. All rights reserved.
//

#include <iostream>


// xの最上位ビットを評価する(奇数判定する)
bool odd(int n){ return n & 0x1; }

// xを右へ1つシフトする(1/2する)
int half(int n){ return n >> 1; }

// 乗法1 a + a + ... + a
int multiply0(int n, int a){
    if(n == 1) return a;
    return multiply0(n - 1, a) + a;
}


// 乗法2 a + a + a .. + a = (a + a) + (a + a) + ... + a
int multiply1(int n, int a){
    if (n == 1) return a;
    
    // a + a + a + a = (a + a) + (a + a)
    int result = multiply1(half(n), a + a);
    
    // (a + a) + (a + a) + (a + a) (nの2進数表現における1の数(population count) - 1 だけ呼ばれる)
    if(odd(n)){
        std::cout << "plus" << std::endl;
        result = result + a;
    }
    
    return result;
}

// おまけ: 16進数表現
void output16(int a){
    printf("a = 0x%x", a);
}

// 15倍の加法連鎖
int multiply_by_15(int a){
    int b = (a + a) + a;
    int c = b + b;
    return (c + c) + b;
}

// 乗累算1（関数呼び出しを減らす）
int multi_acc0(int r, int n, int a){
    if(n == 1) return r + a;
    
    if(odd(n)){
        return multi_acc0(r + a, half(n), a + a);
    }else{
        return multi_acc0(r, half(n), a + a);
    }
}

// 乗累算2（記述を単純化する）このような状態を末尾再帰(tail-recursive)という
int multi_acc1(int r, int n, int a){
    if(n ==1)return r + a;
    
    if(odd(n)) r = r + a;
    return multi_acc1(r, half(n), a + a);
}

// 乗累算3 比較回数の削減(比較の順序によって計算回数が減るケースがある)
int multi_acc2(int r, int n, int a){
    if(odd(n)){
        r = r + a;
        if(n ==1)return r;
    }
    return multi_acc2(r, half(n), a + a);
}

// 乗累算4 正確なtail-recursive → 再帰から繰り返し構造に置き換えることが簡単
int multi_acc3(int r, int n, int a){
    if(odd(n)){
        r = r + a;
        if(n ==1)return r;
    }
    
    n = half(n);
    a = a + a;
    
    return multi_acc3(r, n, a);
}

// 乗累算5 再帰から繰り返し構造への置き換え
int multi_acc4(int r, int n, int a){
    while(true)
    {
        if(odd(n)){
            r = r + a;
            if(n ==1)return r;
        }
        
        n = half(n);
        a = a + a;
    }
}

// ヘルパー1
int multiply2(int n, int a){
    if(n == 1) return a;
    return multi_acc4(a, n - 1, a);
}

// ヘルパー2
int multiply3(int n, int a){
    // nが奇数になるまで、1/2を繰り返す
    while(!odd(n)){
        a = a + a;
        n = half(n);
    }
    return multiply2(n, a);
}

// ヘルパー3
int multiply4(int n, int a){
    // nが奇数になるまで、1/2を繰り返す
    while(!odd(n)){
        a = a + a;
        n = half(n);
    }

    if(n == 1) return a;
    
    // かならずnが奇数で呼び出すので奇数のときに行われる処理を事前に行っておく
    return multi_acc4(a, half(n - 1), a + a);
}


int main(int argc, char* argv[]){
    std::cout << "multiplication." << std::endl;

    // 和の再帰で積を表現
    std::cout << "multipliycation = add." << std::endl;
    std::cout << multiply0(3, 2) << std::endl;

    // 奇数
    std::cout << "odd" << std::endl;
    std::cout << odd(13) << std::endl;
    
    // 偶数
    std::cout << "even" << std::endl;
    std::cout << odd(12) << std::endl;
    
    // 1/2
    std::cout << "1/2" << std::endl;
    std::cout << half(5) << std::endl;
    
    // 積(アーメスのアルゴリズム)
    std::cout << "egyption multiplycation." << std::endl;
    std::cout << multiply1(6, 2) << std::endl;
    
    // おまけ: 16進表現
    output16(100);
    
    // 15の加法連鎖
    std::cout << "multipy by 15." << std::endl;
    std::cout << multiply_by_15(30) << std::endl;
    
    // 乗累算
    std::cout << multi_acc1(0, 5, 100) << std::endl;
    
    std::cout << "optimize multipy." << std::endl;
    std::cout << multi_acc2(0, 5, 100) << std::endl;
    std::cout << multi_acc3(0, 5, 100) << std::endl;
    std::cout << multi_acc4(0, 5, 100) << std::endl;
    
    // ヘルパー呼び出し
    std::cout << multiply2(5, 100) << std::endl;
    std::cout << multiply3(5, 100) << std::endl;
    std::cout << multiply4(5, 100) << std::endl;
    
    
    return 0;
}