non vorrei lavorare

2020年度からの小学校プログラミング教育の必修化を親として迎えるブロガーの書く、子供との日常

node.jsでtruncatable primeを試したら、OpenSSLをビルドした件

おはようございます。先週は次男が発熱の為、自分と次男だけ実家で生活していました。幸い次男はインフルエンザは陰性でしたが、なかなか熱が平熱に戻らず、結局、1週間ほど実家で過ごしていました。@kjunichiです。

背景

Mathematicaの公式の以下のツイートで知った。

truncatable primeをnode.jsで計算してみた

node.jsのv10からbigintがサポートされる

以下のQiitaの記事にあるように、node.jsでもbigintがv10以降サポートされ、大きな数も手軽に扱えるように なっている。

qiita.com

愚直な素数判定だと日が暮れても終わらなかった

Wikipediaには計算機で簡単に計算できる]と書いてあるが、真に受けて愚直な実装で試したら、日が暮れても終わらなかった。(三日三晩放置したが、半分も求めることが出来なかった。。。)

ja.wikipedia.org

手っ取り早くネイティブモジュールで時短を図った

そこで、以前の記事を思い出し

https://abrakatabura.hatenablog.com/entry/2014/11/28/175853

このbignumモジュールの素数判定を利用して高速化を図ろうとした。

WindowsではOpenSSLのビルドが必要に!

bignumモジュールのビルドでWindowsではOpenSSLの.libファイルが必要になった。DLLファイルはnode.jsに含まれているが、 Windowsは.libファイルがnpmモジュールのビルドに必要なため、これを用意する必要があった。

OpenSSLのビルドにはPerlが必要となったり、なかなか家族旅行中のSurface Goでの作業では 大変だった。

そう言えば、以前、東京Node学園で大津さんの「祝Node-v10リリース これまでのNodeの振り返り」でもPerlが使われているという話を思い出した。そう、OpenSSLのビルドにはPerlが必要なのだった。

また、とにかく最新のOpenSSLのバージョンで良いわけでもなく、Node.jsで利用している系のバージョンに限定されている模様。 今回は OpenSSL_1_0_2-stable を使用した。 ビルドは

  • INSTALL.W64
  • INSTALL.W32

を参考にすすめ、インストール先をbignumモジュールの参照している openssl-win64 を指定する。

成果物

WindowsはにOpenSSLをビルドした後、macOSLinuxは事前準備なしで

npm i bignum

試行錯誤したままのコードなので、ちょっと恥ずかしいけど。

const bignum = require('bignum')

const cachePrime = {}
let findDigit = 0
let counter = 1
let cacheCounter = 0
let numOfTruncatablePrime = 1

const isPrime = (n) => {
    const bn = bignum(n.toString())
    const r = bn.probPrime(80)
    //console.log(`r = ${r}`)
    return r
}

const getNum = () => {
    if (findDigit > 0) {
        //console.log(cachePrime[findDigit - 1][cacheCounter])
        if (cachePrime[findDigit - 1][cacheCounter] === undefined) {
            return -1
        }
        const sNum = counter.toString() + cachePrime[findDigit - 1][cacheCounter++].toString()
        //console.log(sNum)
        num = BigInt(sNum)
        if (cacheCounter >= cachePrime[findDigit - 1].length) {
            cacheCounter = 0
            counter++
        }
    } else {
        num = BigInt(counter)
        counter++
    }
    if (counter > 9) {
        findDigit++
        //console.log(`findDigit = ${findDigit}, counter = ${counter}`)
        cachePrime[findDigit] = []
        counter = 1
        cacheCounter = 0
    }
    //console.log(`${num}`)
    return num
}

const check = (num) => {
    if (!isPrime(num)) {
        return
    }
    let cnum = num.toString()
    const digit = cnum.length

    console.log(`truncatable prime (${numOfTruncatablePrime++}[${digit}]) : ${num}`)
    cachePrime[digit - 1].push(num)
}

cachePrime[0] = []
while (true) {
    const num = getNum()
    if (num > 0) {
        //console.log(`num = ${num}`)
        check(num)
    } else {
        break
    }
}

参考資料

関連記事

14年前の記事

12年前の記事

7年前の記事

5年前の記事