Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Unknown Evolution of the Built-in Function pow
Search
HayaoSuzuki
October 15, 2021
Technology
0
1.1k
Unknown Evolution of the Built-in Function pow
PyCon JP 2021
HayaoSuzuki
October 15, 2021
Tweet
Share
More Decks by HayaoSuzuki
See All by HayaoSuzuki
Tasting "Python Distilled"
hayaosuzuki
0
16
Let's implement useless Python objects
hayaosuzuki
0
1k
How to Write Robust Python Code
hayaosuzuki
5
3k
Python for Everyday
hayaosuzuki
1
1.4k
How to Use In-Memory Streams
hayaosuzuki
0
3.4k
Do you know cmath module?
hayaosuzuki
0
2.8k
Elementary Number Theory with Python
hayaosuzuki
1
3k
Django QuerySet "ARE" Patterns
hayaosuzuki
0
2.8k
A Modernization of Legacy Django Based Applications
hayaosuzuki
1
6.4k
Other Decks in Technology
See All in Technology
地理空間データ可視化・解析・活用ソリューション Pacific Spatial Solutions (PSS)
pacificspatialsolutions
0
330
EM完全に理解した と思ったけど、 やっぱり何も分からなかった話 / EM Night Fukuoka #1
hirutas
0
140
プロンプトエンジニアリングでがんばらない-Agentic Workflow へ-近藤憲児
kenjikondobai
6
1.1k
推しは推せるときに推せ! プロダクトにフィードバックしていこう
nakasho
0
440
IaCジェネレーターとBedrockで詳細設計書を生成してみた
tsukasa_ishimaru
4
850
データベース02: データベースの概念
trycycle
0
170
20分で完全に理解するGrafanaダッシュボード
hamadakoji
5
850
Azureの基本的な権限管理の勉強会
yhana
1
1.8k
Building Dashboards as a Hobby
egmc
0
340
開発パフォーマンスを最大化するための開発体制
ham0215
2
530
Python と Snowflake はズッ友だょ!~ Snowflake の Python 関連機能をふりかえる ~
__allllllllez__
2
140
[新卒向け研修資料] テスト文字列に「うんこ」と入れるな(2024年版)
infiniteloop_inc
4
17k
Featured
See All Featured
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
41
4.4k
Side Projects
sachag
451
41k
Atom: Resistance is Futile
akmur
260
25k
The Cult of Friendly URLs
andyhume
74
5.7k
Building Applications with DynamoDB
mza
88
5.6k
Principles of Awesome APIs and How to Build Them.
keavy
121
16k
Code Review Best Practice
trishagee
56
15k
Mobile First: as difficult as doing things right
swwweet
217
8.6k
How to Ace a Technical Interview
jacobian
273
22k
Building an army of robots
kneath
300
41k
Automating Front-end Workflow
addyosmani
1357
200k
For a Future-Friendly Web
brad_frost
172
9k
Transcript
ΈࠐΈؔ pow ͷΒΕ͟ΔਐԽ Unknown Evolution of the Built-in Function pow
Hayao Suzuki PyCon JP 2021 October 15, 2021
ൃදʹࡍͯ͠ GitHub › https://github.com/HayaoSuzuki/pyconjp2021 Twitter ϋογϡλά › #pyconjp #pyconjp_3 PyCon
JP 2021 Discord › #hayao-suzuki-ΈࠐΈؔ pow ͷΒΕ͟ΔਐԽ › #pyconjp_3 ʢ1 17:30ʙ18:15ʣ 2 / 33
Who am I ? ͓લ୭Α ໊લ Hayao Suzukiʢླɹॣʣ Twitter @CardinalXaro
ࣄ Software Developer @ BeProud Inc. › גࣜձࣾϏʔϓϥυ › IT ษڧձࢧԉαʔϏε connpass › ΦϯϥΠϯֶशαʔϏε PyQ › γεςϜ։ൃͷͨΊͷυΩϡϝϯταʔϏε Tracery 3 / 33
Who am I ? ༁ɾࠪಡٕͨ͠ज़ॻʢൈਮʣ › ೖ Python 3 ୈ
2 ൛ (O’Reilly Japan) › Effective Python ୈ 2 ൛ (O’Reilly Japan) › ػցֶशʹΑΔ࣮༻ΞϓϦέʔγϣϯߏங (O’Reilly Japan) › PyTorch ͱ fastai Ͱ͡ΊΔσΟʔϓϥʔχϯά (O’Reilly Japan) › ࣮ફ ࣌ܥྻղੳ (O’Reilly Japan) New! › ػցֶशσβΠϯύλʔϯ (O’Reilly Japan) New! https://xaro.hatenablog.jp/ ʹϦετ͕͋Γ·͢ɻ 4 / 33
Who am I ? ൃදϦετʢൈਮʣ › ϨΨγʔ Django ΞϓϦέʔγϣϯͷݱԽ (DjangoCongress
JP 2018) › SymPy ʹΑΔࣜॲཧ (PyCon JP 2018) › Python ͱָ͠Ήॳ (PyCon mini Hiroshima 2019) › ܅ cmath Λ͍ͬͯΔ͔ (PyCon mini Shizuoka 2020) › ΠϯϝϞϦʔετϦʔϜ׆༻ज़ (PyCon JP 2020) https://xaro.hatenablog.jp/ ʹϦετ͕͋Γ·͢ɻ 5 / 33
ࠓͷඪ ΈࠐΈؔ pow › pow ؔͷႈΛฦؔ͢ › Python ʹݶΒͣɺେͷݴޠʹ pow
͕ؔଘࡏ͢Δ Python 3.8 ͰػೳՃ › m Λ๏ͱ͢Δ༨ྨʹ͓͚Δ๏ٯݩ͕ܭࢉͰ͖Δ › Α͘Θ͔Βͳ͍୯ޠΛฒΔͳʂ 6 / 33
ࠓͷඪ ΈࠐΈؔ pow ͷΒΕ͟ΔਐԽ › Python 3.8 ͰՃ͞Εͨ pow ؔͷ৽ػೳΛཧղ͢Δ
› ʮ m Λ๏ͱ͢Δ༨ྨʹ͓͚ΔٯݩʯͷҙຯΛཧղ͢Δ › ʮ m Λ๏ͱ͢Δ༨ྨʹ͓͚ΔٯݩʯΛܭࢉ͢ΔΞϧΰ ϦζϜΛཧղ͢Δ 7 / 33
ࠓ·Ͱͷ pow ؔ Python 3.7 ·Ͱͷ pow ؔΛ෮श͠Α͏ 8 /
33
ͷႈ ఆٛ (ͷႈ) b ͱࣗવ n ʹରͯ͠ɺႈ bn Λ
bn ≜ n ݸ z }| { b ˆ b ˆ ´ ´ ´ ˆ b ͱఆٛ͢Δɻb Λఈɺn ΛࢦͱݺͿɻ ͷႈͷྫ 232 = 4294967296: 9 / 33
ͷႈ Python ʹ͓͚Δႈ ΈࠐΈؔ pow ·ͨ**ԋࢉࢠΛ͏ɻ ႈͷ࣮ߦྫ >>> pow(2, 32)
4294967296 >>> 2 ** 32 4294967296 10 / 33
ႈ༨ ఆٛ (ႈ༨) ࣗવͷఈ b ͱࣗવ n; m ʹରͯ͠ɺ bn
mod m Λ m Λ๏ͱ͢Δႈ༨ͱఆٛ͢Δɻ ႈ༨ͷྫ 232 mod 65535 = 1: 11 / 33
ႈ༨ Python ʹ͓͚Δႈ༨ › ΈࠐΈؔ pow ͰޮతʹܭࢉͰ͖Δɻ › **ԋࢉࢠ͓Αͼ%ԋࢉࢠͰܭࢉՄೳ͕ͩޮ͕ѱ͍ɻ ›
Python 1.5 ͔Βར༻Մೳʢint ܕͷൣғͳͲͷ੍ݶ ͋ͬͨʣ ɻ ႈ༨ͷ࣮ߦྫ >>> pow(2, 262144, 65535) 1 >>> (2 ** 262144) % 65535 1 12 / 33
ႈ༨ ͲΕ͚ͩޮత͔ >>> import timeit >>> timeit.timeit("pow(2, 262144, 65535)", number=1000)
0.0007324999999999693 >>> timeit.timeit("(2 ** 262144) % 65535", number=1000) 0.868453 ݁ՌΛ࣮ߦճͰׂΕฏۉ͕࣌ؒΘ͔Δɻ 13 / 33
ႈ༨ ԋࢉࢠͱؔʹ͓͚Δܭࢉ࣌ؒͷൺֱ 14 / 33
͜Ε͔Βͷ pow ؔ Python 3.8 ͔Βͷ pow ؔΛཧղ͢ΔͨΊʹ 15 /
33
ͷ߹ಉ ఆٛ (ͷ߹ಉ) a ͕ m Λ๏ͱͯ͠ b ͱ߹ಉͰ͋Δͱ
m ͕ a ` b ΛׂΓΔ ͜ͱΛ͍͍ɺ a ” b (mod m) ͱද͢ɻ ͷ߹ಉͷྫ 47 ” 35 (mod 6) 47 ` 35 = 12 6 ͰׂΓΕΔɻ 16 / 33
༨ྨ ఆٛ (༨ྨ) ू߹ Z ͱ m Λ๏ͱ͢Δ߹ಉؔʹΑΔಉྨ͔ΒͳΔू ߹Λ༨ྨͱݺͼɺZm ͱද͢ɻ
༨ྨͷΠϝʔδ Λ m Ͱׂͬͨ༨Ͱྨͯ͠ɺ༨͕ಉ͡ಉ༷͡ͳͷͱ ͯ͠ߟ͑Δɻͭ·ΓɺΛ 0; 1; : : : ; m ` 1 ͷ͍ͣΕ͔ʹྨͯ͠ ී௨ͷͷΘΓʹ 0; 1; : : : ; m ` 1 ͚ͩͷੈքΛߟ͍͑ͯΔɻ m = 2 ͳΒɺΛۮ͔حͷ 2 ͭʹྨ͢Δ͜ͱͱಉ͡ɻ 17 / 33
༨ྨʹ͓͚Δ๏ٯݩ ఆٛ (Zm ʹ͓͚Δ๏ٯݩ) a; b ͱࣗવ m ʹରͯ͠ɺ
ab ” 1 (mod m) ͱͳΔͱ͖ɺb Λ a ͷ๏ٯݩͱݺͼɺa`1 ͱද͢ɻ ༨ྨʹ͓͚Δ๏ٯݩͷྫ 38 ˜ 23 ” 1 (mod 97) 38 ͷ 97 Λ๏ͱ͢Δ๏ٯݩ 23 18 / 33
༨ྨʹ͓͚Δ๏ٯݩ Python ʹ͓͚Δ༨ྨʹ͓͚Δ๏ٯݩ › ΈࠐΈؔ pow ͷୈ 2 Ҿʹ `1
ΛͤܭࢉՄೳ › ͜Ε͕ Python 3.8 ͷ৽ػೳ ༨ྨʹ͓͚Δ๏ٯݩͷ࣮ߦྫ >>> pow(38, -1, 97) 23 >>> (38 * 23) % 97 == 1 True 19 / 33
༨ྨʹ͓͚Δ๏ٯݩ ඞͣ͠๏ٯݩ͕ଘࡏ͢ΔͱݶΒͳ͍ >>> pow(2, -1, 6) Traceback (most recent call
last): File "<stdin>", line 1, in <module> ValueError: base is not invertible for the given modulus ༩͑ΒΕͨ๏ʹରͯ͠ఈ͕๏ٯݩΛ࣋ͨͳ͍ʢԿނʁʣ ɻ 20 / 33
๏ٯݩΛٻΊͯ ๏ٯݩͷҙຯ a ʹରͯ͠ɺm Λ๏ͱ͢Δ߹ಉํఔࣜ ax ” 1 (mod
m) Λղ͘͜ͱʹଞͳΒͳ͍ɻ 21 / 33
߹ಉͷఆٛʹཱͪฦΔ ๏ٯݩͷҙຯ ax ” 1 (mod m) Λมܗ͢Δͱɺ1 ࣍ෆఆํఔࣜ ax
` my = 1 ͕ղ x; y Λ࣋ͭ͜ͱʹଞͳΒͳ͍ɻ 22 / 33
߹ಉํఔࣜͷղ ఆཧ a; c ʹରͯ͠ɺm Λ๏ͱ͢Δ߹ಉํఔࣜ ax ” c
(mod m) ɺc ͕ gcd(a; m) ͰׂΓΕΔͱ͖ͷΈɺͪΐ͏Ͳ gcd(a; m) ݸͷޓ͍ʹ߹ಉͰͳ͍ղΛ࣋ͭɻͨͩ͠ɺgcd(a; m) a ͱ m ͷ ࠷େެͰ͋Δɻ ূ໌ɺదͳॳͷڭՊॻΛࢀর͍ͯͩ͘͠͞ɻ 23 / 33
ࠓճͷέʔε ܥ a; ʹରͯ͠ɺm Λ๏ͱ͢Δ߹ಉํఔࣜ ax ” 1 (mod
m) ɺgcd(a; m) = 1 ͷ߹ͷΈɺ1 ݸͷޓ͍ʹ߹ಉͰͳ͍ղΛ ࣋ͭɻ ๏ٯݩ͕ଘࡏ͢Δ͔Ͳ͏ֶ͔తͳཪ͚͕͋Δɻ 24 / 33
༨ྨʹ͓͚Δ๏ٯݩ ๏ٯݩ͕ଘࡏ͢Δέʔε >>> import math >>> math.gcd(38, 97) 1 >>>
pow(38, -1, 97) 23 gcd(38; 97) = 1 ͳͷͰɺ97 Λ๏ͱ͢Δ 38 ͷ๏ٯݩ͕ଘࡏ͢Δɻ 25 / 33
༨ྨʹ͓͚Δ๏ٯݩ ๏ٯݩ͕ଘࡏ͠ͳ͍έʔε >>> import math >>> math.gcd(2, 6) 2 >>>
pow(2, -1, 6) Traceback (most recent call last): File "<stdin>", line 1, in <module> ValueError: base is not invertible for the given modulus gcd(2; 6) 6= 1 ͳͷͰɺ6 Λ๏ͱ͢Δ 2 ͷ๏ٯݩଘࡏ͠ͳ͍ɻ 26 / 33
༨ྨʹ͓͚Δ๏ٯݩ ఆཧ a ʹରͯ͠ɺm Λ๏ͱ͢Δ๏ٯݩ͕ଘࡏ͢ΔͨΊͷඞཁे ݅ gcd(a; m) =
1 Ͱ͋Δɻ ެࣜυΩϡϝϯτʹʮIf mod is present and exp is negative, base must be relatively prime to mod.ʯͱ͋Δɻ 27 / 33
Euclid ͷޓআ๏ ఆཧ a; b Λ a – b Ͱ͋Δɺr
Λ a Λ b Ͱׂͬͨ༨Γͱ͢Δɻ͜ͷ ͱ͖ɺ gcd(a; b) = gcd(b; r) ͕Γཱͭɻ 28 / 33
Euclid ͷޓআ๏ Euclid ͷޓআ๏ͱ 1 ࣍ෆఆํఔࣜ a Λ b Ͱׂͬͨͱ༨ΛͦΕͧΕ
q; r ͱ͢Δɻ1 ࣍ෆఆํఔࣜ ax + by = 1 ʹ a = qb + r Λೖ͢Δͱɺ (qb + r)x + by = 1 )b(qx + y) + rx = 1 ͱͳΔɻ ͭ·Γɺax + by = 1 ͔Β bs + rt = 1 ͱ͢Δ͜ͱ͕Ͱ͖Δɻ x = t; y = s ` qt ͱ͍͏ؔɻ 29 / 33
pow ͷத longobject.c ͷίϝϯτʹ͋Δ࣮ʢҰ෦վมʣ def invmod(a, m): x, y =
1, 0 while m: q, r = divmod(a, m) a, m = m, r x, y = y, x - q * y if a == 1: return x raise ValueError("Not invertible") 30 / 33
༨ྨʹ͓͚Δ๏ٯݩ ΞϧΰϦζϜ a ͱ m ͷ࠷େެΛܭࢉ͢ΔաఔͰ๏ٯݩΛܭࢉ͢Δ͜ͱ͕Ͱ ͖Δɻ Remark a
ʹରͯ͠ɺm Λ๏ͱ͢Δ๏ٯݩΛܭࢉ͢ΔΞϧΰϦζϜ֦ ு Euclid ͷޓআ๏ͱݺΕΔɻ 31 / 33
ԿނՃ͞Εͨͷ͔ bpo-36027 ʹॻ͔Ε͍ͯΔཧ༝ Here is another number theory basic that
I’ve needed every now... ͷجຊతͳ͔ؔͩΒඞཁͩΑͶʂ 32 / 33
·ͱΊ ·ͱΊ › pow ؔͷႈΛฦؔ͢Ͱ͋Δɻ › ႈ༨Λܭࢉ͢Δ߹ඞͣ pow ؔΛ͏ɻ ›
Python 3.8 Ͱ༨ྨͷ๏ٯݩ͕ܭࢉͰ͖ΔΑ͏ʹͳͬͨɻ › ๏ٯݩ͕ܭࢉͰ͖ΔΈ Euclid ͷޓআ๏ʹ͋Δɻ PyCon JP 2021 Discord ΑΖ͘͠ › #hayao-suzuki-ΈࠐΈؔ pow ͷΒΕ͟ΔਐԽ › #pyconjp_3 ʢ1 17:30ʙ18:15ʣ 33 / 33