sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.32k stars 453 forks source link

Need a function to calculate the Hamming weight of Boolean functions #37754

Open 10v1 opened 5 months ago

10v1 commented 5 months ago

Problem Description

sage: B = random_boolean_function(28) sage: %time sum(B.truth_table()) CPU times: user 4.16 s, sys: 388 ms, total: 4.54 s Wall time: 4.55 s 134213651



### Proposed Solution

For Boolean functions, we can calculate the sum of the truth table in the Cython layer to avoid constructing python list. 

For Boolean polynomials, we can convert them to Boolean functions through Mobius transform, and then use the method above. Specifically, when the Boolean polynomials are sparse, the Algorithm 2 of https://dx.doi.org/10.1007/978-3-030-84252-9_9 is much more efficient.

### Alternatives Considered

https://dx.doi.org/10.1007/978-3-642-30615-0_8 also provide a method to calculate the Hamming weight of Boolean polynomials.

### Additional Information

_No response_

### Is there an existing issue for this?

- [X] I have searched the existing issues for a bug report that matches the one I want to file, without success.
10v1 commented 5 months ago

I have written some code during my study (expect a PR soon).

The calculation of Hamming weight is 1000x faster than the current method.

sage: B = random_boolean_function(28)
sage: %time B.hamming_weight()
CPU times: user 4.42 ms, sys: 64 µs, total: 4.48 ms
Wall time: 4.5 ms
134213651

For sparse Boolean polynomials, I have practically calculated the Hamming weight of some polynomials with more than 64 variables, and about 2^16 terms.