Skip to content

Instantly share code, notes, and snippets.

@tildedave
Created January 3, 2025 17:19
Show Gist options
  • Save tildedave/6ba4429c6c9091fd1d94e835f16f043a to your computer and use it in GitHub Desktop.
Save tildedave/6ba4429c6c9091fd1d94e835f16f043a to your computer and use it in GitHub Desktop.
Generalized kroneker symbol in Rust with trait params
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