積を計算することは、現代では0と位取り表記によって大変容易になったが、古代エジプトなどでは専門性を求められるものであった。
積は和を複数回繰り返すことによって実現できる。コンピュータではビット演算を組み合わせることによってより効率的に積を計算することができる。
以下は、アーメスのアルゴリズムとその改善版を記述したコードである。
コードが最適化されているか常に思考し、よりよいコードに変換する作業を繰り返すことが大切だとわかる。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // | |
| // 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; | |
| } |
