プログラミング言語ごとの多倍長整数の取り扱い
ぼくにはプログラミング言語に求める基本的な機能がある。
その一つが多倍長整数（演算）である。だから、基本的には多倍長整数族の言語が好きなのだ。多倍長整数が当たり前ってのが、とくにね。Common Lisp とか Python とかね。好きだね。そもそもこれが言語機能に存在しないプログラミング言語というものはひ弱に思われる。もっとも多倍長整数なんて必要ないという人が多数派だよね。わかってる。でも、やっぱり、多倍長整数ができないってのはね ．．。
そこでこんかいは、Julia、Go、D、Rust、Nim、Free Pascal、FreeBASIC のそれぞれでで多倍長整数がどうなっているのか調べてみよう。
まず Julia だけど、これはいい言語だね。Julia については語りたいことは多いけど、こんかいは多倍長整数がテーマだ。さて、Julia には factorial という組込関数がある。まずはそれを試してみよう。
factorial(100) でオーバーフローだ。そこでこれだ。
julia> factorial(big(100))
9332621544394415268169923885626670049071596826438162146859296389521759
9993229915608941463976156518286253697920827223758251185210916864000000
000000000000000000
無事計算できたぞ。以下、factorial(big(1000)) も同様にうまく行く。
もし、独自に関数をつくって多倍長整数に対応させたければ、以下のようにすればよい。
function fact(n)
if n == 0
big(1)
else
n * fact(n - 1)
end
end
そして fact(1000) とすればよい。Python に近い使い心地だけど、やはり、ちょっとだけだけど工夫が必要なんだ。ぼくは気付かなかったけど、使う人によっては Python とは雲泥の差と感じるようなんだ。
じゃ、つぎは Go だ。
Go はぼくにとって最も信頼できるコンパイラ言語の一つなんだ。ただ、それでもね、矛盾するようだが、あまり使う気にならないだよなぁ。多倍長整数の仕様もその理由の一つだね。
だけど、Go の信頼できるスタンドアロンの exe は使わなきゃもったいない。それに、ぼくはこういうシンプルな言語を求めていたはずなんだ。それがねぇ。
で、Go の場合の多倍長整数は import "math/big" で準備ＯＫ。以下のプログラムはずいぶん前にぼくが作ったものだが、動いたかなぁ（笑）。しーらないっと。でも、多倍長整数の使い方はわかるよね。しかし、それにしても何でこんな仕様かというと、その原因は GNU Multiple Precision Arithmetic Library にあるのだろう。それと、Go はオーバーロードができないということか。それで、こんなに醜くなってしまうとしたら、やっぱり必要な機能なんだね。
package main
import (
"fmt"
"strconv"
"math/big"
)
func isPrime(n *big.Int) bool{
isPrime := n.ProbablyPrime(50) // 20 で十分かも
return isPrime
}
func main() {
var s string
fmt.Print("メルセンヌ数を素数判定する n を入力せよ（2^n - 1）： ")
fmt.Scanln(&s)
m, _ := strconv.ParseInt(s, 10, 64)
one := big.NewInt(1)
two := big.NewInt(2)
mer := big.NewInt(m)
n := new(big.Int).Exp(two, mer, nil)
n.Sub(n, one)
fmt.Println(n)
fmt.Println("素数： ", isPrime(n))
}
↑この仕様を見る限り使う気にはならないんだけどね。でも、何はともあれ、コンパイラ言語が標準で多倍長整数が使えるのは魅力だね。
つぎ、D言語行ってみよう。
D はぼくのお気に入り言語の一つだ。
でもね、それなのにぃ、D は日本語入りソースは utf-8 じゃないとコンパイルエラーだ。で、utf-8 にする。それなのに、DOS窓では日本語が文字化けしちゃうんだ。もちろん文字変換をすればいいだけの話ではあるんだけどね。
多倍長整数の話だったけど、話が出たついでに、ぼくが何を文句を言ってるかってこと。困っている人がいたら以下のようにすればいいよ。（なぜ、"表計算" なのかはわかる人にはわかるよね）
import std.stdio;
import std.file;
import std.string;
import std.conv;
import std.windows.charset;
string tosjis(string u){return to!(string)(toMBSz(u));}
string toutf8(string s){return fromMBSz(toStringz(cast(char[])s));}
void main(){
string utf8 = "あいうえお"; // UTF8
writeln("utf8 : ", utf8);
// UTF8 を Shift-JIS に
writeln("utf8 to sjis : ", tosjis(utf8));
writeln(tosjis("表計算するぞぉ！"));
auto sjis = File("sjis.txt").readln; // あいうえお をS-JISで保存したファイル
writeln("sjis : ", sjis);
// Shift-JIS を UTF8 に
writeln("sjis to utf8 : ", toutf8(sjis));
writeln(tosjis("表計算するぞぉ！"));
}
さて、話を戻して、D の多倍長整数。うん、それが、なかなかいいんだよ。まぁ、我慢できるよ。これなら使う気になるよね。
import std.stdio;
import std.bigint;
void main()
{
BigInt a = "23456789012345678901234567890";
BigInt b = "742072812345678901234567890";
auto c = a * b;
writeln(c);
BigInt p = BigInt(2) ^^ 742072 - 1;
writeln(p);
}
つぎは Rust だ。手短に行こう。
なぜって、ぼくは Rust が好きじゃない。
じゃ、取り上げなきゃいいだろう。まぁ、いい。で、案の上だ。
いろんな仕組みがある言語なのに、で、多倍長整数をやらせたらこのていたらくだ。（Go と変わんない気がするけど ．．）
use num::{BigUint, Zero, One};
use std::mem::replace;
fn fib(n: usize) -> BigUint {
let mut f0: BigUint = Zero::zero();
let mut f1: BigUint = One::one();
for _ in 0..n {
let f2 = f0 + &f1;
f0 = replace(&mut f1, f2);
}
f0
}
println!("fib(1000) = {}", fib(1000));
前にも書いたと思うけど、Rust は学習シームレスからはほど遠い言語。この変態言語め！ いやいや、まじんくん、まちたまえ。将来有望といわれている言語だ。きみが気に入らないからって、そんな言い方はないだろう。
気を取り直して、わが愛する Nim に行きましょう。
こんかい紹介する言語の中でぼくが一番好きなのが、この Nim なんだ。確かにね、コンパイルでぶっ飛んだこともあるけどね。それでも、ぼくは Nim が好き。
まぁ、趣味の人だからそう言えるのだろう。職業プログラマなら、まだ、Nim は使えないだろう。それはわかるよ。
で、まずは Nim の日本語処理の話から。
Nim の日本語を含むソースコードは uft-8 で保存するのがいいのか、shift-jis がいいのか。まぁ、厳密に言えば、uft-8 なんだろうけど、すると、DOS窓に日本語を出すときには shift-jis にコード変換をしなければならない。うん、それで問題ない。ただ、気分がよくない。気分がよくないと言っても↓この程度なんだけどね。
で、取りあえずぼくは、ソースは shift-jis で保存している。その場合は、ある種の漢字の場合に限っては DOS窓で文字化けする。ここで、ある種の漢字とは「―ソЫ噂浬欺圭構蚕十申曾箪貼能表暴予禄兔喀媾彌拿杤歃濬畚秉綵臀藹觸軆鐔饅鷭」のこと。このなかには、みんなもよく使う「表計算」の「表」が入っているね。
で、RAW文字列の r"―ソЫ噂浬欺圭構蚕十申曾箪貼能表暴予禄兔喀媾彌拿杤歃濬畚秉綵臀藹觸軆鐔饅鷭" で出力すれば問題なし。ただし、内部で utf-8 用関数で文字列処理をする場合はあらかじめ uft-8 に変換する必要があるよね。
おっと、多倍長整数がテーマだってことをすっかり忘れていたよ。
Nim の多倍長整数はわかりやすい。以下のコードのなかの 1234567890 は通常の整数の範囲なので、1234567890.initBigInt としているが、もっと数字の桁が多い場合は、"12345678901234567890".initBigInt などとすること。あるいは、常に文字列で与えてもいいよね。
#--------------------------------------
import bigints
var i = 1234567890.initBigInt
while true:
i *= 1234567890
echo i
if i.toString.len > 100: break
#--------------------------------------
上のプログラムを走らせた結果は以下の通り。
C:\_nim>bigint
1524157875019052100
1881676371789154860897069000
2323057227982592441500937982514410000
2867971860299718107233761438093672048294900000
3540705968149597751242378595390670323015412790761000000
4371241896208856100100048221092623586370756606568819264290000000
5396594884482166474814145321212573795589977741475227338905857648100000000
6662462759719942007440037531362779472290810125440036903063319585255179509000000000
8225262591471025795047611436615355477641378922955141680937016996764162077997366010000000000
10154645082248316311927502100842088153631659353603201829685466296589268404251223580523418900000000000
うーん、素晴らしい！ 簡単簡単。
さて、つぎは FreePascal だ。
Free Pascal で多倍長整数をするにはいろんな方法があるようだけど、Free Pascal では、GNU Multiple Precision Arithmetic Library の gmp をオフィシャルなライブラリとして採用しているようだ。
その使用例は以下の通りなのだが、ああ、なんじゃこりゃ。でも、Go や Rust よりはいいと思う。
program gmptest;
{$mode objfpc}
uses gmp;
var
p, q : mpz_t;
i : integer;
begin
mpz_init_set_si(p, 1);
mpz_init_set_si(q, 1);
for i := 1 to 100 do
begin
p := p * i;
q := q * 2;
end;
p := p + q;
mp_printf('%Zd', [@p]);
end.
上のプログラムをコンパイルして、実行した結果は以下の通り。
C:\_pp>fpc gmptest.pp
Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
Copyright (c) 1993-2015 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling gmptest.pp
Linking gmptest.exe
16 lines compiled, 1.6 sec, 66432 bytes code, 4100 bytes data
C:\_pp>gmptest
933262154439441526816992388562667004907159682643816214685929638952
175999932299156089414639761565182862536979208272237582511852121845
14600228229401496703205376
さぁ、こんかいの大トリは FreeBASIC だ。
気付いてみれば、FreeBASIC のバージョンが 1.05.0 になっていた。以前触っていたころは、0.xx だったと思ったが。さてさて、Basic 野郎のぼくとしては、どうしたって、FreeBASIC なんだ。うん、なにが？
ぼくから見ると FreeBASIC は Basic の皮を被った C言語といった感じ。ぼくの好きなプログラミング言語の一つなんだ。
また、ちょっとした試していないから断言はできないけど、この多倍長整数ライブラリは、とても自然で使いやすい。これだったら、仕様面では Python と遜色ないだろう。
''---------------------------------------------------------
#Include "lib/big_integer.bas"
Dim as Bigint a, b
a = "123456789012345678901234567890"
b = "12345678901234567890"
Do
a = a * b
print a
Loop Until Len(Str(a))>100
Sleep
''---------------------------------------------------------
いつものテストプログラムを書いてみた。上のプログラムを実行してみよう。
C:\_bas>fbc bigint.bas
C:\_bas>bigint
+1524157875323883675034293577501905199875019052100
+18816763723536577725090825131463319235514383922198701224860897069000
+232305722891181533285658896508982806450763702875773153342648107111742077337982514410000
+2867971861733704037699097396383673365184800604885499673956725400135253627043136307363852838672048294900000
まぁ、どの言語だって使用するライブラリによるだろうけど、こんかいの例では FreeBASIC の多倍長整数が一番使いやすかったように思う。
なお、一番最初に出てきた顔の画像は、Free Pascal 用の統合環境 Lazarus のロゴだ。気になった人のために。
【Lazarus】http://www.lazarus-ide.org/
実は先日、Delphi 7 を Windows8.1PC にインストしようとしたら互換性がないと怒られた。そこで、Dephi の代わりに Lazarus をインスト。
これ、素晴らしいよ！
