はじめに
2020/11/10 に .NET 5 がリリースされました。 🎉
何気なく MSDN を見ていると、結構便利なメソッドがちょくちょく追加されていることに気づいたので、擬似乱数の実装(または、何らかの数学的処理や黒魔術)で役立ちそうなものを実例と合わせてピックアップして紹介します。加えて、古い環境で悲しみを背負った場合のために、代替実装もできる限り載せておきたいと思います。
普段が .NET Standard 2.0 だったり果ては .NET Framework 4.5.2 だったりする民なので、最新環境の方からすれば既知の情報が多いかもですがご容赦ください。 また、.NET 5 に限らず、比較的新しめ[要出典]の .NET Core 3.0 あたりで追加されたものについても取り上げていきます。
System.Math
数学ライブラリ System.Math にもいくつか追加があります。
BigMul (.NET 5)
public static ulong BigMul (ulong a, ulong b, out ulong low);
a * b
を 128 bit で計算して、上位 64 bit (と out 引数で下位 64 bit) を返します。
使用例としては、 64 bit の乱数を 0 <= x < max
の範囲に加工するときが挙げられます。
// Next() は ulong (64 bit) の乱数を返すものとします // [0, max) の乱数を得ます static ulong Next(ulong max) => Math.BigMul(Next(), max, out _);
どうしてこれが成り立つのかは、小数点以下 64 bit の固定小数点数に見立ててみると分かりやすいです。
Next() / 2^64
は 0 <= x < 1
となるので、それに max
を掛ければ 0 <= x < max
が得られるというわけです。上位 64 ビットだけ取り出すことで / 2^64
の部分と同じ効果が得られます。
*1
上の例のように、コストの重い除算や剰余算の代替として使える場合があります。 *2 そこそこ使う割に実装しようとすると面倒なので、標準で採用されて本当にうれしいです。
代替実装の例を以下に挙げます。 *3
public static (ulong lo, ulong hi) BigMul(ulong a, ulong b) { ulong ahi = a >> 32, alo = a & uint.MaxValue, bhi = b >> 32, blo = b & uint.MaxValue; ulong tlo = alo * blo; ulong thi = ahi * bhi; ulong tmid = (ahi - alo) * (blo - bhi); long carry = tmid == 0 ? 0 : (long)(ahi - alo) >> 63 ^ (long)(blo - bhi) >> 63; tmid += tlo; if (tmid < tlo) carry++; tmid += thi; if (tmid < thi) carry++; carry <<= 32; ulong lo = tlo + (tmid << 32); if (lo < tlo) carry++; ulong hi = thi + (tmid >> 32) + (ulong)carry; return (lo, hi); }
BitIncrement / BitDecrement (.NET Core 3.0)
public static double BitIncrement (double x);
public static double BitDecrement (double x);
指定した浮動小数点値の次に大きい・小さい値を返します。例えば 1 を渡すと、それぞれ 1.0000000000000002
, 0.9999999999999999
を返します。
乱数生成のほうでは、例えば厳密に 0 <= x < max
の範囲を求めたい際に計算誤差で x == max
となってしまった場合に 1 つ小さくして x < max
を保証する、といった使い方をします。 *4
今までは擬似 union でビットレイアウトを重ねることで、整数として +1/-1 してまた戻す、といった手法で実現していました。
[StructLayout(LayoutKind.Explicit)] internal struct DoubleUint64Union { [FieldOffset(0)] public double d; [FieldOffset(0)] public ulong i; } public static double BitIncrement(double d) { if (double.IsNaN(d) || double.IsInfinity(d)) return d; if (d == 0) return double.Epsilon; var conv = new DoubleUint64Union() { d = d }; if (d > 0) conv.i++; else conv.i--; return conv.d; } public static double BitDecrement(double d) { if (double.IsNaN(d) || double.IsInfinity(d)) return d; if (d == 0) return -double.Epsilon; var conv = new DoubleUint64Union() { d = d }; if (d > 0) conv.i--; else conv.i++; return conv.d; }
FusedMultiplyAdd (.NET Core 3.0)
public static double FusedMultiplyAdd (double x, double y, double z);
x * y + z
を返します。いわゆる積和演算というものです。
一見存在意義が不明そうですが、通常の x * y + z
が (t =) x * y
と t + z
の 2 回丸め処理が入るのに対し、このメソッドでは 1 回だけに抑えることができます。したがって等価な計算ではないため、互いに置き換えると結果が微妙に変わる場合があって注意が必要です。
実用的には、例えば 0.0 <= x < 1.0
の乱数を min <= x < max
に加工する際に FusedMultiplyAdd(x, max - min, min)
などとして使えます。
これについてはソフトウェア的に再現するのが面倒そうです。
他の言語で fma
などとして使われているものを正しく移植する際にも役立ちそうです。
ScaleB (.NET Core 3.0)
public static double ScaleB (double x, int n);
x * 2^n
を返します。こちらも効率的らしいです。 n
には負値も指定できます。
実用的には、64 bit の乱数を 0.0 <= x < 1.0
の浮動小数点数に変換する際に使えそうです。
(ほぼ)等価な演算と合わせて例を載せます。
double NextDouble() => Math.ScaleB(Next() >> 11, -53); // double NextDouble() => (Next() >> 11) * (1.0 / (1ul << 53));
(ちなみに少し試した感じでは、結果はほぼ同じで後者のほうが若干速い気がしました… 環境によるのでしょうか…?)
System.MathF (.NET Core 2.1)
System.Math の float 版です。 Unity の UnityEngine.Mathf とは微妙に文字が違います…
float 版のメソッドを作成する際にキャストが不要になるため便利です。 (結構前からあったようですが気づきませんでした…)
System.BitConverter
Int32BitsToSingle / SingleToInt32Bits (.NET Core 2.0)
public static float Int32BitsToSingle (int value);
public static int SingleToInt32Bits (float value);
float ⇔ int の変換を行います。キャストと違うのは、 浮動小数点数のビット構造 をそのままコピーする点です。
例えば、 SingleToInt32Bits(1f) == 0x3f800000
となります。
今までは BitIncrement の項と同じように擬似 union で得ていました。
実用例としては、整数 (uint/ulong) の出力を浮動小数点数に変換する手法のひとつが知られています。
// returns 0f <= x < 1f float NextFloat() => BitConverter.Int32BitsToSingle(0x3f800000 | NextUint() >> 9) - 1f;
雑に解説すると、ビットパターン 0x3fxXXXXX (x = 8~f) は (1.xXXXXX * pow(2, 0))、すなわち 1.0f <= x < 2.0f
となります。そこから 1 を引いて 0f <= x < 1f
を得ています。
なお、double ⇔ long 版の Int64BitsToDouble
, DoubleToInt64Bits
は昔 (.NET Framework 1.1) から存在しました。なぜ double だけ…とか言いながら float 版の互換実装を用意する必要がなくなりました。
ところで、なぜ float ⇔ uint, double ⇔ ulong ではないのか、と思ったのは私だけではないと信じています… 完全に推測ですが CLS 準拠 のためかと思っています。
System.Buffers.Binary.BinaryPrimitives (.NET Core 2.1)
クラスの存在自体気づいていませんでした…
ReverseEndianness
public static ulong ReverseEndianness (ulong value);
(その他のプリミティブ型も同様)
バイトオーダーを逆転させます (いわゆる BSWAP
です)。 0x0123456789abcdef ⇔ 0xefcdab8967452301 となります。
まれに BSWAP を使ったプログラムを書きたくなったときに便利そうです…? *5
今までは System.Net.IPAddress.HostToNetworkOrder (かその逆) の目的外使用をすることもあったかと思いますが、正式にこちらが使えそうです。ちなみに、普通に実装しようとすると以下のようになります。
ulong ReverseEndianness(ulong x) { x = (x & 0x00ff00ff00ff00ff) << 8 ^ (x >> 8 & 0x00ff00ff00ff00ff); x = (x & 0x0000ffff0000ffff) << 16 ^ (x >> 16 & 0x0000ffff0000ffff); return x << 32 ^ x >> 32; }
ちなみにちなみに、 ReverseEndianness(byte value)
とかいう虚無も存在します。なにもしません。
このクラスには、これ以外にも ReadOnlySpan<byte>
からそれぞれのエンディアンでプリミティブ型を読み込む・書き込むメソッドが用意されています。
System.Half (.NET 5)
16 bit の浮動小数点型です。精度を犠牲にするかわりに、スペースや処理負荷を軽減する際に使う用です。
今のところは別環境との相互運用のためにあるらしく、直接計算はできず、比較や float / double へのキャストのみが行えます。 導入の経緯については 公式のブログ に詳しいです。
ちなみに、まだ half
ではありません。Half
と大文字で書く必要があります。
おわりに
書き終わってみると .NET 5 より前に出ていた API が多いですね… アンテナが低いです…
この記事を要約すると Math.BigMul がうれしい になります。他にも Index/Range や Span, MemoryMarshal.Cast など、便利アイテムが続々追加されているので (例によって .NET 5 よりも前からあるものですが)、興味のある方は調べてみてください。
いつの日か Unity で使えることを願って……
*1:なお、この使い方は厳密には正しい分布が得られないことは注記しておきます。 max が 2 のべき乗でなければわずかに生成確率に偏りが生じます。偏らない改善手法などについては https://www.pcg-random.org/posts/bounded-rands.html が詳しいです。
*2:実測だとあまり変わらない場合もありますが…
*3:Karatsuba 法の勉強もかねて実装したのですが、安直に 4 回乗算する手法のほうがなぜか早くなってつらみを背負っています…?正直あまり自信がないので安直にやったほうがいい気もします
*4:C# ではないですが、Java の Random.doubles(double, double) の実装において見られます。
*5:擬似乱数の出力関数の設計をするときに使っていたことがありました。キャリーによる非線形性は上位ビットに集まりがちなので、これで上下を入れ替えてまんべんなく非線形にしよう、という狙いがありました。例えば bswap(s0 + s1) + s1 など。