Solve quadratic equations when 1+1=0

Question

There already have been multiple challenges about carryless multiplication, this challenge will work with the same calculation rules.

You task is given a quadratic polynomial ax²+bx+c, to find an integer r such that a*r*r+b*r+c is zero, with + meaning exclusive or and * being carryless multiplication (use xor to add up the numbers in binary long multiplication).

Input: Polynomial ax²+bx+c for instance given as an coefficient vector

Goal: find a number r such that a*r*r+b*r+c=0 with * being multiplication without carry and + being exclusive or.

Rules:

• You may assume there is an integral solution
• You only need to return a single solution of the equation
• The returned solution may be different if the program is called multiple times
• This is code-golf the shortest solution (per language) wins

Examples:

x²+x         -> x=0 or x=1
x²+3x+2      -> x=1 or x=2
x²+5         -> x=3
x²+7x+12     -> x=3 or x=4
5x²+116x+209 -> x=25
x²+12x+45    -> x=5 or x=9

Answer 1

05AB1E, 30 28 bytes

àÝʒUεXN.DNFV0sbv·yY*^}}}.«^_

Takes a reversed polynomial triplet as input (if this is not allowed, a single R can be added between the Uε).

Try it online or verify all test cases.

Explanation:

0sbv·yY*^} is taken from my answer for one of the resulted challenges.

à               # Push the maximum of the (implicit) input-list
 Ý              # Pop and push a list in the range [1,max]
  ʒ             # Filter this list by:
   U            #  Pop and store the current value in variable `X`
   ε            #  Map over the (implicit) input-list of the reversed polynomial
                #   (implicitly push the current polynomial integer of the map)
    XN.D        #   Push the 0-based map-index amount of copies of value `X`
    NF          #   Loop the 0-based map-index amount of times:
      V         #    Pop and store the current top value in variable `Y`
      0         #    Push a 0
       s        #    Swap so the next value is at the top of the stack
        b       #    Convert it to a binary-string
         v      #    Pop and loop over each of its bits `y`:
          ·     #     Double the current value
           y    #     Push the current bit `y`
            Y*  #     Multiply it to value `Y`
              ^ #     Bitwise-XOR the two together
         }      #    Close the foreach-loop
     }          #   Close the ranged loop
   }            #  Close the map
    .«          #  Reduce the list by:
      ^         #   Bitwise-XOR
       _        #  Check if the final result is 0
                # (after which the filtered list is output implicitly as result)

Answer 2

Haskell, 108 102 101 bytes

import Data.Bits
a%b=xor a b
0!_=0
a!b=(2*div a 2!b)%(mod a 2*b)
f a b c=head[x|x<-[0..],1>a!x%b!x%c]

Try it online!

Answer 3

PARI/GP, 90 bytes

a->[subst(lift(t-x),y,2)|t<-factor(Pol([Pol(Mod(binary(i),2),y)|i<-a]))[,1],deriv(t,x)==1]

Attempt This Online!

Coverts the input to a polynomial in \$\mathbb{F}_2[y][x]\$, and then factors it to find the roots.

Answer 4

Python3, 338 bytes:

E=enumerate
def C(a,b):
 d={}
 for x,A in E(a[::-1]):
  for y,B in E(b[::-1]):
   if'11'==A+B:d[x+y]=int(d.get(x+y,0)==0)
 return''.join(str(d.get(i,0))for i in range(0,max(d or[0])+1))[::-1]
def f(p):
 r=0;A,B=bin(p[0])[2:],bin(p[1])[2:]
 while 1:
  if p[2]==int(''.join(C(C(A,J:=bin(r)[2:]),J)),2)^int(''.join(C(B,J)),2):return r
  r+=1

Try it online!

Answer 5

Charcoal, 57 bytes

Ｆ³⊞υ⌕Ａ⮌⍘Ｎ²1Ｗ⊙Ｅ⟦⌕Ａ⮌⍘ⅈ²1⟧⁺§υ²∧κΣＥκ⁺μ⁺§υ¹ΣＥκ⁺ξ§υ⁰⊙κ﹪№κμ²Ｍ→Ｉⅈ

Attempt This Online! Link is to verbose version of code. Explanation:

Ｆ³⊞υ⌕Ａ⮌⍘Ｎ²1

Read in the three coefficients, then decompose them as a sum of powers of 2.

⌕Ａ⮌⍘ⅈ²1

Decomposing the trial result as a sum of powers of 2, ...

Ｅ⟦...⟧⁺§υ²∧κΣＥκ⁺μ⁺§υ¹ΣＥκ⁺ξ§υ⁰

... compose the decomposed values together by matrix sum, then flatten and join the matrices together, ...

Ｗ⊙...⊙κ﹪№κμ²

... and while any power of two appears an odd number of times, ...

Ｍ→

... increment the trial result.

Ｉⅈ

Output the final result.

By representing an integer as a list of powers of 2, the sum of integers is equivalent to the concatenation of the lists with duplicates removed, while the product of integers is equivalent to the Cartesian product of the lists, where each entry is reduced by sum, and then duplicates removed (note that in both cases triplicates become single entries). However it's not actually necessary to remove the duplicates, merely to check that there would be no left over entries.

I don't know whether there's a mathematical or computing term for creating an N-dimensional matrix where each entry is the sum of the relevant entries of N vectors, but numpy.add.outer performs the equivalent operation when N=2.

Answer 6

JavaScript (ES6), 63 bytes

-3 bytes thanks to @Neil

(a,b,c)=>(g=r=>(m=n=>n&&n%2*r^2*m(n>>1))(m(a)^b)^c?g(r+1):r)(0)

Try it online!

Commented

(a, b, c) =>  // input triplet (a, b, c)
( g = r => (  // g is a recursive function taking r
  m = n =>    // m is a recursive function taking n and
              // computing the carryless multiplication n * r
  n &&        //   stop if n = 0
  n % 2 * r ^ //   otherwise XOR the LSB of n multiplied by r
  2 *         //   with twice the result of
  m(n >> 1)   //   a recursive call with floor(n / 2)
)(m(a) ^ b)   // compute ((a * r) XOR b) * r
^ c           // XOR it with c
?             // if the result is not 0:
  g(r + 1)    //   try again with r + 1
:             // else:
  r           //   stop and return r
)(0)          // initial call to g with r = 0

Answer 7

Ruby, 68 65 bytes

Utilizes the multiplication function from Arnauld's JavaScript answer. -3 bytes from @Neil.

->a,b,c{(0..).find{|x|m=->a{a>0?a%2*x^2*m[a/2]:0}
m[m[a]^b]^c<1}}

Attempt This Online!