Created
January 3, 2025 17:19
-
-
Save tildedave/6ba4429c6c9091fd1d94e835f16f043a to your computer and use it in GitHub Desktop.
Generalized kroneker symbol in Rust with trait params
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
fn kroneker_symbol<T>(a: T, b: T) -> i32 | |
where | |
T: Zero + One + Signed + BitAnd<Output = T> + PartialOrd + Copy, | |
{ | |
let (zero, one, two, three) = ( | |
T::zero(), | |
T::one(), | |
T::one() + T::one(), | |
T::one() + T::one() + T::one(), | |
); | |
let (four, five) = (two + two, three + two); | |
let (six, seven) = (three + three, three + four); | |
let kroneker_table = |x| { | |
if x == zero { | |
0 | |
} else if x == one { | |
1 | |
} else if x == two { | |
0 | |
} else if x == three { | |
-1 | |
} else if x == four { | |
0 | |
} else if x == five { | |
-1 | |
} else if x == six { | |
0 | |
} else if x == seven { | |
1 | |
} else { | |
panic!("impossible") | |
} | |
}; | |
if b == T::zero() { | |
return if a.abs() == T::one() { 1 } else { 0 }; | |
} | |
if is_even(a) && is_even(b) { | |
return 0; | |
} | |
let mut v = T::zero(); | |
let mut a = a; | |
let mut b = b; | |
while is_even(b) { | |
v = v + T::one(); | |
b = b / two; | |
} | |
// a&7 = (-1)^((a^2 - 1)/8) | |
let mut k = if v % two == T::zero() { | |
1 | |
} else { | |
kroneker_table(a & seven) | |
}; | |
if b < T::zero() { | |
b = -b; | |
if a < T::zero() { | |
k = -k; | |
} | |
} | |
loop { | |
assert!(b % two != T::zero()); | |
assert!(b > T::zero()); | |
if a == T::zero() { | |
return if b > T::one() { 0 } else { k }; | |
} | |
v = T::zero(); | |
while is_even(a) { | |
v = v + one; | |
a = a / two; | |
} | |
if !is_even(v) { | |
k = kroneker_table(b & seven); | |
} | |
// reciprocity | |
// (-1)^((a - 1)(b - 1)/4)k | |
if (a & b & two) != T::zero() { | |
k = -k; | |
} | |
let r = a.abs(); | |
a = b % r; | |
b = r; | |
} | |
} | |
fn is_even<T>(x: T) -> bool | |
where | |
T: Zero + One + Rem<Output = T> + PartialEq, | |
{ | |
x % (T::one() + T::one()) == T::zero() | |
} | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment