![見出し画像](https://assets.st-note.com/production/uploads/images/60566877/rectangle_large_type_2_7117c234b4f84510d04483ef98edcbd0.png?width=1200)
#としじのPS その10~発展問題2:冪剰余 c:=b^e mod m~
#としじのPS その10~発展問題2~
早くも趣味に走ってますね、さっすが俺w
大きな数から余りを求めようとすると、PSは見当違いの数を返してくるようです。ここはエラーでも吐いてほしかったな、まあいいや。
例えば46の46乗を47で割ったときの余りを求めたいとします。
この答えは1になるのですが、僕の環境ではPSは5を返してきました。
$a = [math]::Pow(46,46)
$a % 47
細かいことはちょっとわからないのですが、ケタ落ちしてるんでしょうね。Twitterでそれを回避するアルゴリズムを教わったので試してみました!
cls; cd C:\PowerShell
# aのn乗をmで割った余りを返却
function LargeMod($a,$n,$m){
$ret=$a%$m
if($n-ge 2){
2..$n|%{$ret=($ret*$a)%$m}
}
$ret
}
(LargeMod 46 46 47)
(LargeMod 28 28 47)
(LargeMod 30 30 47)
(LargeMod 37 37 47)
(LargeMod 31 31 47)
(LargeMod 40 40 47)
(LargeMod 18 18 47)
(LargeMod -11 11 47) +47
(LargeMod -41 41 47) +47
-(LargeMod -42 42 47) +47
(LargeMod 43 43 47)
(LargeMod 27 27 47)
美しいですね!
買っちまった😆✨ pic.twitter.com/A6yuMXWfDK
— としじ🎤VBAer (@toshi81350036) September 5, 2021
ついでにVBAでも書いてみました♪
' aのn乗をmで割った余りを返却 '
Function LargeMod(a, n, m): Dim i, ret
ret = a Mod m
If n >= 2 Then
For i = 2 To n
ret = (ret * a) Mod m
Next
End If
LargeMod = ret
End Function
Sub Main()
Debug.Print (LargeMod(46, 46, 47))
Debug.Print (LargeMod(28, 28, 47))
Debug.Print (LargeMod(30, 30, 47))
Debug.Print (LargeMod(37, 37, 47))
Debug.Print (LargeMod(31, 31, 47))
Debug.Print (LargeMod(40, 40, 47))
Debug.Print (LargeMod(18, 18, 47))
Debug.Print (LargeMod(-11, 11, 47) + 47)
Debug.Print (LargeMod(-41, 41, 47) + 47)
Debug.Print (LargeMod(-42, 42, 47) - 47) * -1
Debug.Print (LargeMod(43, 43, 47))
Debug.Print (LargeMod(27, 27, 47))
End Sub
さらにPythonのPowを再現してみた、中身のロジックについては再現しているのかどうかはわからないけども←
Function Pow(b, e, Optional m): Dim i, ret
If IsMissing(m) Then
Pow = b ^ e
Exit Function
End If
ret = b Mod m
If e >= 2 Then
For i = 2 To e
ret = (ret * b) Mod m
Next
End If
Pow = ret
End Function
あれ、PSについて語るハズでは・・・ま、いっかw
やっぱりよくない、PSでも書きましょうw
cls; cd C:\PowerShell
function Pow($b, $e, $m = 0){
if($m -eq 0){return [math]::Pow($b, $e)}
$ret = $b % $m
if($e -ge 2){
2..$e | % {$ret = ($ret * $b) % $m}
}
return $ret
}
Pow 46 46
Pow 46 46 47
このデータならマイナスを考慮せずともちゃんと出るとのこと・・・
どうやってこんなの見つけてきてるんでしょうね、不思議😇
この記事が気に入ったらサポートをしてみませんか?