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
みんなでたのしむ math/big / i love math big
Search
convto
May 10, 2024
Technology
0
270
みんなでたのしむ math/big / i love math big
convto
May 10, 2024
Tweet
Share
More Decks by convto
See All by convto
バクラクの認証基盤の成長と現在地 / bakuraku-authn-platform
convto
4
1.1k
gob バイナリが Go バージョンによって 出力が変わることについて調べてみた / Investigating How gob Binary Output Changes Across Go Versions
convto
0
100
Go 関連の個人的おもしろCVE 5選 / my favorite go cve
convto
3
420
バイナリを眺めてわかる gob encoding の仕様と性質、適切な使い方 / understanding gob encoding
convto
6
2.7k
Go1.22からの疑似乱数生成器について/go-122-pseudo-random-generator
convto
2
760
Go1.20からサポートされるtree構造のerrの紹介と、treeを考慮した複数マッチができるライブラリを作った話/introduction of tree structure err added since go 1_20
convto
0
1.1k
byte列のbit表現を得るencodingライブラリ作った
convto
1
1.2k
Go runtimeの歩き方/how to follow go runtime function
convto
1
990
入出金ドメインの苦労話と解決へのアプローチ/funds in/out difficulties and solutions
convto
2
1.4k
Other Decks in Technology
See All in Technology
[zh-TW] DevOpsDays Taipei 2025 -- Creating Awesome Change in SmartNews!(machine translation)
martin_lover
1
650
AIコードエディタは開発を変えるか?Cursorをチームに導入して1ヶ月経った本音
ota1022
1
700
【5分でわかる】セーフィー エンジニア向け会社紹介
safie_recruit
0
25k
Oracle Base Database Service 技術詳細
oracle4engineer
PRO
8
65k
All About Sansan – for New Global Engineers
sansan33
PRO
1
1.2k
やさしいClaude Code入門
minorun365
PRO
32
25k
AIに実況させる / AI Streamer
motemen
3
1.4k
What's Next in OpenShift Q2 CY2025
redhatlivestreaming
1
820
障害を回避するHttpClient再入門 / Avoiding Failures HttpClient Reintroduction
uskey512
1
140
GitHub Coding Agent 概要
kkamegawa
1
1.7k
データプレーンプログラミングとは? DPU&スイッチASICの開発経験から語る
ebiken
PRO
1
270
テストを実施する前に考えるべきテストの話 / Thinking About Testing Before You Test
nihonbuson
PRO
14
2.1k
Featured
See All Featured
Statistics for Hackers
jakevdp
799
220k
How to Ace a Technical Interview
jacobian
276
23k
Into the Great Unknown - MozCon
thekraken
39
1.8k
Typedesign – Prime Four
hannesfritz
41
2.6k
How to Think Like a Performance Engineer
csswizardry
23
1.6k
Building Applications with DynamoDB
mza
95
6.4k
Dealing with People You Can't Stand - Big Design 2015
cassininazir
367
26k
Refactoring Trust on Your Teams (GOTO; Chicago 2020)
rmw
34
3k
Large-scale JavaScript Application Architecture
addyosmani
512
110k
VelocityConf: Rendering Performance Case Studies
addyosmani
329
24k
Optimising Largest Contentful Paint
csswizardry
37
3.3k
Templates, Plugins, & Blocks: Oh My! Creating the theme that thinks of everything
marktimemedia
30
2.4k
Transcript
みんなでたのしむ math/big 2024/05/10(金) Asakusa.go
自己紹介 @convto レイヤ低めの技術などに興味がありま す 読みはこんぶとです つくばエクスプレス沿線ユーザー、論理 浅草勢として参戦しました
突然ですが Go Conference 2024 参加しますか?
すきなパッケージなにを選びましたか?
ぼくは math/big ! - math/big はいいぞ - あったら嬉しい処理を標準で準備してくれ てるのは助かる -
実装も TAOCP で言及されてるやつばっ かり - どういう課題があるのか、どういう面白い ことしてるのか、ざっと触りを伝えたい
発表の目的 - 課題: math/big は面白いが, おもしろいと 言ってる人をあまり見かけない - 目的: どういう課題があるのか,
どういう 面白いことしてるのか, ざっと触りを伝え たい - いきごみ: 前提知識が必要なところもある ので, そのへんは深入りせずみんなでた のしみましょう〜
今日話すこと
contents - math/big ってなに? - どういうところで使われてるの? - 多倍長演算って大変なの? - math/big
はどういうアルゴリズムを実装 してるの? - まとめ: math/big はいいぞ
math/big ってなに?
ようは限界を超えて舞えるやつ
word size を超えた多倍長演算をサポートする - 値を word size の値の slice として扱っ
て、でかい整数や任意精度の浮動小数と かの演算をする - な、なにがうれしいんだってばよ...? big.Int の型はこれだけ (nat は word の slice)
どういうところで使われてるの?
使われかたいろいろ - math/big.Int だけみても, 暗号周りでよく 使う - 巨大な整数の冪乗とかたくさんする ため, RSA
以外にもいろいろ - math/big.Float は ethereum/go-ethereum とかで使われて るのを見た std crypto で使われてる図
多倍長演算って大変なの?
計算コストとか (多倍長整数) - 加算, 減算は雑にやっても O(N) とか. N は word
slice の len
計算コストとか (多倍長整数) - 加算, 減算は雑にやっても O(N) とか. N は word
slice の len x_1 x_2 x_3 x_4 y_1 y_2 y_3 y_4 +
計算コストとか (多倍長整数) - 加算, 減算は雑にやっても O(N) とか. N は word
slice の len x_1 x_2 x_3 x_4 y_1 y_2 y_3 y_4 + r_4 carry_4
計算コストとか (多倍長整数) - 加算, 減算は雑にやっても O(N) とか. N は word
slice の len x_1 x_2 x_3 x_4 y_1 y_2 y_3 y_4 + r_4 r_3 carry_3
計算コストとか (多倍長整数) - 加算, 減算は雑にやっても O(N) とか. N は word
slice の len x_1 x_2 x_3 x_4 y_1 y_2 y_3 y_4 + z_4 z_3 carry_3 以下繰り返す...
計算コストとか (多倍長整数) - 加算, 減算は雑にやっても O(N) とか. N は word
slice の len x_1 x_2 x_3 x_4 y_1 y_2 y_3 y_4 + z_4 z_3 z_2 z_1 carry_1
計算コストとか (多倍長整数) - 加算, 減算は雑にやっても O(N) とか. N は word
slice の len x_1 x_2 x_3 x_4 y_1 y_2 y_3 y_4 - z_4 z_3 z_2 z_1 borrow_4 … 減算も大体おなじ! 足りなかったら借りてきたりする とかちょっと違いはあるが、減 算も大体おなじ!
計算コストとか (多倍長整数) - 加算, 減算は雑にやっても O(N) とか. N は word
slice の len - 乗算, 除算は結構きつい. ざつにやると O(N^2) になる
計算コストとか (多倍長整数) - 加算, 減算は雑にやっても O(N) とか. N は word
slice の len - 乗算, 除算は結構きつい. ざつにやると O(N^2) になる x_1 x_2 x_3 y_1 y_2 y_3 x
計算コストとか (多倍長整数) - 加算, 減算は雑にやっても O(N) とか. N は word
slice の len - 乗算, 除算は結構きつい. ざつにやると O(N^2) になる x_1 x_2 x_3 y_1 y_2 y_3 x z_3:3 z_2:3 z_1:3 c_3:3 c_2:3 c_1:3
計算コストとか (多倍長整数) - 加算, 減算は雑にやっても O(N) とか. N は word
slice の len - 乗算, 除算は結構きつい. ざつにやると O(N^2) になる x_1 x_2 x_3 y_1 y_2 y_3 x z_3:3 z_2:3 z_1:3 c_3:3 c_2:3 c_1:3 z_3:2 z_2:2 z_1:2 c_2:2 c_3:2 c_1:2
計算コストとか (多倍長整数) - 加算, 減算は雑にやっても O(N) とか. N は word
slice の len - 乗算, 除算は結構きつい. ざつにやると O(N^2) になる x_1 x_2 x_3 y_1 y_2 y_3 x z_3:3 z_2:3 z_1:3 c_3:3 c_2:3 c_1:3 z_3:2 z_2:2 z_1:2 c_2:2 c_3:2 c_1:2 つづく...
計算コストとか (多倍長整数) - 加算, 減算は雑にやっても O(N) とか. N は word
slice の len - 乗算, 除算は結構きつい. ざつにやると O(N^2) になる x_1 x_2 x_3 y_1 y_2 y_3 ÷
計算コストとか (多倍長整数) - 加算, 減算は雑にやっても O(N) とか. N は word
slice の len - 乗算, 除算は結構きつい. ざつにやると O(N^2) になる x_1 x_2 x_3 y_1 y_2 y_3 ÷ z_1 z_2 z_3 上の桁から for 1..9 mul(y, i) して、xに収まる最大の値を入 れていく...
計算コストとか (多倍長整数) - 加算, 減算は雑にやっても O(N) とか. N は word
slice の len - 乗算, 除算は結構きつい. ざつにやると O(N^2) になる - ぼくらは (bigint^bigint) mod bigint とか をやりたがるが, そんなことをすると号泣 してしまう
計算コストとか (多倍長整数) - 加算, 減算は雑にやっても O(N) とか. N は word
slice の len - 乗算, 除算は結構きつい. ざつにやると O(N^2) になる - ぼくらは (bigint^bigint) mod bigint とか をやりたがるが, そんなことをすると号泣 してしまう - O(N^2) の掛け合わせだってばよ...
それ以外に求められる機能とか - 算術演算だけじゃなくて、ほかにも求めら れるものがある - bit shift 的な操作もほしーよーとか - 任意サイズのでけー素数を生成して〜と
か - 泣いちゃいますね
大変です - 演算するだけでも計算量低いアルゴリズ ムを使わんとあかん, 素朴にやってはい けません - それだけじゃなくて, いくつかの要求もあ るためそれにも答えないとあかん
math/big はどういう アルゴリズムを実装してるの?
てきとうにpickして説明
karatsuba 法による多倍長整数乗算 - [x_1, x_2] * [y_1, y_2] の乗算は, 4回
計算必要 - x1*y1, x1*y2, x2*y1, x2*y2 - (厳密にはこれらを足し合わせる必要 があるが省略)
x_1 x_2 y_1 y_2 x_2*y_2 x karatsuba 法による多倍長整数乗算 - [x_1,
x_2] * [y_1, y_2] の乗算は, 4回 計算必要 - x1*y1, x1*y2, x2*y1, x2*y2 - (厳密にはこれらを足し合わせる必要 があるが省略) x_2*y_1 x_1*y_2 x_1*y_1 * word * word * (word ^ 2)
x_1 x_2 y_1 y_2 x_2*y_2 x karatsuba 法による多倍長整数乗算 - [x_1,
x_2] * [y_1, y_2] の乗算は, 4回 計算必要 - x1*y1, x1*y2, x2*y1, x2*y2 - (厳密にはこれらを足し合わせる必要 があるが省略) - これを3回にできるテクがある x_2*y_1 x_1*y_2 x_1*y_1 * word * word * (word ^ 2)
ふつうにやるとこう x_2*y_1 x_1*y_2 ( + ) + << word x_2*y_2
x_1*y_1 << (word * 2) + + 乗算4回
こいつをグッとにらむ x_2*y_1 x_1*y_2 ( + )
こいつをグッとにらむ x_2*y_1 x_1*y_2 ( + ) = x_2 + x_1
y_1 + y_2 ( * ) - ( + ) x_1*y_1 x_2*y_2
こいつをグッとにらむ x_2*y_1 x_1*y_2 ( + ) = x_2 + x_1
y_1 + y_2 ( * ) - ( + ) x_1*y_1 x_2*y_2 すでに求めてるの でコストなし
こいつをグッとにらむ x_2*y_1 x_1*y_2 ( + ) = x_2 + x_1
y_1 + y_2 ( * ) - ( + ) x_1*y_1 x_2*y_2 すでに求めてるの でコストなし コストの高い乗算が 2回 -> 1回に!
さっきのに入れるとこうなる x_2 + x_1 y_1 + y_2 ( * )
- ( + ) x_1*y_1 x_2*y_2 ( ) << word x_2*y_2 x_1*y_1 << (word * 2) + +
さっきのに入れるとこうなる x_2 + x_1 y_1 + y_2 ( * )
- ( + ) x_1*y_1 x_2*y_2 ( ) << word x_2*y_2 x_1*y_1 << (word * 2) + + 3回しか乗算してない!
ほかにもいろいろ! - GCD(最大公約数)だすやつ - 冪乗のmodとるやつ - 剰余環の逆元とるやつ - and more!
うれしい! - これほしいな〜と思うものは大体ある - かつ妥当なアルゴリズムを使ってる - 前提知識を求めるものも標準で作られて る! - 実質
TAOCP 本であり、本読みながら実 装みるとたのしい
まとめ: math/big はいいぞ
math/big はいいぞ - こいつがなかったら crypto package は ギャンこまり - 実質
TAOCP 詰め合わせセット. コードに も TAOCP section x.y を参考にしたでみ たいなコメントいっぱいある. 本片手に読 むといい勉強になる - みんなもでかい値を扱おう!
今週のスローガン - 夢は大きく値もでかく, みんなでやろう math/big
宣伝
https://layerx.connpass.com/event/317228/
ご清聴ありがとうございました