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
170
みんなでたのしむ math/big / i love math big
convto
May 10, 2024
Tweet
Share
More Decks by convto
See All by convto
gob バイナリが Go バージョンによって 出力が変わることについて調べてみた / Investigating How gob Binary Output Changes Across Go Versions
convto
0
43
Go 関連の個人的おもしろCVE 5選 / my favorite go cve
convto
3
300
バイナリを眺めてわかる gob encoding の仕様と性質、適切な使い方 / understanding gob encoding
convto
6
1.9k
Go1.22からの疑似乱数生成器について/go-122-pseudo-random-generator
convto
2
430
Go1.20からサポートされるtree構造のerrの紹介と、treeを考慮した複数マッチができるライブラリを作った話/introduction of tree structure err added since go 1_20
convto
0
840
byte列のbit表現を得るencodingライブラリ作った
convto
1
1.1k
Go runtimeの歩き方/how to follow go runtime function
convto
1
880
入出金ドメインの苦労話と解決へのアプローチ/funds in/out difficulties and solutions
convto
2
1.3k
rsa_understanding_memo
convto
0
530
Other Decks in Technology
See All in Technology
学術機関におけるID連携とOpenID Connect
fujie
0
580
不感対策ソリューション
jtes
0
220
読みやすいテストコードの書き方
autifyhq
0
120
【株式会社ELYZA】|GENIAC成果報告会 自社開発モデルプレゼンテーション
elyza
2
770
公共交通データとアプリ制作 - Mini Tokyo 3D の初期制作過程を振り返る
nagix
2
190
FastAPIでのasync defとdefの使い分け
takashi1029
3
550
あなたのアプリケーションをレガシーコードにしないための実践Pytest入門/pyconjp2024_pytest
mhrtech
3
280
What’s new in Keycloak, the open source IAM?
ahus1
1
120
Vista FinderMx
jtes
0
160
サーバーレスAPIのパフォーマンステストとアプリの未来
nagix
5
2.9k
CDK Pipelinesをざっくり理解する
smt7174
0
190
『SUUMO』 スマホサイト デザインリニューアルへの挑戦
recruitengineers
PRO
4
130
Featured
See All Featured
Testing 201, or: Great Expectations
jmmastey
36
7k
From Idea to $5000 a Month in 5 Months
shpigford
380
46k
How to Ace a Technical Interview
jacobian
274
23k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
eileencodes
28
1.7k
Side Projects
sachag
452
42k
Robots, Beer and Maslow
schacon
PRO
157
8.2k
Typedesign – Prime Four
hannesfritz
39
2.3k
Designing for humans not robots
tammielis
248
25k
Building Better People: How to give real-time feedback that sticks.
wjessup
359
19k
Dealing with People You Can't Stand - Big Design 2015
cassininazir
363
22k
Clear Off the Table
cherdarchuk
91
320k
Keith and Marios Guide to Fast Websites
keithpitt
408
22k
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/
ご清聴ありがとうございました