【python】第1回 チキチキ プログラミング初心者のための型に関する考察 ～pythonで基数変換できるかな？～【学習】
第1回 チキチキ プログラミング初心者のための型に関する考察 ～pythonで基数変換できるかな？～
はじめに
こんな記事を見たんですよ。
Sum of three cubes for 42 finally solved – using real life planetary computer
要は、 となる
（１～１００の自然数）
の組を求める問題です。
３３と４２以外のほとんどの整数については、解かれているか、解がないことが証明されていました。
今年に入って、３３の解がスパコンで解かれて、最近４２の解が５０万台のコンピュータをネットワークで接続し、アイドル時間を借りて計算を行う方式の分散コンピューティングで解かれました。（SETIプロジェクトみたいなもんかな？）
分散コンピューティングにより、今までの探索範囲よりも桁の範囲を広げて計算することができたのが勝因のようです。
ちなみに、答えは。。。
となります。
ちょっと確認してみますね。
ほんとだｗ
それで思ったんですよ。pythonって、こんなでかい値計算できるわけで、んでpythonって、いわゆる型推論してるけど、整数の大きさってどこまで使えるの？
型って？
むかしながらの、FORTRAN, pascal, Cなどのプログラミング言語には、確実に型ってのが存在しています。
簡単には、データを入れるための箱の形式＝コンピュータがデータの形式を判断し、正確に処理を行うための仕組みなのかなと思います。
C言語の主な型
C言語の例を見ると（一部処理系依存の部分がありますので、悪しからず）
| 型名 | 種類 | サイズ | 範囲 | 備考 |
|---|---|---|---|---|
| int | 整数 | 4byte | -2147483648 〜 2147483647 | 負数は２の補数表現 |
| short | 整数 | 2byte | -32768 〜 32767 | 負数は２の補数表現 |
| char | 整数 | 1byte | -128~127 | 負数は２の補数表現 |
| float | 実数 | 4byte | 1.17549e-38 〜 3.40282e+38（±10-38 〜 1038） | IEEE754浮動小数点形式 |
| double | 実数 | 8byte | 2.22507e-308 〜 1.79769e+308（±10-308 〜 10308） | IEEE754浮動小数点形式 |
つまり、型はそのデータがメモリ上でどう表現されているか、ということになります。
C言語の演算にかかわる型の扱われ方
C言語では変数を使うときは型同士のやり取りに細心の注意を払ってソースを書かなければなりません。
例えば、
#include <stdio.h>
int main(void){
// Your code here!
int x=3;
int y=5;
printf("%lf", x/y);
}出力は 「０．００００」 になります。
C言語では、整数を整数で割った余りは整数で返ってきます。
また、char型（8bit:-128~127)の整数をカウントアップしていき（そもそも１２７以上カウントアップできないのでintの変数を作ってそれをchar型に代入します）、どのように値が変化するか観察する処理を書いてみます。
#include <stdio.h>
int main(void){
// Your code here!
char c = 0;
int i;
for(i=0;i<300;i++)
{
c = i;
printf("%04d ", c);
if(i%25 == 0)printf("\n");
}
}実際の出力は、
0000 0001 0002 0003 0004 0005 0006 0007 0008 0009 0010 0011 0012 0013 0014 0015 0016 0017 0018 0019 0020 0021 0022 0023 0024 0025 0026 0027 0028 0029 0030 0031 0032 0033 0034 0035 0036 0037 0038 0039 0040 0041 0042 0043 0044 0045 0046 0047 0048 0049 0050 0051 0052 0053 0054 0055 0056 0057 0058 0059 0060 0061 0062 0063 0064 0065 0066 0067 0068 0069 0070 0071 0072 0073 0074 0075 0076 0077 0078 0079 0080 0081 0082 0083 0084 0085 0086 0087 0088 0089 0090 0091 0092 0093 0094 0095 0096 0097 0098 0099 0100 0101 0102 0103 0104 0105 0106 0107 0108 0109 0110 0111 0112 0113 0114 0115 0116 0117 0118 0119 0120 0121 0122 0123 0124 0125 0126 0127 -128 -127 -126 -125 -124 -123 -122 -121 -120 -119 -118 -117 -116 -115 -114 -113 -112 -111 -110 -109 -108 -107 -106 -105 -104 -103 -102 -101 -100 -099 -098 -097 -096 -095 -094 -093 -092 -091 -090 -089 -088 -087 -086 -085 -084 -083 -082 -081 -080 -079 -078 -077 -076 -075 -074 -073 -072 -071 -070 -069 -068 -067 -066 -065 -064 -063 -062 -061 -060 -059 -058 -057 -056 -055 -054 -053 -052 -051 -050 -049 -048 -047 -046 -045 -044 -043 -042 -041 -040 -039 -038 -037 -036 -035 -034 -033 -032 -031 -030 -029 -028 -027 -026 -025 -024 -023 -022 -021 -020 -019 -018 -017 -016 -015 -014 -013 -012 -011 -010 -009 -008 -007 -006 -005 -004 -003 -002 -001 0000 0001 0002 0003 0004 0005 0006 0007 0008 0009 0010 0011 0012 0013 0014 0015 0016 0017 0018 0019 0020 0021 0022 0023 0024 0025 0026 0027 0028 0029 0030 0031 0032 0033 0034 0035 0036 0037 0038 0039 0040 0041 0042 0043
となります。
char型の変数の範囲は-128~127までですので、127までは順調にカウントアップしています。
127の次は、-128,-127,...と負の数が登場して１ずつ増えてゆき-2,-1の後、0,1,2,3とカウントアップになっています。
C言語は声高らかに、自分の使うデータ型を宣言して、プログラマの理解の範疇で適切な処理を施していくプログラミング言語ですので、別の型同士の演算などはC言語で決められているルールをプログラム製作者が正確に理解していないと、データ表現の違いによるバグを引き起こしてしまいます。
pythonなどの言語は、その辺はシステムの方が推定して適切な型を内部で使ってくれるのでこのようなことは起こりにくい？と思われます。
ちょっと型の中身をのぞいてみる
ちょっと細かい話になるのですが、基本情報処理技術者試験や応用情報処理技術者試験のテクノロジ系でよく出てくる話ですので、知ってるといいことあるかもしれないよ。
型のある言語C/C++, JAVA, C#等では大体同じような型が使われており、中身も共通する部分が多いです。
一番簡単な整数型に関して、考えてみます。
よく言われるように、コンピュータの内部データはすべて、０と１でできています。（皆さんの書いたソースコード自体も内部では０と１で表される命令群に変換されます）
０と１は、電気的にはONかOFFの信号を表しています。電気的にONかOFFかの羅列でプログラムやデータを読んだり書いたり、加工していったりするんですね。
よく考えてみると面白くないですか？
２進数の数値表現
前にも書いたのですが、pythonでは、細かいことをやらない限りプログラム製作者はこんなこと気にすることはないのかもしれませんが、知っているとバグの原因の特定が早かったり、ほかの言語への対応が簡単になるかもです。（まぁ、私自身がpython初心者なんですが。。。）
それではさっそく。
整数型は、「プログラム上の処理で扱う変数の入れ物として、整数を表すもの」です。大きさが決まった整数を入れる箱だと思うといいかも。
内部では２進数で値を表します。
２進数は、いわゆるコンピュータの中で使われているとされる０と１しかない値の表現です。１０進数は０，１，２。。。８，９で１０、１１と１０ごとに桁が上がっていきます。
ちなみに、このように、桁が上がるベースとなっている数を「基数（radix)」といいます。
２進数は、
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | … |
| ０ | １ | １０ | １１ | １００ | １０１ | １１０ | １１１ | １０００ | … |
と、２進数だと２ごとに桁が上がっていきます。
何とか進数（ｎ進数）には、２進数以外にも、４進数、５進数・・・と無限に進数があります。
コンピュータの世界では、２，８，１６進数を覚えておけば間違いないです。
１０進数と１～９進数までの数字の並びの対応表を以下に示しておきます。
| 10進数 | 2進数 | 3進数 | 4進数 | 5進数 | 6進数 | 7進数 | 8進数 | 9進数 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 10 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 3 | 11 | 10 | 3 | 3 | 3 | 3 | 3 | 3 |
| 4 | 100 | 11 | 10 | 4 | 4 | 4 | 4 | 4 |
| 5 | 101 | 12 | 11 | 10 | 5 | 5 | 5 | 5 |
| 6 | 110 | 20 | 12 | 11 | 10 | 6 | 6 | 6 |
| 7 | 111 | 21 | 13 | 12 | 11 | 10 | 7 | 7 |
| 8 | 1000 | 22 | 20 | 13 | 12 | 11 | 10 | 8 |
| 9 | 1001 | 100 | 21 | 14 | 13 | 12 | 11 | 10 |
| 10 | 1010 | 101 | 22 | 20 | 14 | 13 | 12 | 11 |
| 11 | 1011 | 102 | 23 | 21 | 15 | 14 | 13 | 12 |
| 12 | 1100 | 110 | 30 | 22 | 20 | 15 | 14 | 13 |
| 13 | 1101 | 111 | 31 | 23 | 21 | 16 | 15 | 14 |
| 14 | 1110 | 112 | 32 | 24 | 22 | 20 | 16 | 15 |
| 15 | 1111 | 120 | 33 | 30 | 23 | 21 | 17 | 16 |
この表を見てわかる通り、ｎ進数には０～（n-1)の数字しかでてきません。
だから２進数は、０と１なんですね。
１０進数と２進数の変換
１０進数をｎ進数に変換するときは、以下の図のように目的の数をｎで割っていき、余りを並べるとｎ進数に変換できます。
実際に、１０進数の１３を２進数に変換してみます。
１０進数の１３は２進数では１１０１であることがわかりました。
ほかの進数でも同じようにできます。１０進数の２４を５進数に変換します。
１０進数の１４は５進数では２４であることがわかりました。
２進数と１０進数の変換
２進数を１０進数に戻すときのイメージを考えるために、１０進数を基数をベースに分解してみます。
桁の仕組みってこうなってたんですね、ｎ桁目＝基数のｎ乗桁目になっていて、すべての桁の基数の重みｘその桁の数をかけて足したものが、元の数値になる（よくわからない説明ｗ）
多分２進数で同じことをやってみるとすぐわかります。
２進数は、基数２なので桁の重みはと増えていきます。（2進のときは桁のことをビット(bit)と呼びます、知ってますよね？）
２進数の1011で考えてみると
2進数の１０１１は10進数では１１です（1と0しかない数字選んじゃって分かりづらくなってしまったｗ）
どんな基数の時もこのルールは一緒です。
8進数の765を10進数に変換してみます。
これで、ｎ進数⇔10進数の変換ができるようになりましたね！
２進数と整数型
整数型は、コンピュータの内部形式では２進数で表すことはわかりました。現実世界ではほとんどのものが１０進数で表されていますので、普段は２進数やほかのｎ進数について考えることもないと思います。
実際プログラミングをしていても、pythonを使っている分にはそんなに気にならないのかなと思います。
（でも、実質C言語と絡むと、ちゃんと理解してるしかないし、基本情報では基礎事項として入ってるし。。。）
コンピュータの回路には、一度にデータをやり取りできる数が決まっています。
CPUの裏側を見ると細かい足がたくさん生えています、このうちの何本かがデータをやり取りする配線になっています。
CPUの何ビットCPUというのは一度にメモリとのやり取りをするのに使えるビット数のことです。(正確にはレジスタの幅かな？）
大体、データや命令が２進数で表されることもあって、８の倍数（乗数）で増えていきます。
一度にやり取りできる命令やデータのビット数が決められているということは、先ほどの計算のようにただ１０進数を２進数に変換したものを使うと、ビット数が足りなくなったり、余ったりと、いろいろ不都合が出てきます。８ビットしか使えないのに２ビットだけ使ってるとか、８ビットしか使えないのに、データが１５ビットとか、多くても、少なくてもめんどくさいことになりそうですよね。
そこで型の登場なのですが、もう一度型とデータサイズ（ビット幅）の関係を見てみます。
| 型名 | 種類 | サイズ |
|---|---|---|
| int | 整数 | 4byte |
| short | 整数 | 2byte |
| char | 整数 | 1byte |
| float | 実数 | 4byte |
| double | 実数 | 8byte |
一番小さいchar型で1byte=8bitですね。
このときに、1ってデータはどのように入っているのでしょうか？箱が8ビットでできているんで、当然１のみってことはあり得ません。
正解は、
00000001でした。箱の何も入っていないところは0で埋めます。
それでは、すべて1で埋まった数はいくつでしょうか？
8ビットの整数では０～２５５の範囲があらわされることがわかりました。
さて、この11111111に1足しちゃったらどうなるでしょう？
数学的には、
です。9ビットの100000000になりますね。でも、今用意している箱は8ビットしかありません。
型のある言語では、この場合、あふれた1ビットは捨てられます。
結果残った00000000が答えとなります。なので、11111111+1は０です(笑)
この現象を桁あふれ(Overflow：オーバーフロー)と呼びます。
聞いたことはありますよね。
所感
Sum of three cubes 問題を発端に、pythonの整数の扱いについて、いろいろ考えてみました。
今回は正の整数についてのみ考えましたが、次回は負の数や小数についても考えてみたいと思います。
気づく人は気づいたと思いますが、途中に出てきた表の整数範囲と、今回導き出した範囲は異なっています。この違いについても次回には触れようと思います。
へば、またねー！
