Unknown Evolution of the Built-in Function pow

PyCon JP 2021

Transcript

1. ૊ΈࠐΈؔ਺ pow ͷ஌ΒΕ͟ΔਐԽ Unknown Evolution of the Built-in Function pow Hayao Suzuki PyCon JP 2021 October 15, 2021
2. ൃදʹࡍͯ͠ 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
3. Who am I ? ͓લ୭Α ໊લ Hayao Suzukiʢླ໦ɹॣʣ Twitter @CardinalXaro ࢓ࣄ Software Developer @ BeProud Inc. › גࣜձࣾϏʔϓϥ΢υ › IT ษڧձࢧԉαʔϏε connpass › ΦϯϥΠϯֶशαʔϏε PyQ › γεςϜ։ൃͷͨΊͷυΩϡϝϯταʔϏε Tracery 3 / 33
4. 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
5. 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
6. ࠓ೔ͷ໨ඪ ૊ΈࠐΈؔ਺ pow › pow ؔ਺͸਺ͷႈ৐Λฦؔ͢਺ › Python ʹݶΒͣɺେ఍ͷݴޠʹ͸ pow ؔ਺͕ଘࡏ͢Δ Python 3.8 Ͱػೳ௥Ճ › ੔਺ m Λ๏ͱ͢Δ੔਺৒༨ྨʹ͓͚Δ৐๏ٯݩ͕ܭࢉͰ͖Δ › Α͘Θ͔Βͳ͍୯ޠΛฒ΂Δͳʂ 6 / 33
7. ࠓ೔ͷ໨ඪ ૊ΈࠐΈؔ਺ pow ͷ஌ΒΕ͟ΔਐԽ › Python 3.8 Ͱ௥Ճ͞Εͨ pow ؔ਺ͷ৽ػೳΛཧղ͢Δ › ʮ੔਺ m Λ๏ͱ͢Δ੔਺৒༨ྨʹ͓͚ΔٯݩʯͷҙຯΛཧղ͢Δ › ʮ੔਺ m Λ๏ͱ͢Δ੔਺৒༨ྨʹ͓͚ΔٯݩʯΛܭࢉ͢ΔΞϧΰ ϦζϜΛཧղ͢Δ 7 / 33
8. ࠓ·Ͱͷ pow ؔ਺ Python 3.7 ·Ͱͷ pow ؔ਺Λ෮श͠Α͏ 8 / 33
9. ੔਺ͷႈ৐ ఆٛ (੔਺ͷႈ৐) ੔਺ b ͱࣗવ਺ n ʹରͯ͠ɺႈ৐ bn Λ bn ≜ n ݸ z }| { b ˆ b ˆ ´ ´ ´ ˆ b ͱఆٛ͢Δɻb Λఈɺn Λࢦ਺ͱݺͿɻ ੔਺ͷႈ৐ͷྫ 232 = 4294967296: 9 / 33
10. ੔਺ͷႈ৐ Python ʹ͓͚Δႈ৐ ૊ΈࠐΈؔ਺ pow ·ͨ͸**ԋࢉࢠΛ࢖͏ɻ ႈ৐ͷ࣮ߦྫ >>> pow(2, 32) 4294967296 >>> 2 ** 32 4294967296 10 / 33
11. ႈ৐৒༨ ఆٛ (ႈ৐৒༨) ࣗવ਺ͷఈ b ͱࣗવ਺ n; m ʹରͯ͠ɺ bn mod m Λ m Λ๏ͱ͢Δႈ৐৒༨ͱఆٛ͢Δɻ ႈ৐৒༨ͷྫ 232 mod 65535 = 1: 11 / 33
12. ႈ৐৒༨ Python ʹ͓͚Δႈ৐৒༨ › ૊ΈࠐΈؔ਺ pow Ͱޮ཰తʹܭࢉͰ͖Δɻ › **ԋࢉࢠ͓Αͼ%ԋࢉࢠͰ΋ܭࢉՄೳ͕ͩޮ཰͕ѱ͍ɻ › Python 1.5 ͔Βར༻Մೳʢint ܕͷൣғ಺ͳͲͷ੍ݶ͸ ͋ͬͨʣ ɻ ႈ৐৒༨ͷ࣮ߦྫ >>> pow(2, 262144, 65535) 1 >>> (2 ** 262144) % 65535 1 12 / 33
13. ႈ৐৒༨ ͲΕ͚ͩޮ཰త͔ >>> import timeit >>> timeit.timeit("pow(2, 262144, 65535)", number=1000) 0.0007324999999999693 >>> timeit.timeit("(2 ** 262144) % 65535", number=1000) 0.868453 ݁ՌΛ࣮ߦճ਺ͰׂΕ͹ฏۉ͕࣌ؒΘ͔Δɻ 13 / 33
14. ႈ৐৒༨ ԋࢉࢠͱؔ਺ʹ͓͚Δܭࢉ࣌ؒͷൺֱ 14 / 33
15. ͜Ε͔Βͷ pow ؔ਺ Python 3.8 ͔Βͷ pow ؔ਺Λཧղ͢ΔͨΊʹ 15 / 33
16. ੔਺ͷ߹ಉ ఆٛ (੔਺ͷ߹ಉ) ੔਺ a ͕ m Λ๏ͱͯ͠ b ͱ߹ಉͰ͋Δͱ͸ m ͕ a ` b ΛׂΓ੾Δ ͜ͱΛ͍͍ɺ a ” b (mod m) ͱද͢ɻ ੔਺ͷ߹ಉͷྫ 47 ” 35 (mod 6) 47 ` 35 = 12 ͸ 6 ͰׂΓ੾ΕΔɻ 16 / 33
17. ੔਺৒༨ྨ ఆٛ (੔਺৒༨ྨ) ੔਺ू߹ Z ͱ੔਺ m Λ๏ͱ͢Δ߹ಉؔ܎ʹΑΔಉ஋ྨ͔ΒͳΔ঎ू ߹Λ੔਺৒༨ྨͱݺͼɺZm ͱද͢ɻ ੔਺৒༨ྨͷΠϝʔδ ੔਺Λ m Ͱׂͬͨ৒༨Ͱ෼ྨͯ͠ɺ৒༨͕ಉ͡੔਺͸ಉ༷͡ͳ΋ͷͱ ͯ͠ߟ͑Δɻͭ·Γɺ੔਺Λ 0; 1; : : : ; m ` 1 ͷ͍ͣΕ͔ʹ෼ྨͯ͠ ී௨ͷ੔਺ͷ୅ΘΓʹ 0; 1; : : : ; m ` 1 ͚ͩͷੈքΛߟ͍͑ͯΔɻ m = 2 ͳΒ͹ɺ੔਺Λۮ਺͔ح਺ͷ 2 ͭʹ෼ྨ͢Δ͜ͱͱಉ͡ɻ 17 / 33
18. ੔਺৒༨ྨʹ͓͚Δ৐๏ٯݩ ఆٛ (Zm ʹ͓͚Δ৐๏ٯݩ) ੔਺ a; b ͱࣗવ਺ m ʹରͯ͠ɺ ab ” 1 (mod m) ͱͳΔͱ͖ɺb Λ a ͷ৐๏ٯݩͱݺͼɺa`1 ͱද͢ɻ ੔਺৒༨ྨʹ͓͚Δ৐๏ٯݩͷྫ 38 ˜ 23 ” 1 (mod 97) 38 ͷ 97 Λ๏ͱ͢Δ৐๏ٯݩ͸ 23 18 / 33
19. ੔਺৒༨ྨʹ͓͚Δ৐๏ٯݩ Python ʹ͓͚Δ੔਺৒༨ྨʹ͓͚Δ৐๏ٯݩ › ૊ΈࠐΈؔ਺ pow ͷୈ 2 Ҿ਺ʹ `1 Λ౉ͤ͹ܭࢉՄೳ › ͜Ε͕ Python 3.8 ͷ৽ػೳ ੔਺৒༨ྨʹ͓͚Δ৐๏ٯݩͷ࣮ߦྫ >>> pow(38, -1, 97) 23 >>> (38 * 23) % 97 == 1 True 19 / 33
20. ੔਺৒༨ྨʹ͓͚Δ৐๏ٯݩ ඞͣ͠΋৐๏ٯݩ͕ଘࡏ͢Δͱ͸ݶΒͳ͍ >>> 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
21. ৐๏ٯݩΛٻΊͯ ৐๏ٯݩͷҙຯ ੔਺ a ʹରͯ͠ɺm Λ๏ͱ͢Δ߹ಉํఔࣜ ax ” 1 (mod m) Λղ͘͜ͱʹଞͳΒͳ͍ɻ 21 / 33
22. ߹ಉͷఆٛʹཱͪฦΔ ৐๏ٯݩͷҙຯ ax ” 1 (mod m) Λมܗ͢Δͱɺ1 ࣍ෆఆํఔࣜ ax ` my = 1 ͕੔਺ղ x; y Λ࣋ͭ͜ͱʹଞͳΒͳ͍ɻ 22 / 33
23. ߹ಉํఔࣜͷղ ఆཧ ੔਺ a; c ʹରͯ͠ɺm Λ๏ͱ͢Δ߹ಉํఔࣜ ax ” c (mod m) ͸ɺc ͕ gcd(a; m) ͰׂΓ੾ΕΔͱ͖ͷΈɺͪΐ͏Ͳ gcd(a; m) ݸͷޓ͍ʹ߹ಉͰ͸ͳ͍ղΛ࣋ͭɻͨͩ͠ɺgcd(a; m) ͸ a ͱ m ͷ ࠷େެ໿਺Ͱ͋Δɻ ূ໌͸ɺద౰ͳॳ౳੔਺࿦ͷڭՊॻΛࢀর͍ͯͩ͘͠͞ɻ 23 / 33
24. ࠓճͷέʔε ܥ ੔਺ a; ʹରͯ͠ɺm Λ๏ͱ͢Δ߹ಉํఔࣜ ax ” 1 (mod m) ͸ɺgcd(a; m) = 1 ͷ৔߹ͷΈɺ1 ݸͷޓ͍ʹ߹ಉͰ͸ͳ͍ղΛ ࣋ͭɻ ৐๏ٯݩ͕ଘࡏ͢Δ͔Ͳ͏͔͸਺ֶతͳཪ෇͚͕͋Δɻ 24 / 33
25. ੔਺৒༨ྨʹ͓͚Δ৐๏ٯݩ ৐๏ٯݩ͕ଘࡏ͢Δέʔε >>> import math >>> math.gcd(38, 97) 1 >>> pow(38, -1, 97) 23 gcd(38; 97) = 1 ͳͷͰɺ97 Λ๏ͱ͢Δ 38 ͷ৐๏ٯݩ͕ଘࡏ͢Δɻ 25 / 33
26. ੔਺৒༨ྨʹ͓͚Δ৐๏ٯݩ ৐๏ٯݩ͕ଘࡏ͠ͳ͍έʔε >>> 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
27. ੔਺৒༨ྨʹ͓͚Δ৐๏ٯݩ ఆཧ ੔਺ a ʹରͯ͠ɺm Λ๏ͱ͢Δ৐๏ٯݩ͕ଘࡏ͢ΔͨΊͷඞཁे෼৚ ݅͸ gcd(a; m) = 1 Ͱ͋Δɻ ެࣜυΩϡϝϯτʹ΋ʮIf mod is present and exp is negative, base must be relatively prime to mod.ʯͱ͋Δɻ 27 / 33
28. Euclid ͷޓআ๏ ఆཧ a; b Λ a – b Ͱ͋Δ੔਺ɺr Λ a Λ b Ͱׂͬͨ༨Γͱ͢Δɻ͜ͷ ͱ͖ɺ gcd(a; b) = gcd(b; r) ͕੒Γཱͭɻ 28 / 33
29. 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
30. 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
31. ੔਺৒༨ྨʹ͓͚Δ৐๏ٯݩ ΞϧΰϦζϜ a ͱ m ͷ࠷େެ໿਺Λܭࢉ͢ΔաఔͰ৐๏ٯݩΛܭࢉ͢Δ͜ͱ͕Ͱ ͖Δɻ Remark ੔਺ a ʹରͯ͠ɺm Λ๏ͱ͢Δ৐๏ٯݩΛܭࢉ͢ΔΞϧΰϦζϜ͸֦ ு Euclid ͷޓআ๏ͱݺ͹ΕΔɻ 31 / 33
32. Կނ௥Ճ͞Εͨͷ͔ bpo-36027 ʹॻ͔Ε͍ͯΔཧ༝ Here is another number theory basic that I’ve needed every now... ਺࿦ͷجຊతͳؔ਺͔ͩΒඞཁͩΑͶʂ 32 / 33
33. ·ͱΊ ·ͱΊ › pow ؔ਺͸਺ͷႈ৐Λฦؔ͢਺Ͱ͋Δɻ › ႈ৐৒༨Λܭࢉ͢Δ৔߹͸ඞͣ pow ؔ਺Λ࢖͏ɻ › Python 3.8 Ͱ੔਺৒༨ྨͷ৐๏ٯݩ͕ܭࢉͰ͖ΔΑ͏ʹͳͬͨɻ › ৐๏ٯݩ͕ܭࢉͰ͖Δ࢓૊Έ͸ Euclid ͷޓআ๏ʹ͋Δɻ PyCon JP 2021 Discord ΋ΑΖ͘͠ › #hayao-suzuki-૊ΈࠐΈؔ਺ pow ͷ஌ΒΕ͟ΔਐԽ › #pyconjp_3 ʢ1 ೔໨ 17:30ʙ18:15ʣ 33 / 33