01 specification

Convolution F_2^64

Input contains two length-2048 sequences of unsigned 64-bit integers representing elements of F_{2^64}. Print their convolution over F_{2^64}.

Field addition is bitwise xor. Field multiplication is carryless polynomial multiplication over F_2 reduced by P(x) = x^64 + x^4 + x^3 + x + 1.

Input format matches Library Checker convolution_F_2_64: N M, then the N values of a, then the M values of b. Output N+M-1 unsigned 64-bit integers separated by spaces.

minimal Rust solution

use std::io::Read;

fn main() {
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    let mut values = input.split_ascii_whitespace();
    let n: usize = values.next().unwrap().parse().unwrap();
    let m: usize = values.next().unwrap().parse().unwrap();
    let a: Vec<u64> = (0..n).map(|_| values.next().unwrap().parse().unwrap()).collect();
    let b: Vec<u64> = (0..m).map(|_| values.next().unwrap().parse().unwrap()).collect();

    let mut c = vec![0_u64; n + m - 1];
    for i in 0..n {
        for j in 0..m {
            c[i + j] ^= gf_mul(a[i], b[j]);
        }
    }

    for (i, value) in c.iter().enumerate() {
        if i > 0 {
            print!(" ");
        }
        print!("{value}");
    }
}

fn gf_mul(a: u64, mut b: u64) -> u64 {
    let mut product = 0_u128;
    while b != 0 {
        let shift = b.trailing_zeros();
        product ^= (a as u128) << shift;
        b &= b - 1;
    }
    gf_reduce(product)
}

fn gf_reduce(product: u128) -> u64 {
    let low = product as u64;
    let high = (product >> 64) as u64;
    let mut reduced = low ^ high ^ (high << 1) ^ (high << 3) ^ (high << 4);
    let carry = (high >> 63) ^ (high >> 61) ^ (high >> 60);
    reduced ^= carry ^ (carry << 1) ^ (carry << 3) ^ (carry << 4);
    reduced
}

02 scope / runtime over time

03 leaderboard

Leaderboard · top 3 click any row to expand · open multiple to compare

Leaderboard:

Rank User Lang Best · ms Position in CDF Delta

04 submit

Your Solution

Single File

use std::io::Read;

fn main() {
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    let mut values = input.split_ascii_whitespace();
    let n: usize = values.next().unwrap().parse().unwrap();
    let m: usize = values.next().unwrap().parse().unwrap();
    let a: Vec<u64> = (0..n).map(|_| values.next().unwrap().parse().unwrap()).collect();
    let b: Vec<u64> = (0..m).map(|_| values.next().unwrap().parse().unwrap()).collect();

let mut c = vec![0_u64; n + m - 1];
    for i in 0..n {
        for j in 0..m {
            c[i + j] ^= gf_mul(a[i], b[j]);
        }
    }

for (i, value) in c.iter().enumerate() {
        if i > 0 {
            print!(" ");
        }
        print!("{value}");
    }
}

fn gf_mul(a: u64, mut b: u64) -> u64 {
    let mut product = 0_u128;
    while b != 0 {
        let shift = b.trailing_zeros();
        product ^= (a as u128) << shift;
        b &= b - 1;
    }
    gf_reduce(product)
}

fn gf_reduce(product: u128) -> u64 {
    let low = product as u64;
    let high = (product >> 64) as u64;
    let mut reduced = low ^ high ^ (high << 1) ^ (high << 3) ^ (high << 4);
    let carry = (high >> 63) ^ (high >> 61) ^ (high >> 60);
    reduced ^= carry ^ (carry << 1) ^ (carry << 3) ^ (carry << 4);
    reduced
}