第86回情報処理学会全国大会　第6回中高生情報学研究コンテスト

よこはま市立あざみ野中学校

梶田　光くん(3年生) 

（2024年3月取材）

初等整数論では、オイラー関数などの数論的関数の性質を研究するとき、想定した方程式の解のパターンを数値計算によって予測を立てることが重要である。このとき整数一つ一つに対して素因数分解を行うのは時間がかかるため、エラトステネスの篩などを使用することになる。

既存のライブラリ等はほとんどがRAMに収まる範囲での数値計算を前提としているため、10億程度が数値計算の限界となってしまう。さらに処理時間にも数日を要することが多い。

そこでメモリマップドファイルと区間篩を組み合わせ、予めルックアップテーブルを生成することにより高速で計算ができるライブラリを実装した。これによって事実上SSDの容量が許せば1000京まで計算ができるようになり、処理速度は数分程度まで抑えられた。

※クリックすると拡大します

■今回発表した研究を始めた理由や経緯を教えてください。

学習院大学理学部の飯高茂先生でのゼミにおいて、数論的関数の研究をしていました。

そこでは、数値計算によって解を計算し、その性質を考察するという過程があるのですが、重要となる例外解の範囲が広く(億単位になることもありました)、計算に非常に時間がかかるという問題がありました。

そこで、高速に計算ができる区間篩と、ディスク上のデータの高速な読み書きができるメモリマップドファイルを組み合わせ、ルックアップテーブルのようなものを作ることを考えました。言語は高速だと聞いていたRustを利用することにしました。

■今回の研究にかかった時間はどのくらいですか。

1か月ほどです。

ほとんどがRustについての勉強とプログラムの実装でした。

■今回の研究ではどんなことに苦労しましたか。

Rustの言語仕様を理解することでした。

ドキュメンテーションの例を読んで理解したつもりになっても、実際にプログラムを動かすとコンパイルエラーが発生するということがよく起きました。

特に、所有権やライフタイムなどは、他の言語では見たことがなく、とても難しかったです。

また、利用するライブラリのドキュメンテーションをよく読まずに、実行時エラーに悩まされることもありました。

■「ココは工夫した!」「ココを見てほしい」という点を教えてください。

新しくアルゴリズムを発見し、それを実装したことです。

自然数ごとに因数を2つ記録することで、メモリを抑えながら効率的に素因数分解を記録できるということに気づいたときは、とても嬉しかったです。

他には、Rustのライブラリのソースコードから、内部でunsafeな処理をしていても外部から呼び出しされるメソッドは必ず安全にする、といった考え方を取り入れたりもしました。

■今後「こんなものを作ってみたい!」「こんな研究をしてみたい」と思うことがあれば教えてください。

まずは、ドキュメンテーションなどを整備した後、ソースコードを公開したいです。

長期的な目標としては、僕の研究対象であるオイラー関数の計算において、それに特有の性質を使ったアルゴリズムを考案するなどし、さらに高速化を図れたら良いなと思います。

※梶田くんの発表は、中高生研究賞最優秀賞・文部科学大臣賞を受賞しました。