【c++】二分探索より速いisqrtを実装する
はじめに この記事はアドベントカレンダー2025 16日目の記事です コンテスト中の人へ or 結果が早く知りたい人へ コードを示します。コードテストでも何でもにこれをコピペしたら、正しく動いていることが分かると思います。 #include <iostream> #include <vector> using namespace std; unsigned long long isqrt_aux(int c,unsigned long long n){ if (c == 0){ return 1; } else { int k = (c - 1) / 2; unsigned long long a = isqrt_aux(c / 2, n >> (2*k + 2)); return (a << k) + (n >> (k+2)) / a; } } unsigned long isqrt(u
自然言語処理を10年ぐらいやってきた
学業でも仕事でも趣味でも、ずっと自然言語処理をやってきた。 別に最初からAIだのNLPだのに興味があったわけじゃない。 きっかけは、学生時代にちょっとしたレポートでテキストの単語出現頻度を数えようとしたとき、「あれ、そもそも日本語ってどうやって単語に分けんの？」って疑問が出たところからだ。 英語ならスペースで切れるけど、日本語はそうはいかない。で、いろいろ調べて「形態素解析」って言葉にたどり着いた。 その瞬間にちょっとハマったんだよね。 辞書をもとに文を機械的に切り刻んで、品詞をラベル付けして、統計を取って、構文を推定する。まるで人間の頭の中を数理的に覗いているようで。 そこからMeCabとかJumanとかKyTeaとか、いろんなツールを触った。 Pythonでテキスト処理のパイプラインを組んだり、mecab-ipadic-NEologdを突っ込んで新語に対応させたり。 「言葉を数理で扱え
90 分で学ぶ P 対 NP 問題
第1章 導入 (6～54 ページ) 第2章 P 対 NP 問題の定義 (55～90 ページ) 第3章 P=NP の場合にわかること (91～111 ページ) 第4章 P≠NP の場合にわかること (112～226 ページ) 第5章 まとめ (227～234 ページ)
ssh-keygenしたときに出るあのキラキラの正体
LabBaseテックカレンダー Advent Calendar 2024の12月17日分のアドベントカレンダーです。 このブログのゴール ssh-keygenしたときに出るあのキラキラの正体を突き止めて、Rustで完全再現する⭐️ 再現するだけにとどまらずオエー鳥AAで似たようなものを作る🐦⬛ コードはここ 出典 http://www.dirk-loss.de/sshvis/drunken_bishop.pdf https://github.com/lfam/randomart あのキラキラの正体 randomartって言う テキストベースのフィンガープリントだと人間が誤って確認するリスクがあるから、視覚的な差分が取りやすいようにAAとして可視化している アルゴリズム 公開鍵ファイルの解析 公開鍵の中身はこうなっている ssh-ed25519 AAAAC3NzaC1lZDI1NTE5A
malloc.c を読む (malloc / free)
このシリーズではこれらの関数が内部でどのように処理されるのかを調べていきます。 malloc.c を読む (malloc / free) malloc.c を読む (bins) malloc.c を読む (arena) 今回は malloc() free() の全体像を紹介します。 注意としてここでの目的は全体を俯瞰して、詳細を詰めずとも各 bins の役割を理解し、攻撃手法を理解できるようにすることです。それに合わないマルチスレッドや最適化などにおける緻密なトリックやコーナーケースなどは暗黙的に実装されていると仮定します。その詳細についてはソースコードや他の資料を参考にしていただきたいです。 ここで扱う glibc のバージョンは v2.38 です。また glibc のソースコードはブラウザ上で読むことができます。 https://elixir.bootlin.com/glibc/lat
オセロの必勝法が見つかった件 | やねうら王 公式サイト
すごいニュースが飛び込んできた。オセロの必勝法が見つかったのだ。正確に言うとオセロが弱解決された。まずはその論文を紹介する。 Othello is Solved : https://arxiv.org/abs/2310.19387 「弱解決(weakly solved)」を簡単に言うと、初期局面からの双方最善手を打つ時の結論(勝敗)がわかったと言う意味である。8×8のオセロの結論は引き分けなのだそうだ。「必勝法が見つかった」と本記事のタイトルで書いたが、その結果として双方最善を尽くした時のオセロの結論が引き分けだったことが判明したので正しくは「必勝法(必ず勝てる方法)が存在しないことが証明された」とでも言うべきか。 今回は、初期局面から到達できるあらゆる局面についての結論(勝敗)がわかったわけではない。こちらは「強解決(strongly solved)」と呼ばれる。 弱解決と強解決とでは、
天才プログラマだと言われる人が書くコードは、どんな観点が天才的なんでしょうか？ | mond
天才プログラマと言われて頭に思い描く人物が複数いて、共通点が実はそんなに無いので共通点を洗い出すのはやめて「自分だったらできないだろうなぁ」という事例を思い出した順に列挙してみます。 しょぼそうな高速化がめちゃくちゃ刺さる凡人に理解できないような天才的なアルゴリズムを用いてめちゃくちゃ計算量を減らしている、なんてことは実はほぼ見かけなくて実際によくあるのがこのパターンです。賢いアルゴリズムというだけなら素養のある秀才ならなんだかんだ思いつくので個人的には天才とまでは感じません。 天才は「Aを受け取って計算してBを返す」みたいな一見平凡な処理に対し「Aの配列を受け取って結果をBの配列にして返す」みたいな誰でも思いつくようなしょぼそうな効率化を行って途方もない効率化を果たします。もちろん凡人が任意の場所でそういう細かい最適化を入れて同様の効率化が再現されるわけではないのですが、天才はただのバッ
何故パスワードをハッシュ化して保存するだけでは駄目なのか？ - NRIネットコムBlog
不正アクセスによるIDとパスワードの漏洩を受けて、MD5によるハッシュ化について話題になっていました。システムを作る上で、パスワードの管理や認証はどう設計すべきかを考えるために、少し整理をしてみます。もし事実誤認があれば、どしどしご指摘ください。 == 2023/8/21追記 == この記事は、ハッシュの保存の仕方一つとっても、沢山の対策方法が必要であるということをお伝えするために記載しています。そして、これから紹介する手法を取れば安全とお勧めしている訳ではないので、その点をご留意いただければと思います。攻撃手法に応じての対応策の変遷を知っていただくことで、セキュリティ対策は一度行えば安全というものではないことを知って頂くキッカケになれば幸いです。 == 追記終わり == パスワードのハッシュ化 まず最初にパスワードの保存方法です。何も加工しないで平文で保存するのは駄目というのは、だいぶ認
解説: Life Universe
公開からだいぶ時間が経ってしまいましたが、Life Universe の技術解説を書きます。 English version is here. Life Universe について その前に、いくつか知っておくとよい事柄があるので先に説明します。 OTCA Metapixel について ライフゲームの説明については割愛します。ライフゲームはチューリング完全なので様々なパターンが存在し、その中に OTCA Metapixel というものが存在します。OTCA Metapixel は（メタ）セルのオンとオフの状態が視覚的に分かる特殊なパターンで、ライフゲームのみならず outer totalistic なルール[1]で動く全ての[2]２次元セルオートマトンを再現できます。 つまり、ライフゲームの中で動くライフゲームを見ることができます。 こちらは有名な動画ですが、実際にこういう計算が可能になり
暗号の歴史と現代暗号の基礎理論（RSA, 楕円曲線）-前半- - ABEJA Tech Blog
はじめに このブログに書かれていること 自己紹介 注意 Part1 古典暗号 2つの暗号方式 スキュタレー暗号 アルゴリズムと鍵 シーザー暗号 原理 頻度分析 アルベルティ暗号 ヴィジュネル暗号 如何にしてヴィジュネル暗号は破られたか Part2 近代暗号 エニグマ エニグマの登場 エニグマの基本構造 如何にしてエニグマは突破されたか 前提条件 必ず異なる文字に変換される性質を利用 ループを利用 まとめ 参考文献 採用情報 はじめに このブログに書かれていること 前半 古代暗号から始まる暗号の歴史 エニグマの構造と解読法について 後半（後半ブログは こちら） RSA暗号の基本 楕円曲線暗号の基本 自己紹介 こんにちは！株式会社ABEJAの @Takayoshi_ma です。今回のテックブログですが、ネタに5時間程度悩んだ挙句、暗号を取り上げることにしました！暗号化手法の解説にとどまらず、そ
アタリ・ポンの回路 - k-igrsの日記
アタリのポンは1972年に発表された。設計者はアラン・アルコーン。 汎用CPUがない時代なので(intelの8008が1972年)TTLロジックで構成されている。 オブジェクトの移動、当たり判定、得点表示、フィールド描画等をすべて論理回路で実現している。 ポンの回路を解析している人がいてその説明からどのようにゲームを実現しているか見てみる。 参考にしたpdfファイル。 http://www1.cs.columbia.edu/~sedwards/papers/edwards2012reconstructing.pdf ポンは 二人用ゲーム パドルを操作してボールを打ち合い相手がミスをしたら得点 という単純なもの。ゲーム画面は Wikipediaポンより 画面から 左右にプレイヤーが操作するラケットがあり上下に移動する ボールはラリーによって左右に移動する 画面上部に得点が描画されている 画面
RSAの終わりの始まり - 暗号移行再び - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 前振り 全国の暗号を使うエンジニアの皆さんこんにちは。今日は暗号移行とRSA暗号の話をしたいと思います。まず暗号を利用している皆さんであればCRYPTRECの「電子政府推奨暗号リスト」のことはご存じですよね！（言い切るw） CRYPTRECから2022年7月（昨年夏）に暗号強度要件（アルゴリズム及び鍵長選択）に関する設定基準（PDF直リンク）が公開されました。この中では暗号のセキュリティ強度で各種暗号と鍵長が整理されています。セキュリティ強度はビットセキュリティと呼ばれるビットサイズ（共通鍵暗号の場合のビット長）で区分されます。暗号アル
ヒープについてわかりやすく解説してみた – Yasufumi Taniguchi – Medium
基本的なデータ構造であるヒープについて、概要、計算量と実装、そして最もシンプルな応用であるヒープソートを紹介します。MITが講義や資料を公開しているMIT OpenCourseWareのアルゴリズムとデータ構造の講義 が非常にわかりやすかったので、その内容に沿ってまとめました。この記事ではHeaps and Heap Sortの内容を以下の順序で解説します。 ヒープの概要ヒープの表現ヒープの構築ヒープの計算量ヒープの実装ヒープソート1. ヒープの概要ヒープ (heap) は優先度付きキュー (priority queue) の実装の1つです。優先度付きキューは集合 (set) を扱うデータ型で、集合に含まれる要素が何らかの優先度 (priority) 順に取り出されるという特徴を持っています。学会のポスター発表を回るときや、旅行先での観光地巡りでは、優先度に基づいて要素を取り出すことが重要
クッキークリッカーで学ぶアルゴリズム入門 : あすなろの雑記
0. 目次 1. クッキークリッカーとは? 2. クッキークリッカー100万枚RTA 3. 解答? 4. 解答 5. 余談 6. おわりに 1. クッキークリッカーとは? 皆さんはクッキークリッカーというゲームをご存じでしょうか？ 2013年に公開され同年に日本でも爆発的に流行を見せたゲームです。知らないよという方もご安心ください、最初の方だけですがざっくり説明します。 上の画像がプレイ画面です。左にあるクッキーをクリックします。 クッキーが1枚焼けました。やったね。 クッキーが15枚貯まりました、右側にあるカーソルをクリックしてみます。 指はどこだ！？ クッキーの周りにある指が10秒に1回クッキーをクリックしてくれます。助かるー。 100枚貯まりました。アップグレード「強化された人差し指」を買ってみます。 クッキーの上に、クリックした回数分「+2」と書かれています 1回のクリックでクッキ
テキストエディタで使われがちなデータ構造 Piece Table の概要と実装 - A Memorandum
テキストエディタのデータ構造 Gap method Piece Table method Piece Table の構造 Piece Table の実装 Piece Table のメソッド まとめ テキストエディタのデータ構造 テキストエディタで採用されているデータ構造にはいろいろあります。 こちらの論文 Data Structures for Text Sequences では各種データ構造について比較検討されています。 多くは、Gap method や Piece table method をベースにしたものが多いのではないでしょうか(図で言う最下部の中心の丸印に当たります)。最近では Rope なども有名ですね。 Gap method Gap method では、現在のカーソル位置で、テキストバッファを2つに分割し Gap を間に挟み、カーソル位置に対する編集(テキスト追加/削除)を
仕事で出会ったアルゴリズムたち - estie inside blog
こんにちは。@kenkoooo です。 教科書に載っているようなアルゴリズムって勉強しても仕事では全然使わない、と見せかけて意外と使うなぁと感じたので、仕事で見たことがあるアルゴリズムをいくつか紹介します。 広告を配信したい！ あなたはウェブサービスの会社で働いています。サービス利用者のユーザーに広告を配信することで、広告主からお金をもらっています。 あなたは今から広告主からもらった広告をユーザーに配信します。 広告主が 社います。 広告主 は広告を 人に配信したいです。 配信対象となるユーザーが 人います。 ユーザー は広告主 の広告は受け取りを許可しています。 ユーザー は、合計 件までしか広告を受け取りたくないです。 上記のような条件の中で、どのように広告を配信したら良いでしょうか？ 条件を整理する 条件を整理してみましょう。 各ユーザーごとに、受け取りを許可している広告主がいます。
40年越しにTCPの仕様(RFC793)が改訂される RFC9293 - ASnoKaze blog
2022/08/09 追記 「RFC 9293 Transmission Control Protocol (TCP)」として正式なRFCが出ました TCPのコア部分の仕様は1981年に発行された「RFC793 TRANSMISSION CONTROL PROTOCOL」で標準化されています。 この、RFC793の改訂版となる「Transmission Control Protocol (TCP) Specification」は、2013年からIETFのTCPM WGで議論されてきましたが、4月4日にIESGによって承認されました(参考URL)。現在はRFC出版の準備に入っています(新しいRFC番号はこの後正式に決まります) www.ietf.org 改めてTCPの仕様を読みたい場合はこのドキュメントを読むのが良さそう。 概要 この改訂版の仕様(通称 rfc793bis)は、RFC793が
Gödel's Incompleteness Theorem, in Bash
Gödel’s first incompleteness theorem states that there are mathematical statements that can neither be proven or disproven. His proof is fairly difficult to understand - it involves prime numbers, factorization, all this number theory. Gödel’s proof had to be complicated because in 1931, computer algorithms hadn’t really been invented. Turing machines would only be invented in 1936, five years lat
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
【実践】エンジニアの基礎教養-アルゴリズムを学べる本
何でも微分する
