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
290
みんなでたのしむ math/big / i love math big
convto
May 10, 2024
Tweet
Share
More Decks by convto
See All by convto
詳解!defer panic recover のしくみ / Understanding defer, panic, and recover
convto
0
240
MCPと認可まわりの話 / mcp_and_authorization
convto
2
690
バクラクの認証基盤の成長と現在地 / bakuraku-authn-platform
convto
4
1.4k
gob バイナリが Go バージョンによって 出力が変わることについて調べてみた / Investigating How gob Binary Output Changes Across Go Versions
convto
0
130
Go 関連の個人的おもしろCVE 5選 / my favorite go cve
convto
3
480
バイナリを眺めてわかる gob encoding の仕様と性質、適切な使い方 / understanding gob encoding
convto
6
2.9k
Go1.22からの疑似乱数生成器について/go-122-pseudo-random-generator
convto
2
850
Go1.20からサポートされるtree構造のerrの紹介と、treeを考慮した複数マッチができるライブラリを作った話/introduction of tree structure err added since go 1_20
convto
0
1.2k
byte列のbit表現を得るencodingライブラリ作った
convto
1
1.3k
Other Decks in Technology
See All in Technology
大「個人開発サービス」時代に僕たちはどう生きるか
sotarok
20
10k
DevIO2025_継続的なサービス開発のための技術的意思決定のポイント / how-to-tech-decision-makaing-devio2025
nologyance
1
400
なぜスクラムはこうなったのか?歴史が教えてくれたこと/Shall we explore the roots of Scrum
sanogemaru
5
1.6k
【NoMapsTECH 2025】AI Edge Computing Workshop
akit37
0
210
AI時代を生き抜くエンジニアキャリアの築き方 (AI-Native 時代、エンジニアという道は 「最大の挑戦の場」となる) / Building an Engineering Career to Thrive in the Age of AI (In the AI-Native Era, the Path of Engineering Becomes the Ultimate Arena of Challenge)
jeongjaesoon
0
190
Oracle Base Database Service 技術詳細
oracle4engineer
PRO
9
74k
S3アクセス制御の設計ポイント
tommy0124
3
200
「Linux」という言葉が指すもの
sat
PRO
4
140
サラリーマンの小遣いで作るtoCサービス - Cloudflare Workersでスケールする開発戦略
shinaps
2
460
Platform開発が先行する Platform Engineeringの違和感
kintotechdev
4
580
AIのグローバルトレンド2025 #scrummikawa / global ai trend
kyonmm
PRO
1
300
react-callを使ってダイヤログをいろんなとこで再利用しよう!
shinaps
1
250
Featured
See All Featured
Designing for Performance
lara
610
69k
Six Lessons from altMBA
skipperchong
28
4k
Code Review Best Practice
trishagee
70
19k
Documentation Writing (for coders)
carmenintech
74
5k
What's in a price? How to price your products and services
michaelherold
246
12k
Thoughts on Productivity
jonyablonski
70
4.8k
The Pragmatic Product Professional
lauravandoore
36
6.9k
Making Projects Easy
brettharned
117
6.4k
Making the Leap to Tech Lead
cromwellryan
135
9.5k
ReactJS: Keep Simple. Everything can be a component!
pedronauck
667
120k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
358
30k
Faster Mobile Websites
deanohume
309
31k
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/
ご清聴ありがとうございました