2乗・2進 is magic
１．べき乗(Power)のパワー(Power)
このワークシートはMath by Codeの一部です。
たとえば、１/7と1÷7=0.142857142857.........も同じ数のちがう表示です。
分数を使うことで、１０進数表示の無限展開をかかなくてよくなります。
分数1/7は式１÷７を数に格上げする約束の数とも言えますね。
同じように、式２×２×２×２×２×２×２×２×２×２を指数[power, index]記号で２10の数としてかけます。
２10も、同じ数を何個もかけ算する式を数に格上げする約束の数とも言えるでしょう。
べき、指数[power, index]の法則を使うとさらに便利になります。
・指数が合成数なら、何乗の何乗に分解できます。
aのpq乗はaのp乗のq乗、または、aのq乗のp乗に等しい。つまり
だから、(ap)2=a2p 、2乗したかったら指数を2倍すればよいのですね。
反対にルートしたかったら指数を半分にすればよいですね。
（例）28=(24)2=162=256という計算ができます。
・指数が２以上の数なら、和分解した何乗と何乗の積にできるというとこです。
aのp+q乗はaのp乗とaのq乗の積に等しい。
だから、aをN乗倍したかったら、Nを和分解して、小さい乗数に還元することができるね。
（例）2100=232+32+32+2=232･232･232･22というように、式を再表現できます。
・指数法則のいいところは、積も和も分解の自由度が高いため、
べき計算に自由度が生まれるということです。
２．２進化
２進数は指数に関係があります。
たとえば、３けたの整数を作るときに使える数字を０か１に制限してみましょう。
すると、できる整数は０００、つまり０から１１１までの23個です。
このように０，１の２つの数字しか使わないのが２進数です。
また、１０進数は１０で１つ上の位の１に上がりますが、２進数は２で１つ上の位の１に上がります。
だから、１の次の２は「１０」，２の次の３は「１１」、３の次の４は「１００」と書きます。
こうやって見ると、
１０進数では右から順に１，１０，１００，…と位が１０倍になりますが、
２進数では右から順に１，２，４，８、…と位が２倍になりますね。
＜10進数を２進数にする＞
１０進数を２進数に直す方法は、数を２で割った商を２でわり続けます。
そのとき、２で割った余りを右から順に並べるという方法です。
１００は２で７回割り算できるので、
余りが７回出ますね。
だから、７けたになります。
１００÷２＝５０余り０
５０÷２＝２５余り０
２５÷２＝１２余り１
１２÷２＝６余り０
６÷２＝３余り０
３÷２＝１余り１
１÷２＝０余り１
余りを右から順に並べると、１１００１００
です。これが、１００の２進化した数です。
＜２進数を10進数に戻す＞
2進数を10進数に戻すには、１のある位のもつ大きさが鍵です。
右から順に、２進数の位は１，２，４，８, 16, 32, 64 でした。
１１００１００
右から７けた、６けた、３けたが１なので、その位だけを加えましょう。
64＋32＋4＝100に戻りますね。
#[IN]julia
#=================
string(100,base=2)
#=================
[OUT]
"1100100"
#[IN]julia
#=================
Int(0b1100100)
#=================
[OUT]
100#[IN]python
#=================
bin(100)
#=================
[OUT]
'0b1100100'
#[IN]python
#=================
int(0b1100100)
#=================
[OUT]
100
＜指数の２進化＞
２の１００乗したいとします。
２を１００回かけなくても大丈夫です。
指数法則から２100＝２64+32+4=２64・232・24となりますね。
２4=(22)2=42=16。
２8=(24)2=162=256
216=(28)2=2562=65536
232=(216)2=(65536)2=4294967296
２64=(232)2=4294967296・4294967296
２100＝２64+32+4=２64・232・24＝4294967296・4294967296・4294967296・16
=1267650600228229401496703205376
桁は大きいですが、
かけ算そのものの回数は大幅に減らすことができました。
指数が２進数の位になるように、指数を和分解することを２進化とか２進展開とか、くり返し2乗法
などといいますよ。
１０進数を２進数にしよう
３．くりかえし2乗法
＜くり返し2乗法のコード化＞
2^100を求めることは、2^100=２64・232・24と変形しても同じことです。
これはとても便利な考え方なので、関数を作ってみましょう。
#[IN]Python
#============================
def Power(a, k):
b = 1
for i in reversed(bin(k)[2:]):
if i == '1':
b = a * b
a = a**2
return b
Power(2,100)
#============================
#[OUT]
1267650600228229401496703205376
2をa, 100をkとしてみましょう。
bin(k)[2:]によって100を2進数にした文字列'1100100'だけを取り出し,reversedでひっくり返します。
左から１の位が始まるので、’0010011'の文字列の文字を左から1個ずつ取り出したものが iです。
aは2乗を繰り返すことで、aの指数は2倍をくり返し、2進数の位に対応した数値を提供します。
forループが回るたびにaは上書きされますが、順に記録する次のリストを作ることができます。
[a,a2,a4,a8,a16,a32,a64]
取り出した文字i が '１' になるたびに、b=1の初期値にa4,a32,a64をかけるのがif文の役目です。
このaは2だから、2の100乗が計算されるわけです。
質問：解説がなくてもわかるよう順次的ではなく宣言的に書き換えるとどうなるでしょう。
#[IN]Python
#============================
from math import prod
def Power(a, k):
binRev=list( map(lambda x: int(x), list(reversed(bin(k)[2:]))))
index_a = [2**x for x in range(0,len(binRev))]
base_a = [a**i for i in index_a]
sekiwa= [x**y for x,y in zip(base_a,binRev)]
print("index_a=",index_a)
print("base_a=",base_a)
print("sekiwa=",sekiwa)
return prod(sekiwa)
Power(2,100)
#============================
#[OUT]
index_a= [1, 2, 4, 8, 16, 32, 64]
base_a= [2, 4, 16, 256, 65536, 4294967296, 18446744073709551616]
sekiwa= [1, 1, 16, 1, 1, 4294967296, 18446744073709551616]
1267650600228229401496703205376
宣言型にすると、Juliaに移植しやすくなるね。リスト要素の積関数productが
標準であるのが便利ですね。
#[IN]Julia
#============================
function Power(a, k)
binRev = map(x -> parse(Int, x), split(reverse(string(100,base=2)),""))
index_a = [2^x for x in 0:length(binRev)]
base_a = [BigInt(a)^i for i in index_a]
sekiwa= [BigInt(x)^y for (x,y) in zip(base_a,binRev)]
println("index_a=",index_a)
println("base_a=",base_a)
println("sekiwa=",sekiwa)
return prod(sekiwa)
end
Power(2,100)
#============================
#[OUT]
index_a= [1, 2, 4, 8, 16, 32, 64]
base_a= [2, 4, 16, 256, 65536, 4294967296, 18446744073709551616]
sekiwa= [1, 1, 16, 1, 1, 4294967296, 18446744073709551616]
1267650600228229401496703205376
宣言型のコードにできると、geogebraに移しやすくなるね。
質問：geogebaraでもくりかえし2乗法を実装できますか。
くりかえし2乗法
４．くり返し２乗法と剰余
くり返し２乗法を剰余にからめると、
さらに効率的な計算ができる。
剰余は最後に割り算せずに、そのつど計算することで、
ケタの爆発が防げるからだ。
#[INT]Python
#=================================================
def PowerMod(a, k, m):
b = 1
for i in reversed(bin(k)[2:]):
if i == '1':
b = a * b % m
a = a**2 % m
return b
print("5^2 mod 20 =", PowerMod(5,2,20))
print("2^(2^100) mod 5801 =", PowerMod(2, 2**100, 5801))
#=================================================
[OUT]
5^2 mod 20 = 5
2^(2^100) mod 5801 = 2162
実はpythonのpow関数(a,k,m)は３番目の引数mが法の数です。だから、
わざわざ実装しなくてもかまいません。
#[INT]Python
#=================================================
print("5^2 mod 20 =", pow(5,2,20))
print("2^(2^100) mod 5801 =", pow(2, 2**100, 5801))
#=================================================
[OUT]
5^2 mod 20 = 5
2^(2^100) mod 5801 = 2162
juliaにも対応する関数がありますね。powermod(a,k,m)です。
#[INT]julia
#=================================================
println("5^2 mod 20 =", powermod(5,2,20))
println("2^(2^100) mod 5801 =", powermod(2, 2^100, 5801))
println("2^100 mod 23 =", powermod(2,100,23))
println("100^1000 mod 23 =", powermod(100, 1000, 23))
#=================================================
[OUT]
5^2 mod 20 = 5
2^(2^100) mod 5801 = 2162
2^100 mod 23 =2
1000^1000 mod 23 =3