[b]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/b][br]たとえば、１/7と1÷7=0.142857142857.........も同じ数のちがう表示です。[br]分数を使うことで、１０進数表示の無限展開をかかなくてよくなります。[br][color=#0000ff][b]分数1/7は式[/b][/color]１÷７[b][color=#0000ff]を数に格上げ[/color][/b]する約束の数とも言えますね。[br][br]同じように、式２×２×２×２×２×２×２×２×２×２を指数[b][power, index][/b]記号で２[sup]10[/sup]の数としてかけます。[br][color=#0000ff][b]２[sup]10[/sup][/b][/color]も、同じ数を何個もかけ算する[color=#0000ff][b]式を数に格上げ[/b][/color]する約束の数とも言えるでしょう。[br][br]べき、指数[b][power, index][/b]の法則を使うとさらに便利になります。[br]・[b]指数[/b]が合成数なら、何乗の何乗に分解できます。[br]　aのpq乗はaのp乗のq乗、または、aのq乗のp乗に等しい。つまり[math]a^{pq}=\left(a^p\right)^q[/math][br][b][color=#0000ff] だから、(a[/color][sup]p[/sup][color=#0000ff])[/color][sup]2[/sup][color=#0000ff]=a[/color][sup]2p [/sup][color=#0000ff] 、2乗したかったら指数を2倍すればよいのですね。[br]　反対にルートしたかったら指数を半分にすればよいですね。[br][/color]　（例）2[sup]8[/sup]=(2[sup]4[/sup])[sup]2[/sup]=16[sup]2[/sup]=256という計算ができます。[br][sup][br][/sup][color=#0000ff]・指数[/color][/b]が２以上の数なら、和分解した何乗と何乗の積にできるというとこです。[br]　aのp+q乗はaのp乗とaのq乗の積に等しい。　[math]a^{p+q}=a^p\cdot a^q[/math][br]　だから、aをN乗倍したかったら、Nを和分解して、小さい乗数に還元することができるね。[br][b]　（例）2[sup]100[/sup]=2[sup]32+32+32+2[/sup]=2[sup]32[/sup]･2[b][sup]32[/sup][/b][b]･[/b][b]2[b][sup]32[/sup][/b][b]･[/b][/b]2[sup]2[/sup]というように、式を再表現できます。[br][br][size=150][color=#0000ff][u]・指数法則のいいところは、積も和も分解の自由度が高いため、[br]　べき計算に自由度が生まれるということです。[br][/u][/color][/size][/b][br]

２進数は指数に関係があります。[br]たとえば、３けたの整数を作るときに使える数字を０か１に制限してみましょう。[br]すると、できる整数は０００、つまり０から１１１までの2[sup]3[/sup]個です。[br]このように０，１の２つの数字しか使わないのが２進数です。[br]また、１０進数は１０で１つ上の位の１に上がりますが、２進数は２で１つ上の位の１に上がります。[br]だから、１の次の２は「１０」，２の次の３は「１１」、３の次の４は「１００」と書きます。[br]こうやって見ると、[br]１０進数では右から順に１，１０，１００，…と位が１０倍になりますが、[br]２進数では右から順に１，２，４，８、…と位が２倍になりますね。[br][b][size=150]＜10進数を２進数にする＞[/size][/b][br]１０進数を２進数に直す方法は、[color=#0000ff][b][size=150]数を２で割った商を２でわり続けます[/size][/b][/color]。[br]そのとき、[b][size=150][color=#0000ff]２で割った余りを右から順に並べる[/color][/size][/b]という方法です。[br]１００は２で７回割り算できるので、[br]余りが７回出ますね。[br]だから、７けたになります。[br]１００÷２＝５０余り０[br]５０÷２＝２５余り０[br]２５÷２＝１２余り１[br]１２÷２＝６余り０[br]６÷２＝３余り０[br]３÷２＝１余り１[br]１÷２＝０余り１[br]余りを右から順に並べると、１１００１００[br]です。これが、１００の２進化した数です。[br][br][b][size=150]＜２進数を10進数に戻す＞[/size][/b][br]2進数を10進数に戻すには、１のある位のもつ大きさが鍵です。[br][color=#0000ff][b][size=150]右から順に、２進数の位は１，２，４，８, 16, 32, 64 でした。[br][/size][/b][/color]１１００１００[br]右から７けた、６けた、３けたが１なので、その位だけを加えましょう。[br]64＋32＋4＝100に戻りますね。[br] [br][b][color=#0000ff]#[IN]julia[br]#=================[br][/color]string(100,base=2)[br][color=#0000ff]#=================[br][/color][color=#0000ff][OUT][br][/color][b]"1100100"[br][/b][b]#[IN]julia[br]#=================[br][/b]Int(0b1100100)[br][b]#=================[br][OUT][br][/b]100[b]#[IN]python[br]#=================[br][/b]bin(100)[br][b]#=================[br][OUT][br][/b]'0b1100100'[br][/b][br][b][b]#[IN]python[br]#=================[br][/b]int(0b1100100)[br][b]#=================[br][/b][/b][b][b][OUT][br][/b]100[br][/b][br][b][size=150]＜指数の２進化＞[/size][/b][br]２の１００乗したいとします。[br]２を１００回かけなくても大丈夫です。[br]指数法則から２[sup]100[/sup]＝２[sup]64+32+4[/sup]=２[sup]64[/sup]・2[sup]32[/sup]・2[sup]4[/sup]となりますね。[br]２[sup]4[/sup]=(2[sup]2[/sup])[sup]2[/sup]=4[sup]2[/sup]=16。[br]２[sup]8[/sup]=(2[sup]4[/sup])2=16[sup]2[/sup]=256[br]2[sup]16[/sup]=(2[sup]8[/sup])[sup]2[/sup]=256[sup]2[/sup]=65536[br]2[sup]32[/sup]=(2[sup]16[/sup])[sup]2[/sup]=(65536)[sup]2[/sup]=4294967296[br]２[sup]64[/sup]=(2[sup]32[/sup])[sup]2[/sup]=4294967296・4294967296[br]２[sup]100[/sup]＝２[sup]64+32+4[/sup]=２[sup]64[/sup]・2[sup]32[/sup]・2[sup]4[/sup]＝4294967296・4294967296・4294967296・16[br]=1267650600228229401496703205376[br]桁は大きいですが、[br][color=#0000ff][b][size=150]かけ算そのものの回数は大幅に減らすことができました[/size][/b][/color]。[br]指数が２進数の位になるように、指数を和分解することを[color=#0000ff][b]２進化とか２進展開とか、くり返し2乗法[/b][/color][br]などといいますよ。

＜くり返し2乗法のコード化＞[br][br]2^100を求めることは、2^100=２[sup]64[/sup]・2[sup]32[/sup]・2[sup]4[/sup]と変形しても同じことです。[br]これはとても便利な考え方なので、関数を作ってみましょう。[br][br][color=#0000ff]#[IN]Python[br]#============================[br]def Power(a, k):[br] b = 1[br] for i in reversed(bin(k)[2:]):[br] if i == '1':[br] b = a * b[br] a = a**2[br] return b[br]Power(2,100)[br]#============================[br]#[OUT][br]1267650600228229401496703205376[br][/color]2をa, 100をkとしてみましょう。[br]bin(k)[2:]によって100を2進数にした文字列'[b]1100100'だけを取り出し,reversedでひっくり返します。[br][/b]左から１の位が始まるので、’0010011'の文字列の文字を左から1個ずつ取り出したものが iです。[br]aは2乗を繰り返すことで、aの指数は2倍をくり返し、2進数の位に対応した数値を提供します。[br]forループが回るたびにaは上書きされますが、順に記録する次のリストを作ることができます。[br][a,a[sup]2[/sup],a[sup]4[/sup],a[sup]8[/sup],a[sup]16[/sup],a[sup]32[/sup],a[sup]64[/sup]][br]取り出した文字i が '１' になるたびに、b=1の初期値にa[sup]4[/sup],a[sup]32[/sup],a[sup]64[/sup]をかけるのがif文の役目です。[br]このaは2だから、2の100乗が計算されるわけです。[br][br][color=#0000ff][b][u][size=150]質問：解説がなくてもわかるよう順次的ではなく宣言的に書き換えるとどうなるでしょう。[br][/size][/u][/b][br]#[IN]Python[br]#============================[br][/color][color=#0000ff]from math import prod[br]def Power(a, k):[br] binRev=list( map(lambda x: int(x), list(reversed(bin(k)[2:]))))[br] index_a = [2**x for x in range(0,len(binRev))][br] base_a = [a**i for i in index_a] [br] sekiwa= [x**y for x,y in zip(base_a,binRev)][br][/color] print("index_a=",index_a)[br] print("base_a=",base_a)[br] print("sekiwa=",sekiwa)[br][color=#0000ff] return prod(sekiwa)[br]Power(2,100)[br][/color][color=#0000ff]#============================[br]#[OUT][br][/color]index_a= [1, 2, 4, 8, 16, 32, 64][br]base_a= [2, 4, 16, 256, 65536, 4294967296, 18446744073709551616][br]sekiwa= [1, 1, 16, 1, 1, 4294967296, 18446744073709551616][br]1267650600228229401496703205376[br][br]宣言型にすると、Juliaに移植しやすくなるね。リスト要素の積関数productが[br]標準であるのが便利ですね。[br]#[IN]Julia[br]#============================[br][color=#0000ff]function Power(a, k)[br] binRev = map(x -> parse(Int, x), split(reverse(string(100,base=2)),""))[br] index_a = [2^x for x in 0:length(binRev)][br] base_a = [BigInt(a)^i for i in index_a] [br] sekiwa= [BigInt(x)^y for (x,y) in zip(base_a,binRev)][br][/color] println("index_a=",index_a)[br] println("base_a=",base_a)[br] println("sekiwa=",sekiwa)[br] [color=#0000ff] return prod(sekiwa)[br]end[/color][br]Power(2,100)[br][color=#0000ff]#============================[br]#[OUT][br][/color]index_a= [1, 2, 4, 8, 16, 32, 64][br]base_a= [2, 4, 16, 256, 65536, 4294967296, 18446744073709551616][br]sekiwa= [1, 1, 16, 1, 1, 4294967296, 18446744073709551616][br]1267650600228229401496703205376[br][br]宣言型のコードにできると、geogebraに移しやすくなるね。[br][color=#0000ff][b][u][size=150]質問：geogebaraでもくりかえし2乗法を実装できますか。[/size][/u][/b][/color]

くり返し２乗法を剰余にからめると、[br]さらに効率的な計算ができる。[br]剰余は最後に割り算せずに、そのつど計算することで、[br]ケタの爆発が防げるからだ。[br][color=#0000ff][b]#[INT]Python[br]#=================================================[br]def PowerMod(a, k, m):[br] b = 1[br] for i in reversed(bin(k)[2:]):[br] if i == '1':[br] b = a * b % m[br] a = a**2 % m[br] return b[br]print("5^2 mod 20 =", PowerMod(5,2,20))[br]print("2^(2^100) mod 5801 =", PowerMod(2, 2**100, 5801))[br]#=================================================[br][OUT][br][/b][/color]5^2 mod 20 = 5[br]2^(2^100) mod 5801 = 2162[br][br]実はpythonのpow関数(a,k,m)は３番目の引数mが法の数です。だから、[br]わざわざ実装しなくてもかまいません。[br][b]#[INT]Python[br]#=================================================[/b][br]print("5^2 mod 20 =", pow(5,2,20))[br]print("2^(2^100) mod 5801 =", pow(2, 2**100, 5801))[br][b]#=================================================[br][OUT][br][/b]5^2 mod 20 = 5[br]2^(2^100) mod 5801 = 2162[br][br]juliaにも対応する関数がありますね。powermod(a,k,m)です。[br][b]#[INT]julia[br]#=================================================[/b][br]println("5^2 mod 20 =", powermod(5,2,20))[br]println("2^(2^100) mod 5801 =", powermod(2, 2^100, 5801))[br]println("2^100 mod 23 =", powermod(2,100,23))[br]println("100^1000 mod 23 =", powermod(100, 1000, 23))[br][b]#=================================================[br][OUT][br][/b]5^2 mod 20 = 5[br]2^(2^100) mod 5801 = 2162[br]2^100 mod 23 =2[br]1000^1000 mod 23 =3