15
\$\begingroup\$

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 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
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Suggested test case with a>1: 5x²+116x+209 -> x=25 \$\endgroup\$
    – Arnauld
    Jul 28, 2023 at 16:19
  • \$\begingroup\$ I'm from a math background, and is this not equivalent to factoring in F2 after a reduction map? \$\endgroup\$
    – user118161
    Jul 29, 2023 at 0:48
  • \$\begingroup\$ math.stackexchange.com/questions/877682/… @bsoelch, a reduction map is basically the concept of "taking mod 2" \$\endgroup\$
    – user118161
    Jul 29, 2023 at 8:52
  • \$\begingroup\$ @user118161 It seems like taking everything "mod 2" preserves the solutions, but considering that the reduction maps different polynomials to the same value (e.g. (x+2)(x+2) and ) I doubt it is an equivalence. Note that the "numbers" in this problem are just a shorthand notation for polynomials in F2[y] (2 means y not 1+1) \$\endgroup\$
    – bsoelch
    Jul 29, 2023 at 9:43

7 Answers 7

4
\$\begingroup\$

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 ).

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)
\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Jul 29, 2023 at 19:19
  • 2
    \$\begingroup\$ I don't know Haskell but I think you might be able to write (a!x!x)%(b!x)%c as a!x%b!x%c which would save you 7 bytes. \$\endgroup\$
    – Neil
    Jul 30, 2023 at 7:13
  • \$\begingroup\$ @Neil I don't think so. a!x isn't equal to a!x!x, and it needs the parentheses. But now I'm thinking x!(a!x%b)%c would work and save 4 bytes. \$\endgroup\$ Jul 30, 2023 at 7:42
  • \$\begingroup\$ But x!(...) equals (...)!x, and then I think you can remove the ()s, giving my original expression. \$\endgroup\$
    – Neil
    Jul 30, 2023 at 7:46
  • \$\begingroup\$ (Also I've obviously miscounted and it's only a total of 6 bytes saved.) \$\endgroup\$
    – Neil
    Jul 30, 2023 at 7:47
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 57 bytes

F³⊞υ⌕A⮌⍘N²1W⊙E⟦⌕A⮌⍘ⅈ²1⟧⁺§υ²∧κΣEκ⁺μ⁺§υ¹ΣEκ⁺ξ§υ⁰⊙κ﹪№κμ²M→Iⅈ

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

F³⊞υ⌕A⮌⍘N²1

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

⌕A⮌⍘ⅈ²1

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

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

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

W⊙...⊙κ﹪№κμ²

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

M→

... increment the trial result.

Iⅈ

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ m(m(a))^m(b)^c can be written m(m(a)^b)^c to save 3 bytes. \$\endgroup\$
    – Neil
    Jul 30, 2023 at 7:09
1
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ m[m[a]]^m[b]^c can be written m[m[a]^b]^c to save 3 bytes. \$\endgroup\$
    – Neil
    Jul 30, 2023 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.