第6回：■ 整数

第6回：■ 整数

■ 型

型(type)：データの種類のこと

julia> typeof(1)
Int64

julia> typeof(1.0)
Float64
julia> typeof(true)
Bool

julia> typeof(false)
Bool

■ 整数

Integers

既定の整数型は、Int64 であり、 64桁 (64bit, binary digit)の2進数である。

負の数 $-n$ を $2^{64}-n$ で表す「2の補数」方式を用いて、 正負の数を表す「符号付整数」である。

Int64 で表される最大の数は $2^{63}-1$ である。 また、最小の数（絶対値が最大な負の数)は $-2^{63}$ である。 これらの値は、 関数 typemax(Int64),typemin(Int64) で、それぞれ求められる。

julia> 2^63-1
9223372036854775807

julia> typemax(Int64)
9223372036854775807

julia> typemin(Int64)
-9223372036854775808
Note

2の補数を求める方法が知られていれば、 減算は、引く数の「2の補数」を求め、加算すればよい。 実は、2の補数は簡単に求められる。

2の補数では、2進数の最上位の桁が、符号に相当する。 すなわち、負の数では、 最上位の桁 (Most-Significant Bit, MSB)は 1、 正の数または0では、MSBは 0 になる。

■ 整数同士の加減乗算

整数同士の加減算は、2の補数として行われる。 typemin(Int64)から typemin(Int64) までの範囲を超えても、 例外は発生しない。

Overflow behavior

julia> typemax(Int64)+1
-9223372036854775808

julia> typemax(Int64)+2
-9223372036854775807

julia> typemin(Int64)-1
9223372036854775807

julia> typemin(Int64)-2
9223372036854775806

julia> typemax(Int64)+typemax(Int64)
-2

julia> typemax(Int64)*2
-2

julia> typemax(Int64)*4
-4

▼▶︎ 整数の2進数による表現。

関数 bits(x) は、数 x の2進数表現を文字列として返す。

julia> bits(0)
"0000000000000000000000000000000000000000000000000000000000000000"

julia> bits(1)
"0000000000000000000000000000000000000000000000000000000000000001"

julia> bits(2)
"0000000000000000000000000000000000000000000000000000000000000010"

julia> bits(-1)
"1111111111111111111111111111111111111111111111111111111111111111"

julia> bits(-2)
"1111111111111111111111111111111111111111111111111111111111111110"

julia> bits(typemax(Int64))
"0111111111111111111111111111111111111111111111111111111111111111"

julia> bits(typemin(Int64))
"1000000000000000000000000000000000000000000000000000000000000000"

上の例で、以下の理由を説明できただろうか？

typemax(Int64)+1 == typemin(Int64)

typemax(Int64)+typemax(Int64) == -2

typemax(Int64)*2 == -2

2進数に 2 を乗じることは、左に一つ分ずらすこと(左シフト 1bit)と同じである。

■ 整数同士の除算

整数同士の割り算（除算）の結果(商 quotient)は、小数(浮動小数点数)になる。

julia> 1 / 2
0.5

余り (剰余)を求めたい場合は、■ 残余 rem と整商 div を参照せよ。

■ 整数と浮動小数点数との四則演算

整数と小数を四則演算すると、小数になる。

julia> 1 + 2
3

julia> 1 + 2.0
3.0

julia> 1 * 2
2

julia> 1 * 2.0
2.0

■ 浮動小数点数から整数への変換

浮動小数点数を整数に変換するには、Int64(x)を用いる。 ただし、$x$が小数部を含むと例外がでる（エラーとなる）ので、 小数部を $0$に変換する必要がある。

この際、床関数が用いられる。　参考→ ■ 床関数・天井関数

julia> Int64(1.0)
1

julia> Int64(1.1)  # エラー
ERROR: InexactError()

julia> Int64(floor(1.1))
1

■ 残余 rem と整商 div

正の整数 $x > 0$ を、正の整数 $d > 0$ で割った結果、 整数の商 $q$ と余り $r$ が得られたとき、

\[x=qd+r\]

が成り立つ。

割られる数 $x$ を被除数 (divdend)、割る数 $d$ を除数 (divisor)という。

整数の商 $q$ を、整商(integral quotient)、 余り $r$ を残余 (remainder)という。 残余は、$d$ を超えない、すなわち、$0 \le r \lt d$ である。

関数 rem(x,d) は、$x$を$d$で割ったときの残余を返す。 関数 rem の代わりに、% 演算子を用いて x % d と書いてもよい。

julia> rem(15,4)
3

julia> 15 % 4
3

関数 div(x,d) は、$x$を$d$で割ったときの整商を返す。

julia> div(15,4)
3

整数 0から 7までを、3 で割った整商と残余 (divとremの計算結果) をプロットしよう。

using PyPlot
xs=0:7
d=3
plot(xs,rem.(xs,d), "ro", label="rem(x,"*string(d)*")")
plot(xs,div.(xs,d), "b.", label="div(x,"*string(d)*")")

xlim(-0.2,6.2)
ylim(-0.2,3.2)
xlabel("x")
legend()

for x=0:7
  axvline(x, color="k", lw=0.5)
end

for y=0:3
  axhline(y, color="k", lw=0.5)
end

plt[:axes]()[:set_aspect]("equal")

◀︎ 練習：硬貨への分割

日本では、小額の取引に、

の6種類の硬貨がよく用いられる。

金額が与えられたときに、6種類の硬貨が各々何枚必要か計算せよ。 ただし、高額の硬貨を優先して用いるものとする。

▶︎ ユークリッドの互除法

2 つの自然数 $a$, $b$ ($a \ge b$) について、 $a$ の $b$ による残差を $r$ とすると、 $a$ と $b$ との最大公約数 (greatest common divisor, gcd)は $b$ と $r$ との最大公約数に等しいという性質が成り立つ。 この性質を利用して、$b$ を $r$ で割った残差、 除数 $r$ をその剰余で割った残差、 と残差を求める計算を逐次繰り返すと、 残差が $0$ になった時の除数が $a$ と $b$ との最大公約数となる。

julia> a=1071
1071

julia> b=1029
1029

julia> @show a,b
(a, b) = (1071, 1029)
(1071, 1029)

julia> while b != 0
         t = a
         b = rem(a, b)
         a = t
         @show a,b
       end
(a, b) = (1071, 42)
(a, b) = (1071, 21)
(a, b) = (1071, 0)

julia> println( "gcd="*string(a))
gcd=1071

3355と2379の最大公約数を求めてみよう。

julia> a=3355
3355

julia> b=2379
2379

julia> @show a,b
(a, b) = (3355, 2379)
(3355, 2379)

julia> while b != 0
         t = a
         b = rem(a, b)
         a = t
         @show a,b
       end
(a, b) = (3355, 976)
(a, b) = (3355, 427)
(a, b) = (3355, 366)
(a, b) = (3355, 61)
(a, b) = (3355, 0)

julia> println( "gcd="*string(a))
gcd=3355

■ 一般の残余 rem と整商 div

正の整数 $x$を 正の整数 $d$で割ったときの 「商」 $q$ と「余り」 $r$ の関係

\[x=qd+r\]

は、 被除数 $x$ や除数 $d$ が、小数や負の数の場合に拡張できる。 ここで、「商」$q$ は整数であり、 「余り」$r$ の絶対値は、除数 $d$ の絶対値を超えないものとする。

\[0 \le \left\vert{r}\right\vert \lt \left\vert{d}\right\vert\]

さて、被除数 $x$ や除数 $d$ が負の数の場合、 「商」$q$ と「余り」 $r$ の取るべき値について、複数の考え方がある。

残差 remは、被除数 $x$ と同じ符号の「余り」を返す。 すなわち、被除数 $x$ が負なら、残差$r$　は $-|d| \lt r \le 0$

の範囲になる。 対応する「商」は 整商 div で求められる。

以下では、$-6$ から$6$ までの数(被除数)を、$3$ (正の除数)で割ったときの 残余と整商をプロットする。 被除数が負のとき、$−3 \lt r \le 0$ となることを観察せよ。

using PyPlot
xs=-6.8:0.2:6.8
d=3
plot(xs,rem.(xs,d), "ro", label="rem(x,"*string(d)*")")
plot(xs,div.(xs,d), "b.", label="div(x,"*string(d)*")")

xlim(-6.2,6.2)
ylim(-3.2,3.2)
xlabel("x")
legend()
plt[:axes]()[:set_aspect]("equal")

for x=-7:7
  axvline(x, color="k", lw=0.5)
end

for y=-3:3
  axhline(y, color="k", lw=0.5)
end

今度は、被除数の範囲は変えずに、$-3$ (負の除数)で割ったときの 残余と整商をプロットしよう。

using PyPlot
xs=-6.8:0.2:6.8
d=-3
plot(xs,rem.(xs,d), "ro", label="rem(x,"*string(d)*")")
plot(xs,div.(xs,d), "b.", label="div(x,"*string(d)*")")
xlim(-6.2,6.2)
ylim(-3.2,3.2)

xlabel("x")
legend()
plt[:axes]()[:set_aspect]("equal")

for x=-7:7
  axvline(x, color="k", lw=0.5)
end

for y=-3:3
  axhline(y, color="k", lw=0.5)
end

上の二つのグラフを比較すると、 残差 rem(x,3) と rem(x,-3)　が一致することが観察される。また、 整商 div(x,3) と div(x,-3)　は、互いに符号が逆である。

◀︎ 練習：切り捨て

正の数 x を

数を切り捨てるには、どうすればよいか？

プログラムを書いて、実行してみよ。

◀︎ 練習：四捨五入

正の数 x を

数を四捨五入するには、どうしたらよいか？

プログラムを書いて、実行してみよ。

■ 剰余 mod と、商の床 fld

「商」 $q$ と「余り」 $r$ の一般の関係

\[\begin{gather} x=qd+r$, \\ 0 \le \left\vert{r}\right\vert \lt　\left\vert{d}\right\vert \end{gather}\]

について、別の考え方を示す。

剰余 (modulo)は、 除数 $d$と同じ符号の「余り」$r$ である。 剰余関数 mod(x,d) は、この「余り」$r$を返す。 対応する「商」$q$は、関数 fld で求められる。

被除数が非負： $x \ge 0$、かつ、 除数が正: $d \gt 0$　なら、 残差 rem と剰余 mod は一致する。

被除数が負： $x < 0$ の場合も、剰余は非負である。

Note

被除数と除数の両方とも正なら、残差 rem と剰余 mod は一致する。この場合、少し計算コストが小さい残差 rem が好まれる。

では、$-6$ から $6$ までの数(被除数)を、$3$ (正の除数)で割ったときの剰余と「商」をプロットしよう。

using PyPlot
xs=-6.8:0.2:6.8
d=3
plot(xs,mod.(xs,d), "ro", label="mod(x,"*string(d)*")")
plot(xs,fld.(xs,d), "b.", label="fld(x,"*string(d)*")")

xlim(-6.2,6.2)
ylim(-3.2,3.2)
xlabel("x")
legend()
plt[:axes]()[:set_aspect]("equal")

for x=-7:7
  axvline(x, color="k", lw=0.5)
end

for y=-3:3
  axhline(y, color="k", lw=0.5)
end

実は、関数 fld(x,d) は、floor(x/d) と同じ値であり、「商の床」 floored division ともいう。 すなわち、$\dfrac{x}{d}$ 以下の最大の整数である。 参照： ■ 床関数・天井関数

上の例で、「商の床」をプロットしよう。 関数 fldと同じ結果が得られることが観測できる。

using PyPlot
xs=-6.8:0.2:6.8
d=3
qs=floor.(xs/d)
rs=xs-qs*d
plot(xs, rs, "ro", label="remainder divided by "*string(d))
plot(xs, qs, "b.",  label="quotient divided by "*string(d))

xlim(-6.2,6.2)
ylim(-3.2,3.2)
xlabel("x")
legend()
plt[:axes]()[:set_aspect]("equal")

for y=-3:3
  axvline(y, color="k", lw=0.5)
end

for x=-7:7
  axhline(x, color="k", lw=0.5)
end

今度は、被除数の範囲は変えずに、$-3$ (負の除数)で割ったときの剰余と「商」をプロットしよう。

using PyPlot
xs=-6.8:0.2:6.8
d=-3
plot(xs,mod.(xs,d), "ro", label="mod(x,"*string(d)*")")
plot(xs,fld.(xs,d), "b.", label="fld(x,"*string(d)*")")
xlim(-6.2,6.2)
ylim(-3.2,3.2)
xlabel("x")
legend()
plt[:axes]()[:set_aspect]("equal")

for x=-7:7
  axvline(x, color="k", lw=0.5)
end

for y=-3:3
  axhline(y, color="k", lw=0.5)
end

負の数 $-3$ で割ったとき、剰余 $r$ の範囲は $-3 \lt r \le 0$ であることが観察できる。

◀ 練習：「商の床」

上の例で、「商の床」floor( x/-3 )をプロットせよ、 関数 fld(x,-3) と結果が等しいことを確認せよ。

▶ 2piで割った剰余

関数 mod2pi(x) は、mod(x,2*pi) と同じである。 すなわち、$x$ を $2\pi$ で割った剰余を返す。

using PyPlot
is=-24:24
xs=is/3
plot(xs,mod2pi.(xs), ".")
xlabel("x")
ylabel("mod2pi(x)")
axhline(0, color="k", lw=0.5)
axhline(2*pi, color="k",lw=0.5)
plt[:axes]()[:set_aspect]("equal")

■ 整数 0による除算

除数が0であっても、「余り」を計算しない除算では、例外は発生しない。→ ■ 0による除算

しかし、「余り」を計算する rem, mod, div, mod などにおいて、除数が 0 であると例外(exception)を発生する。 例外が発生すると、プログラムの実行は、そこで中断する。

除算例外 Division erros

julia> div(3,0)
ERROR: DivideError: integer division error

julia> rem(3,0)
ERROR: DivideError: integer division error
Note

例外が発生した場合、それを救済する手続きを書いて、プログラムを続行させることもできる。だが、この文書の範囲を超えるので、説明しない。 → Exception Handling

▶ 床関数・天井関数の型を整数型にする

■ 床関数・天井関数 floor(x) および ceil の結果の型は、 引数(ひきすう) x の型に一致する。

julia> floor(2) # => 整数
2

julia> floor(0.2) # => 小数（浮動小数点数)
0.0


julia> ceil(2) # => 整数
2

julia> ceil(0.2) # => 小数（浮動小数点数)
1.0

結果の型を整数にするには、引数xの前に、型の名前 Int64をつける。

julia> floor(Int64, 2)
2

julia> floor(Int64, 0.2)
0


julia> ceil(Int64, 2)
2

julia> ceil(Int64, 0.2)
1

★ 今回のまとめ