跳转到内容

std.Random.ziggurat

标准库Zig 0.17.1官方原文
源码std/Random/ziggurat.zig

第 1 行

实现 [ZIGNOR][1],Jurgen A. Doornik,2005 年,牛津大学纳菲尔德学院。

[1]: https://www.doornik.com/research/ziggurat.pdf

以 rust/rand 为参考。

注意:以下内容似乎有意思,但参考代码稍难理解: https://sbarral.github.io/etf。

std.Random.ziggurat.builtin

常量

第 11 行

std.Random.ziggurat.exp_f

函数

第 150 行

pub fn exp_f(x: f64) f64

参数

x: f64

std.Random.ziggurat.exp_f_inv

函数

第 153 行

pub fn exp_f_inv(y: f64) f64

参数

y: f64

std.Random.ziggurat.exp_r

常量

第 147 行

std.Random.ziggurat.exp_v

常量

第 148 行

std.Random.ziggurat.exp_zero_case

函数

第 156 行

pub fn exp_zero_case(random: Random, _: f64) f64

参数

random: Random
_: f64

std.Random.ziggurat.ExpDist

常量

第 142 行

std.Random.ziggurat.math

别名

第 12 行

别名目标 std.math

std.Random.ziggurat.next_f64

函数

第 15 行

pub fn next_f64(random: Random, comptime tables: ZigTable) f64

参数

random: Random
tables: ZigTable

std.Random.ziggurat.norm_f

函数

第 107 行

pub fn norm_f(x: f64) f64

参数

x: f64

std.Random.ziggurat.norm_f_inv

函数

第 110 行

pub fn norm_f_inv(y: f64) f64

参数

y: f64

std.Random.ziggurat.norm_r

常量

第 104 行

std.Random.ziggurat.norm_v

常量

第 105 行

std.Random.ziggurat.norm_zero_case

函数

第 113 行

pub fn norm_zero_case(random: Random, u: f64) f64

参数

random: Random
u: f64

std.Random.ziggurat.NormDist

常量

第 99 行

std.Random.ziggurat.Random

别名

第 13 行

别名目标 std.Random

std.Random.ziggurat.std

别名

第 10 行

别名目标 std

std.Random.ziggurat.ZigTable

容器

第 53 行

字段

r: f64
x: [257]f64
f: [257]f64
pdf: fn (f64) f64
is_symmetric: bool
zero_case: fn (Random, f64) f64

std.Random.ziggurat.ZigTableGen

函数

第 67 行

pub fn ZigTableGen( comptime is_symmetric: bool, comptime r: f64, comptime v: f64, comptime f: fn (f64) f64, comptime f_inv: fn (f64) f64, comptime zero_case: fn (Random, f64) f64, ) ZigTable

参数

is_symmetric: bool
r: f64
v: f64
f: fn (f64) f64
f_inv: fn (f64) f64
zero_case: fn (Random, f64) f64
源码

std/Random/ziggurat.zig

//! 实现 [ZIGNOR][1],Jurgen A. Doornik,2005 年,牛津大学纳菲尔德学院。
//!
//! [1]: https://www.doornik.com/research/ziggurat.pdf
//!
//! 以 rust/rand 为参考。
//!
//! 注意:以下内容似乎有意思,但参考代码稍难理解:
//! https://sbarral.github.io/etf。

const std = @import("../std.zig");
const builtin = @import("builtin");
const math = std.math;
const Random = std.Random;

pub fn next_f64(random: Random, comptime tables: ZigTable) f64 {
    while (true) {
        // 手动由各部分构造浮点数,因为可将未使用的指数用于查找表条目,
        // 从而避免此处额外进行一次随机查找。
        const bits = random.int(u64);
        const i = @as(usize, @as(u8, @truncate(bits)));

        const u = blk: {
            if (tables.is_symmetric) {
                // 生成 [2, 4) 范围内的值,再缩放至 [-1, 1)
                const repr = ((0x3ff + 1) << 52) | (bits >> 12);
                break :blk @as(f64, @bitCast(repr)) - 3.0;
            } else {
                // 生成范围 [1, 2) 中的值,并缩放到 (0, 1)
                const repr = (0x3ff << 52) | (bits >> 12);
                break :blk @as(f64, @bitCast(repr)) - (1.0 - math.floatEps(f64) / 2.0);
            }
        };

        const x = u * tables.x[i];
        const test_x = if (tables.is_symmetric) @abs(x) else x;

        // 等价于 |u| < tables.x[i+1] / tables.x[i](或 u < tables.x[i+1] / tables.x[i])。
        if (test_x < tables.x[i + 1]) {
            return x;
        }

        if (i == 0) {
            return tables.zero_case(random, u);
        }

        // 等价于 f1 + DRanU() * (f0 - f1) < 1
        if (tables.f[i + 1] + (tables.f[i] - tables.f[i + 1]) * random.float(f64) < tables.pdf(x)) {
            return x;
        }
    }
}

pub const ZigTable = struct {
    r: f64,
    x: [257]f64,
    f: [257]f64,

    // 用作回退的概率密度函数
    pdf: fn (f64) f64,
    // 分布是否对称
    is_symmetric: bool,
    // 位于 0 块时的回退计算
    zero_case: fn (Random, f64) f64,
};

// zigNorInit
pub fn ZigTableGen(
    comptime is_symmetric: bool,
    comptime r: f64,
    comptime v: f64,
    comptime f: fn (f64) f64,
    comptime f_inv: fn (f64) f64,
    comptime zero_case: fn (Random, f64) f64,
) ZigTable {
    var tables: ZigTable = undefined;

    tables.is_symmetric = is_symmetric;
    tables.r = r;
    tables.pdf = f;
    tables.zero_case = zero_case;

    tables.x[0] = v / f(r);
    tables.x[1] = r;

    for (tables.x[2..256], 0..) |*entry, i| {
        const last = tables.x[2 + i - 1];
        entry.* = f_inv(v / last + f(last));
    }
    tables.x[256] = 0;

    for (tables.f[0..], 0..) |*entry, i| {
        entry.* = f(tables.x[i]);
    }

    return tables;
}

// N(0, 1)
pub const NormDist = blk: {
    @setEvalBranchQuota(30000);
    break :blk ZigTableGen(true, norm_r, norm_v, norm_f, norm_f_inv, norm_zero_case);
};

pub const norm_r = 3.6541528853610088;
pub const norm_v = 0.00492867323399;

pub fn norm_f(x: f64) f64 {
    return @exp(-x * x / 2.0);
}
pub fn norm_f_inv(y: f64) f64 {
    return @sqrt(-2.0 * @log(y));
}
pub fn norm_zero_case(random: Random, u: f64) f64 {
    var x: f64 = 1;
    var y: f64 = 0;

    while (-2.0 * y < x * x) {
        x = @log(random.float(f64)) / norm_r;
        y = @log(random.float(f64));
    }

    if (u < 0) {
        return x - norm_r;
    } else {
        return norm_r - x;
    }
}

test "normal dist smoke test" {
    // 将种子硬编码为 0,因为可能存在会导致
    // 此测试失败的种子。
    var prng = Random.DefaultPrng.init(0);
    const random = prng.random();

    var i: usize = 0;
    while (i < 1000) : (i += 1) {
        _ = random.floatNorm(f64);
    }
}

// Exp(1)
pub const ExpDist = blk: {
    @setEvalBranchQuota(30000);
    break :blk ZigTableGen(false, exp_r, exp_v, exp_f, exp_f_inv, exp_zero_case);
};

pub const exp_r = 7.69711747013104972;
pub const exp_v = 0.0039496598225815571993;

pub fn exp_f(x: f64) f64 {
    return @exp(-x);
}
pub fn exp_f_inv(y: f64) f64 {
    return -@log(y);
}
pub fn exp_zero_case(random: Random, _: f64) f64 {
    return exp_r - @log(random.float(f64));
}

test "exp dist smoke test" {
    var prng = Random.DefaultPrng.init(0);
    const random = prng.random();

    var i: usize = 0;
    while (i < 1000) : (i += 1) {
        _ = random.floatExp(f64);
    }
}

test {
    _ = NormDist;
}