heh
add rand module to utils
| -rw-r--r-- | src/main.rs | 13 | ||||
| -rw-r--r-- | src/util.rs | 42 |
2 files changed, 42 insertions, 13 deletions
diff --git a/src/main.rs b/src/main.rs index a320762..cd815fb 100644 --- a/src/main.rs +++ b/src/main.rs @@ -86,22 +86,11 @@ impl UnionFind { } } -/// WYRAND -unsafe fn rng() -> u64 { - static mut STATE: u64 = 0; - STATE = STATE.wrapping_add(0x60bee2bee120fc15); - let tmp = (STATE as u128).wrapping_mul(0xa3b195354a39b70d); - let m1 = (tmp >> 64) ^ tmp; - let tmp = m1.wrapping_mul(0x1b03738712fad5c9); - let m2 = ((tmp >> 64) ^ tmp) as u64; - return m2; -} - pub fn karg(graph: &Graph) -> Option<usize> { let mut v = graph.v; let mut s = UnionFind::new(v); while v > 2 { - let i = ((unsafe { rng() as u128 }.wrapping_mul(graph.edges.len() as u128)) >> 64) as u64; + let i = rand::limit::u64(graph.edges.len() as u64); let α = s.find(graph.edges[i.nat()].0); let β = s.find(graph.edges[i.nat()].1); if α == β { diff --git a/src/util.rs b/src/util.rs index d2c4488..9170742 100644 --- a/src/util.rs +++ b/src/util.rs @@ -13,7 +13,7 @@ pub mod prelude { #[allow(unused_imports)] pub(crate) use super::{bits, dang, leek, mat, shucks, C}; pub use super::{ - even, gcd, gt, l, lcm, lt, pa, r, sort, Dir, FilterBy, FilterBy3, GreekTools, + even, gcd, gt, l, lcm, lt, pa, r, rand, sort, Dir, FilterBy, FilterBy3, GreekTools, IntoCombinations, IntoLines, IterͶ, NumTupleIterTools, ParseIter, Printable, Push, Skip, TakeLine, Trunc, TupleIterTools2, TupleIterTools2R, TupleIterTools3, TupleUtils, UnifiedTupleUtils, UnsoundUtilities, Widen, 読む, 読む::Ext, Ͷ, Α, Κ, Λ, Μ, @@ -1388,3 +1388,43 @@ impl<T> Push<T, 1> for T { [self, and] } } + +/// WYRAND based rng's +pub mod rand { + /// WYRAND + pub fn u64() -> u64 { + static mut STATE: u64 = 0; + let tmp = unsafe { + STATE = STATE.wrapping_add(0x60bee2bee120fc15); + (STATE as u128).wrapping_mul(0xa3b195354a39b70d) + }; + let m1 = (tmp >> 64) ^ tmp; + let tmp = m1.wrapping_mul(0x1b03738712fad5c9); + ((tmp >> 64) ^ tmp) as u64 + } + + /// 0..N + pub mod limit { + use crate::Widen; + + pub fn u64(of: u64) -> u64 { + ((super::u64().widen().wrapping_mul(of.widen())) >> 64) as u64 + } + } + + pub fn u32() -> u32 { + u64() as u32 + } + + pub fn u16() -> u16 { + u64() as u16 + } + + pub fn f32() -> f32 { + (1.0 / ((1u32 << 24) as f32)) * ((u32() >> 8) as f32) + } + + pub fn f64() -> f64 { + (1.0 / ((1u64 << 53) as f64)) * ((u64() >> 11) as f64) + } +} |