全体像 はじめに:計算できるもの、できないものとは 扱いにくい理由、暗号化、解読、鍵、長さ、ビット数、遺伝子、多重配列アラインメント問題、組合せ、指数関数
計算できるもの、計算できないもの ―実践的アプローチによる計算理論入門 (John MacCormick(著)、松崎 公紀(監修)、長尾 高弘(翻訳)、オライリー・ジャパン)の全体像、1章(はじめに:計算できるもの、できないものとは)、演習問題1.3の解答を求めてみる。
1.2
(a)
コード
package main
import (
"fmt"
"math/big"
)
func main() {
ls := []*big.Int{big.NewInt(30), big.NewInt(200), big.NewInt(1000)}
d := big.NewInt(1000000000)
d.Mul(d, big.NewInt(60*60*24))
y := new(big.Int)
y.Set(d)
y.Mul(y, big.NewInt(365))
one := big.NewInt(1)
two := big.NewInt(2)
for _, l := range ls {
n := big.NewInt(1)
i := big.NewInt(0)
for i.Cmp(l) == -1 {
n.Mul(n, two)
i.Add(i, one)
}
nd := new(big.Int)
nd.Set(n)
nd.Div(nd, d)
nd.Add(nd, one)
ny := new(big.Int)
ny.Set(n)
ny.Div(ny, y)
ny.Add(ny, one)
fmt.Printf(
"鍵の長さ: %vビット\n"+
"日数: 約%v日\n"+
"年数: 約%v年\n",
l, nd, ny)
}
}
入出力結果(Terminal, Zsh)
% go run main.go
鍵の長さ: 30ビット
日数: 約1日
年数: 約1年
鍵の長さ: 200ビット
日数: 約18598819956701276337291227920615307899562534651日
年数: 約50955671114250072156962268275658377807020643年
鍵の長さ: 1000ビット
日数: 約124017199905817976961623269567129839185347779132584908268952591246568408695015754918194256807372205801804938995087169771433697371029203014305377055262714986156650089986391562331262437558592258586550395626771371238235902098002300550453304906783299339289018477751001645459032752681164634107日
年数: 約339773150426898567018145944019533805987254189404342214435486551360461393684974671008751388513348509046040928753663478825845746221997816477548978233596479414127808465716141266660992979612581530374110672950058551337632608487677535754666588785707669422709639665071237384819267815564834614年
%
鍵の長さを1ビットずつ長くするたびに、プログラムの予想実行時間は2倍ずつ長くなる。
(b)
テストする挿入方法は、
通り。