Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Sandbox

Post History

60%
+1 −0
Sandbox Product of polynomials modulo 2 in integer representation

posted 2mo ago by celtschk‭  ·  edited 2mo ago by celtschk‭

Article code-golf math
#3: Post edited by user avatar celtschk‭ · 2024-10-13T17:52:05Z (about 2 months ago)
Improved Python code
  • Your task is to implements the product of polynomials modulo 2 $(\mathbb F_2[x]$) in integer representation.
  • ## Background
  • The field $\mathbb F_2$ represents the integers modulo 2, or equivalently, the lowest bit of the binary representation of an integer; it only has the values $0$ and $1$. What I mean with a polynomial modulo 2 (note that this might not be the correct mathematical term) is a polynomial with coefficients from $\mathbb F_2$. Since the coefficients can only be $0$ or $1$, such a polynomial is just a sum of terms of the form $x^n$, for example $x^5+x^2+1$.
  • Multiplying of polynomials modulo 2 can be done by doing normal polynomial multiplication, dropping all terms with even coefficient from the resulting polynomial, and then removing the (odd) factors from the remaining terms.
  • <details>
  • <summary>Example</summary>
  • Take the polynomials $x^4 + x^3 + x$ and $x^3 + x^2 + x + 1$. The normal product of those is
  • $$(x^4 +x^3 + x)(x^3 + x^2 + x +1) = x^7 + 2x^6 + 2x^5 + 3x^4 + 2x^3 + x^2 + x.$$
  • The terms with $x^6$, $x^5$ and $x^3$ have even coefficients and therefore are dropped, and for $x^4$ the odd coefficient is dropped, and therefore the product of those polynomials modulo 2 is
  • $$x^7 + x^4 + x^2 + x$$
  • </details>
  • Now since the coefficients are all either 0 or 1, they can be represented as bits of a (non-negative) integer. To get the integer representation of the polynomial, just interpret it as normal polynomial and evaluate it at $x=2$, for example, the polynomial $x^4 + x^3 + x$ is represented by the number $2^4 + 2^3 + 2 = 26$. For the reverse direction, just represent the number in binary, and read off the coefficients: $26 = 11010_2$ represents the polynomial $1x^4 + 1x^3 + 0x^2 + 1x + 0 = x^4 + x^3 + x$
  • ## Task
  • Your task is to write a function that takes two non-negative integers, interprets them as polynomials modulo 2, and returns the integer representing their product.
  • Your program must handle at least products of polynomials up to degree 14, or equivalently, input numbers from $0$ to $32767$ inclusive.
  • Error handling for invalid input (negative numbers, or non-integers in languages that don't do static typing) is not required.
  • ## Scoring
  • This is code golf, the shortest entry wins.
  • ## Example code
  • Here is an implementation in Python (not golfed) that you can use to compare your results to:
  • ```python
  • def polymul_mod2(m, n):
  • m_digits = [int(d) for d in bin(m)[:1:-1]]
  • n_digits = [int(d) for d in bin(n)[:1:-1]]
  • m_len = len(m_digits)
  • n_len = len(n_digits)
  • polyprod_digits = [0] * (m_len + n_len)
  • for i in range(len(m_digits)):
  • for k in range(len(n_digits)):
  • polyprod_digits[i + k] += m_digits[i] * n_digits[k]
  • return sum(2**k * (polyprod_digits[k] % 2) for k in range(m_len + n_len))
  • ```
  • ## Test cases
  • The following test cases first give the two factors, separated by ` x `, and then the result, separated by ` = `.
  • ```text
  • 0 x 0 = 0
  • 0 x 1 = 0
  • 1 x 1 = 1
  • 2 x 1 = 2
  • 2 x 2 = 4
  • 3 x 2 = 6
  • 3 x 3 = 5
  • 6 x 7 = 18
  • 7 x 6 = 18
  • 8 x 5 = 40
  • 11 x 10 = 78
  • 25 x 15 = 135
  • 26 x 15 = 150
  • 32767 x 32767 = 357913941
  • ```
  • Your task is to implements the product of polynomials modulo 2 $(\mathbb F_2[x]$) in integer representation.
  • ## Background
  • The field $\mathbb F_2$ represents the integers modulo 2, or equivalently, the lowest bit of the binary representation of an integer; it only has the values $0$ and $1$. What I mean with a polynomial modulo 2 (note that this might not be the correct mathematical term) is a polynomial with coefficients from $\mathbb F_2$. Since the coefficients can only be $0$ or $1$, such a polynomial is just a sum of terms of the form $x^n$, for example $x^5+x^2+1$.
  • Multiplying of polynomials modulo 2 can be done by doing normal polynomial multiplication, dropping all terms with even coefficient from the resulting polynomial, and then removing the (odd) factors from the remaining terms.
  • <details>
  • <summary>Example</summary>
  • Take the polynomials $x^4 + x^3 + x$ and $x^3 + x^2 + x + 1$. The normal product of those is
  • $$(x^4 +x^3 + x)(x^3 + x^2 + x +1) = x^7 + 2x^6 + 2x^5 + 3x^4 + 2x^3 + x^2 + x.$$
  • The terms with $x^6$, $x^5$ and $x^3$ have even coefficients and therefore are dropped, and for $x^4$ the odd coefficient is dropped, and therefore the product of those polynomials modulo 2 is
  • $$x^7 + x^4 + x^2 + x$$
  • </details>
  • Now since the coefficients are all either 0 or 1, they can be represented as bits of a (non-negative) integer. To get the integer representation of the polynomial, just interpret it as normal polynomial and evaluate it at $x=2$, for example, the polynomial $x^4 + x^3 + x$ is represented by the number $2^4 + 2^3 + 2 = 26$. For the reverse direction, just represent the number in binary, and read off the coefficients: $26 = 11010_2$ represents the polynomial $1x^4 + 1x^3 + 0x^2 + 1x + 0 = x^4 + x^3 + x$
  • ## Task
  • Your task is to write a function that takes two non-negative integers, interprets them as polynomials modulo 2, and returns the integer representing their product.
  • Your program must handle at least products of polynomials up to degree 14, or equivalently, input numbers from $0$ to $32767$ inclusive.
  • Error handling for invalid input (negative numbers, or non-integers in languages that don't do static typing) is not required.
  • ## Scoring
  • This is code golf, the shortest entry wins.
  • ## Example code
  • Here is an implementation in Python (not golfed) that you can use to compare your results to:
  • ```python
  • def polymul_mod2(m, n):
  • m_digits = [int(d) for d in bin(m)[:1:-1]]
  • n_digits = [int(d) for d in bin(n)[:1:-1]]
  • m_len = len(m_digits)
  • n_len = len(n_digits)
  • p_len = m_len + n_len
  • polyprod_digits = [0] * p_len
  • for i in range(m_len):
  • for k in range(n_len):
  • polyprod_digits[i + k] += m_digits[i] * n_digits[k]
  • return sum(2**k * (polyprod_digits[k] % 2) for k in range(p_len))
  • ```
  • ## Test cases
  • The following test cases first give the two factors, separated by ` x `, and then the result, separated by ` = `.
  • ```text
  • 0 x 0 = 0
  • 0 x 1 = 0
  • 1 x 1 = 1
  • 2 x 1 = 2
  • 2 x 2 = 4
  • 3 x 2 = 6
  • 3 x 3 = 5
  • 6 x 7 = 18
  • 7 x 6 = 18
  • 8 x 5 = 40
  • 11 x 10 = 78
  • 25 x 15 = 135
  • 26 x 15 = 150
  • 32767 x 32767 = 357913941
  • ```
#2: Post edited by user avatar celtschk‭ · 2024-10-12T09:45:15Z (about 2 months ago)
Completed title
  • Product of polynomials modulo 2
  • Product of polynomials modulo 2 in integer representation
#1: Initial revision by user avatar celtschk‭ · 2024-10-12T09:44:35Z (about 2 months ago)
Product of polynomials modulo 2
Your task is to implements the product of polynomials modulo 2 $(\mathbb F_2[x]$) in integer representation.

## Background

The field $\mathbb F_2$ represents the integers modulo 2, or equivalently, the lowest bit of the binary representation of an integer; it only has the values $0$ and $1$. What I mean with a polynomial modulo 2 (note that this might not be the correct mathematical term) is a polynomial with coefficients from $\mathbb F_2$. Since the coefficients can only be $0$ or $1$, such a polynomial is just a sum of terms of the form $x^n$, for example $x^5+x^2+1$.

Multiplying of polynomials modulo 2 can be done by doing normal polynomial multiplication, dropping all terms with even coefficient from the resulting polynomial, and then removing the (odd) factors from the remaining terms.

<details>
<summary>Example</summary>
Take the polynomials $x^4 + x^3 + x$ and $x^3 + x^2 + x + 1$. The normal product of those is
$$(x^4 +x^3 + x)(x^3 + x^2 + x +1) = x^7 + 2x^6 + 2x^5 + 3x^4 + 2x^3 + x^2 + x.$$
The terms with $x^6$, $x^5$ and $x^3$ have even coefficients and therefore are dropped, and for $x^4$ the odd coefficient is dropped, and therefore the product of those polynomials modulo 2 is
$$x^7 + x^4 + x^2 + x$$
</details>

Now since the coefficients are all either 0 or 1, they can be represented as bits of a (non-negative) integer. To get the integer representation of the polynomial, just interpret it as normal polynomial and evaluate it at $x=2$, for example, the polynomial $x^4 + x^3 + x$ is represented by the number $2^4 + 2^3 + 2 = 26$. For the reverse direction, just represent the number in binary, and read off the coefficients: $26 = 11010_2$ represents the polynomial $1x^4 + 1x^3 + 0x^2 + 1x + 0 = x^4 + x^3 + x$

## Task

Your task is to write a function that takes two non-negative integers, interprets them as polynomials modulo 2, and returns the integer representing their product.

Your program must handle at least products of polynomials up to degree 14, or equivalently, input numbers from $0$ to $32767$ inclusive.

Error handling for invalid input (negative numbers, or non-integers in languages that don't do static typing) is not required.

## Scoring

This is code golf, the shortest entry wins.

## Example code

Here is an implementation in Python (not golfed) that you can use to compare your results to:

```python
def polymul_mod2(m, n):
    m_digits = [int(d) for d in bin(m)[:1:-1]]
    n_digits = [int(d) for d in bin(n)[:1:-1]]
    m_len = len(m_digits)
    n_len = len(n_digits)
    polyprod_digits = [0] * (m_len + n_len)
    for i in range(len(m_digits)):
        for k in range(len(n_digits)):
            polyprod_digits[i + k] += m_digits[i] * n_digits[k]
    return sum(2**k * (polyprod_digits[k] % 2) for k in range(m_len + n_len))
```

## Test cases

The following test cases first give the two factors, separated by ` x `, and then the result, separated by ` = `.

```text
0 x 0 = 0
0 x 1 = 0
1 x 1 = 1
2 x 1 = 2
2 x 2 = 4
3 x 2 = 6
3 x 3 = 5
6 x 7 = 18
7 x 6 = 18
8 x 5 = 40
11 x 10 = 78
25 x 15 = 135
26 x 15 = 150
32767 x 32767 = 357913941
```