東大の入試問題をNode.jsに解かせてみた

11月も終わろうとしているのに次男は絶対に布団をかけても直ぐに退けて寝ています。中々鼻水が治りません。こんばんは、@kjunichiです。

はじめに

先日の「東大の過去問をPerlに解かせようとしたらbignumとbigintの違いを知った」をNode.jsで解かせてみた。

事前準備

なんたって、東京大学の問題なので、素のNode.jsでは太刀打ちできません。追加のモジュールが必要になります。

bignumならgmp要らず

以前の「node.jsで大きな数を扱う」の記事では、bigintを紹介しましたが、bigintの場合、gmpがインストールされている必要があります。

これが、インストールされていないと、

make: Entering directory `/root/work/bignum/node_modules/bigint/build'
  CXX(target) Release/obj.target/bigint/bigint.o
../bigint.cc:9:17: fatal error: gmp.h: No such file or directory
 #include <gmp.h>
                 ^
compilation terminated.

とエラーになりモジュールのインストールが出来ません。

しかし、今回使ったbignumモジュールは、外部のライブラリに依存しないので、gmpが入っていなくともインストールできます。

root@0530e4451ffa:~/work/bignum# npm install bignum
-
> bignum@0.9.0 install /root/work/bignum/node_modules/bignum
> node-gyp configure build

make: Entering directory `/root/work/bignum/node_modules/bignum/build'
  CXX(target) Release/obj.target/bignum/bignum.o
  SOLINK_MODULE(target) Release/obj.target/bignum.node
  SOLINK_MODULE(target) Release/obj.target/bignum.node: Finished
  COPY Release/bignum.node
make: Leaving directory `/root/work/bignum/node_modules/bignum/build'
bignum@0.9.0 node_modules/bignum
└── nan@1.2.0
root@0530e4451ffa:~/work/bignum#

Node.jsで問題を解く

var bignum = require('bignum');

var a = bignum.pow(10,210);
var b = bignum.pow(10,10).add(3);
var ans = a.div(b).toString();
console.log("ans = ",ans.length);
console.log("ans = ",ans.charAt(ans.length-1));

bignumモジュールの実装をちょっと眺める

bignum.ccで以下のヘッダファイルの定義あった。

#include <openssl/bn.h>

BN_で始まる関数が、どうやらOpenSSLでの多倍長整数を扱うライブラリらしい

BigNum::BigNum(const v8::String::Utf8Value& str, uint64_t base) : ObjectWrap ()
{
BN_init(&bignum_);
BN_zero(&bignum_);
BIGNUM *res = &bignum_;
const char *cstr = *str;
switch (base) {
case 2:
BN_init(&bignum_);
for (int i = 0, l = str.length(); i < l; i++) {
if (cstr[l-i-1] != '0') {
BN_set_bit(&bignum_, i);
}
}
break;

文字列への変換

BN_bn2dec

nm /usr/local/Cellar/openssl/1.0.1j/lib/libcrypto.dylib|grep BN_init
00000000000371cb T _BN_init

という事で、C言語で使う場合は、libcryptoをリンクして使えば良さそうだ。

まとめ

以前のbigintを紹介した記事を書いている時に気が付けなかったのですが、node.jsはhttpsを標準で扱ったりするのに、2014年すっかり話題になったOpenSSLを使用しており、当然、この内部では大きな素数を判定するなど、大きな数を扱うための関数が用意されています。今回のbignumはこの部分を利用することで、ネイティブモジュールではありますが、bigintのようにgmpライブラリ等の外部のライブラリに依存せず、node.jsが動いている環境であれば、追加のライブラリなしに動くという訳でした。

それにしても、相変わらず今どきのC++なソースは難しく感じる。昨年のウォルマートのメモリーリークの件もあったから、余計の難しく見えるのかもしれないが。。

残念ながら、FFIでこのNode.js付属のOpenSSLの共有ライブラリを叩けば？と思ったのですが、静的にリンクされている(OSX版、Linux版)ようで、node-ffiからは使えませんでした。