Team TripleFalcon. http://www.triplefalcon.com/

概要

 自然数に負の概念を導入したものが整数です。例えば、自然数 3 の前に符号を補って +3 や -3 と表記します。(参照→自然数)

Team TripleFalcon. http://www.triplefalcon.com/

定義

 自然数の二つ組全体の集合 N×N を考えます。組 (a,b) (∈N×N) の上に同値関係を定義します。

 定義1) (a1,b1)〜(a2,b2)
def
a1+b2=a2+b1

 この同値関係により商空間 (N×N)/〜 を Zと表記し整数(integer) と呼びます。

 この対等関係に従って、組の集合を分類してみます。組は、(a<b) のものと (a=b) のものと (a>b) に大別できます。集合は以下の様にきれいに分割できます。

表記 K(n+k,n) K(n,n) K(n,n+k)
同値類 {(a,b)|a,b,k∈N , a=b+k} {(a,b)|a,b∈N ,a=b} {(a,b)|a,b,k∈N , a+k=b}

 例えば、同値類 K(n+3,n) は集合 {(3,0), (4,1), (5,2), (6,3), ... } を意味し、同値類 K(n,n+5) は集合 {(0,5), (1,6), (2,7), (3,8), ...} を意味します。

 k>0 を自然数とします。同値類 K(n+k,n)k と表記します。また、同値類 K(n,n+k)-k と表記します。また、同値類 K(n,n) を 0 と表記します。自然数 k∈N を整数 K(n+k,n) と同一視することができます。

 上記の様に定義した この同値類を整数(integer) と呼ぶわけです。このような回りくどい定義をするのは、自然数に加法逆元が無いためです。自然数の加法と乗法だけを用いて、負の導入された整数上の演算をすべて説明しなくてはなりません。

Team TripleFalcon. http://www.triplefalcon.com/

加法

 関数 Φ:Z×Z→Z を定義します。

 定義2) Φ(K(a1,b1),K(a2,b2))
def
=
K(a1+a2,b1+b2)

 このとき、関数 Φ(i,j) を i+j と表記し、加法と呼びます。また、i+(-j) を i-j と表記します。直感的に言えば、左が3大きい集合(=3) と右が5大きい集合(=-5) を足すと、右が2大きい集合(=-2) になります。自然数 k∈N を整数 K(n+k,n) と同一視したとき、自然数の加法をちゃんと保存します。

Team TripleFalcon. http://www.triplefalcon.com/

乗法

 関数 Ψ:Z×Z→Z を定義します。

 定義3) Ψ(K(a1,b1),K(a2,b2))
def
=
K(a1*a2+b1*b2,a2*b1+a1*b2)

 このとき、関数 Ψ(i,j) を ij や i*j と表記し、乗法と呼びます。自然数 k∈N を整数 K(n+k,n) と同一視したとき、自然数の乗法をちゃんと保存します。

Team TripleFalcon. http://www.triplefalcon.com/

比較

 整数、K(a1,b1) , K(a2,b2) ∈Z に比較を導入します。

 定義4) K(a1,b1)≧K(a2,b2)
def
a1+b2≧a2+b1

 自然数 k∈N を整数 K(n+k,n) と同一視したとき、自然数の比較をちゃんと保存します。

Team TripleFalcon. http://www.triplefalcon.com/

 整数は加法に関して群 (Z,+,0) を作ります。整数の乗法に関しては、逆元が定義できない場合があるため群にはなりません。

Team TripleFalcon. http://www.triplefalcon.com/

注意

 定義としては、集合 S={+,-} と N の直積集合 S×N としてもかまわないし、その方が工学上使いやすいかもしれません。しかし、整数の定義に自然数の定義だけをきちんと使おうとすると、組み合わせが多いため、(例えば (正+負) や (負*正) など) 定義はかえって長くなると思われます。

 例えば、(+,a) と (-,b) の加法を定義する場合、(a>b) と (a<b) を場合分けしなくてはなりません。

Team TripleFalcon. http://www.triplefalcon.com/

整数の実装

 さて、整数をオブジェクト指向言語で「クラス」として実装する場合は次のことに注意する必要があります。まず、本当に (a,b) の集合などと”組の集合を本当に作って”しまう人はいないでしょう。以下の様にします。

 まず、自然数 a,b (∈N) に引き算(加法逆演算)を定義します。答えがない時は未定義とします。

定義5) a-b = ì
í
î
k ..case a≧b ,a=b+k
未定義 ..case a<b

 さらに整数を自然数の2組で代表させ、正規化元と勝手に呼びます。

定義6) 組 (a,b) が正規化元である
def
aかb が 0 である

 まず、同値類 K(n+k,n) = { (n+k,n) | n∈N } を考えます。( k,a,b∈ N とする) この集合は正規化元 (k,0) と同一視します。また、同値類 K(n,n+k) = { (n,n+k) | n∈N } を正規化元 (0,k) と同一視します。証明は省いて、次を主張します。そして、整数とは正規化元であると言い切ってしまいます。

 主張: 全ての整数は等価な正規化元が一意に存在する。

 言ってみれば、整数 -5 を (0,5) で表し、整数 3 を (3,0) で表してしまうわけです。どのような自然数の組 (a,b) , (a,b∈N) も必ず正規化元 (a-b,0)(0,b-a) になります。例として、3 + (-5) を次のように計算します。計算結果 (3,5) の同値類 K(n,n+2) に与えられる正規化元は、(0,2) なので以下が計算できます。

整数
3
(-5)
...?
 
正規化元
(3,0)
(0,5)
(3,5)→正規化します→
(0,2)
 
整数
-2

 上記の様に正規化元の上の演算として、整数の加法、乗法、減法が導けます。実装上は、自然数 N に符号の集合 {+,0,-} を与えて整数を表現します。整数 z∈ {+,0,-}×N を z=('+',n) のとき正規化元 (n,0) と、z=('-',n) のとき正規化元 (0,n) と同一視することで計算時間や記憶容量はもっと省けます。

 つまり、数学上の定義は簡潔性を重視し、実装は利便性を重視します。

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/


Team TRIPLE FALCON

アクション&シミュレーション ゲーミングとゲーム製作を真面目に考える 新進気鋭の研究者集団

   
 
用語集TOP

整数(integer)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
あ-お か-こ さ-そ た-と な-の
は-ほ ま-も や-よ ら-ろ わ-ん

数学、哲学、工学を横断する事典です。よろしければ活用してください。 ゲーム, アクション,シューティング,シミュレーション,リアルタイム, 計量経済学,計量心理学, コンピュータ,用語集,計算機科学用語集,コンピュータ用語集, 3DCG, グラフィックス,ゲームグラフィックス,美少女, 光反射,鏡面反射,拡散反射,屈折,散乱,異方性反射,影, シェーディング,レンダリング,透視変換, 発光,爆発,爆炎,煙, 物理, 人物,表情,表現,運動,力学,流体, 計算幾何学, グラフ,アフィン変換,アフィン写像,凸包,超平面,3D,3Dの数理, コンピュータサイエンス,コンピュータ, 計算機科学, チューリングマシン,チューリング機械,線形有界オートマトン,プッシュダウンオートマトン,有限オートマトン, オートマトン,状態遷移,遷移関数,対角線論法,文字列,記号, FA,NFA,PDA,NPDA,LBA,NLBA,TM, 計算量,P,NP,PSPACE,NP完全,NP困難,P完全,PSPACE完全,PP,APX,APX完全, 確率チューリング機械,確率オートマトン, 音声, 音階,音量,音律,和音,和声,無限上昇音,MIDI, 色彩, 表色系,顕色系,混色系,RGB,CMY,YCbCr,YUV,YIQ,CIE,L*a*b*, 符号, 圧縮,符号化,情報源符号化, 符号,ブロック符号,ストリーム符号,符号理論, 離散数学, 集合,写像,関数,全単写,単写,全写,対応関係,関係,反射,反射推移閉包, 代数系, 群,環,体,モノイド,半群,準同型写像,同型写像, 形式言語, 言語,正則言語,文脈自由言語,文脈依存言語,確率言語, 文法,正則文法,文脈自由文法,文脈依存文法,確率文脈自由言語, 文字,文字列, 3型言語,2型言語,1型言語,0型言語, 信号処理, 変換,フィルタ,信号処理,DFT,DCT,DST,FFT,Wavelet,フーリエ変換, 離散,コサイン変換,サイン変換,ウェーブレット, 基礎数学, 数学,応用数学,基礎数学,フィボナッチ数列, 解析学, 位相空間,線形空間,距離空間,ベクトル空間,vector,バナッハ空間,Banach,ヒルベルト空間,Hilbert,ユークリッド空間,Euclid, ノルム,内積,可算濃度,非可算濃度, 情報理論, 情報源,情報量,エントロピー,相互情報量,記号,記号列, 複雑系, カオス,フラクタル,フラクタル幾何学,カオス写像, インターネット, セキュリティ,HTTP,SMTP,FTP,プロトコル, その他理論,理論, 紅茶,自転車通勤,備忘録, 暗号, モンゴメリ演算,高速計算法,素因数分解,離散対数問題, 暗号,ブロック暗号,ストリーム暗号,楕円暗号, 乱数,乱数生成,共通鍵暗号,公開鍵暗号,公開鍵署名,鍵共有,鍵交換, 線形攻撃,差分攻撃,補間攻撃,スライド攻撃,量子暗号, 依頼計算,ゼロ知識対話証明,ハッシュ,

AES,Rijndael,RSA,ElGamal,Twofish,Serpent,

RC6,MARS,CAST,IDEA,GOST,

MQV,DH,EC-DH,EC-ElGamal,

終了,

フィリピンパブ
アミューズメント企画はお任せ
資産運用はお任せ
メール お問い合わせ お問い合わせ メール メール メール メール メール メール