23
\$\begingroup\$

When learning to factorise quadratics in the form \$x^2 + ax + b\$, a common technique is to find two numbers, \$p, q\$ such that

$$pq = b \\ p + q = a$$

as, for such numbers, \$x^2 + ax + b = (x + p)(x + q)\$

You are to take two integers \$a, b \in (-\infty, +\infty)\$ and output the two integers \$p, q\$ such that

$$pq = b \\ p + q = a$$

You may take input in any convenient method and you may assume that a solution always exists.

This is so the shortest code in bytes wins

Test cases

2, -15 -> 5, -3
-22, 85 -> -5, -17
6, -16 -> -2, 8
-8, -240 -> -20, 12
-1, -272 -> 16, -17
17, 16 -> 1, 16
-4, 0 -> 0, -4
3, -54 -> 9, -6
13, 40 -> 8, 5
-29, 198 -> -11, -18
11, -12 -> -1, 12
4, -320 -> 20, -16
4, 4 -> 2, 2
\$\endgroup\$
2

28 Answers 28

10
\$\begingroup\$

Scala 3, 49 44 bytes

a=>b=>(-b*b to b*b)map(p=>a-p->p)find(_*_==b)

Try it onlne!

Takes (a)(b) and returns an Option[(Int, Int)]. It's now a little more inefficient since it goes from \$-b^2\$ to \$b^2\$ instead of \$-|b|\$ to \$|b|\$, including values that \$p\$ and \$q\$ could never be, but it saves 4 bytes.

a => b =>
  (-b*b to b*b)              //Make a range of all possible q's and then some
    map(q => (a - q, q))     //Make a tuple of (p, q)
    find(_ * _ == b)         //Find a pair such that p * q = b
\$\endgroup\$
3
  • \$\begingroup\$ Why doesn't the range -b*b to b work (I tried it on your link and it failed, but without knowing Scala I'm puzzled what could be wrong...)? \$\endgroup\$ Dec 13, 2020 at 17:25
  • \$\begingroup\$ @DominicvanEssen -b*b is guaranteed to be negative, but b could be negative too (Scala doesn't adjust step automatically, it's +1 by default) \$\endgroup\$
    – user
    Dec 13, 2020 at 17:31
  • \$\begingroup\$ Ah, of course! Sorry for the stupid question! \$\endgroup\$ Dec 13, 2020 at 17:38
9
\$\begingroup\$

JavaScript (ES7),  37 36 34  31 bytes

Saved 3 bytes thanks to @tsh

Expects (a)(b).

a=>b=>[b=a/2+(a*a/4-b)**.5,a-b]

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ 31 bytes: a=>b=>[p=a/2+(a*a/4-b)**.5,a-p] \$\endgroup\$
    – tsh
    Dec 13, 2020 at 7:30
  • \$\begingroup\$ @tsh Simpler is better. :-) Thank you. \$\endgroup\$
    – Arnauld
    Dec 13, 2020 at 19:58
9
\$\begingroup\$

Wolfram Language (Mathematica), 23 21 18 bytes

Solve[x x+#2==x#]&

Try it online!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ The output format’s a little convoluted, but it looks like you can remove the x/. \$\endgroup\$ Dec 13, 2020 at 7:06
  • \$\begingroup\$ In addition, since you can take the input in any convenient format, why not choose the input format [x^2-a x+b] instead of [a,b]? \$\endgroup\$ Dec 13, 2020 at 20:51
  • 4
    \$\begingroup\$ @GregMartin That's a bit too finicky for my liking. \$\endgroup\$
    – att
    Dec 13, 2020 at 20:54
  • \$\begingroup\$ I get that for sure ... it seems that people here say "any convenient format" but then are put off by formats like that ... would be nice to have it clarified (for that matter, the same issue for output already came up in earlier comments on this answer!) \$\endgroup\$ Dec 13, 2020 at 23:36
  • \$\begingroup\$ @GregMartin FWIW, I wouldn't consider it valid either; it's like saying "input is in format <full program>" and the solution is just eval. Note that "convenient format" is precisely specified as per the link... \$\endgroup\$
    – ASCII-only
    Dec 14, 2020 at 11:22
7
\$\begingroup\$

Jelly, 5 bytes

1ṭÆrN

Try it online!

Input as a list [b, a].

1ṭ       Append 1 to the input, (resulting in [b, a, 1])
  Ær     find roots of polynomial from little-endian coefficient list,
    N    negate each root.
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Mine was the same, but with ;1 at the start instead \$\endgroup\$ Dec 12, 2020 at 23:40
  • \$\begingroup\$ why 1 instead of 0? \$\endgroup\$ Dec 14, 2020 at 15:02
  • \$\begingroup\$ @MadPhysicist The 1 is the coefficient of the \$x^2\$ term--if it was 0, I'd be left with just a linear function. \$\endgroup\$ Dec 14, 2020 at 18:34
  • 1
    \$\begingroup\$ OIC. I misread/didn't think it through \$\endgroup\$ Dec 14, 2020 at 18:38
6
\$\begingroup\$

Retina 0.8.2, 94 bytes

\d+
$*
^(-?)(1*)(,(-)(?<2>\2(1(1)*))|(?<5>(?<6>1)*),)(?<-6>\2)*$(?(6)1)
$1$.2,$4$1$.5
--

-0
0

Try it online! Link includes test cases. Explanation: \$|p|\$ is captured in $2 and \$|q|\$ is captured in $5, with $6 being a helper balancing group used to verify the multiplication.

\d+
$*

Convert to unary.

^(-?)(1*)

Start by matching the sign of \$a\$, then initially assume \$|p|\$ is no greater than \$|a|\$.

(,(-)(?<2>\2(1(1)*))

If \$b\$ is negative, then we actually end up matching \$|a|\$, and choose \$|q|\$ and overwrite $2 with \$|p|=|a|+|q|\$, so \$|a|=|p|+|q|\operatorname{sgn}(b)\$.

|(?<5>(?<6>1)*),)

Otherwise \$b\$ is positive, so overwrite $5 with \$|q|\$ such that \$|a|=|p|+|q|\operatorname{sgn}(b)\$.

(?<-6>\2)*$(?(6)1)

Ensure \$|b|=|pq|\$.

$1$.2,$4$1$.5

Output \$p = |p|\operatorname{sgn}(a)\$ and \$q = |q|\operatorname{sgn}(ab)\$. We then have \$p+q=|p|\operatorname{sgn}(a)+|q|\operatorname{sgn}(ab)=(|p|+|q|\operatorname{sgn}(b))\operatorname{sgn}(a)=|a|\operatorname{sgn}(a)=a\$ while \$pq=|p|\operatorname{sgn}(a)|q|\operatorname{sgn}(ab)=|pq|\operatorname{sgn}(b)=|b|\operatorname{sgn}(b)=b\$ as desired (where \$\operatorname{sgn}(0)=1\$).

--

-0
0

Fix up extraneous -s.

\$\endgroup\$
6
\$\begingroup\$

Charcoal, 25 bytes

NθNηI⊟ΦE…·±↔η↔η⟦ι⁻θι⟧⁼ηΠι

Try it online! Link is to verbose version of code. Same idea as @user's Scala solution. Explanation:

NθNη

Input \$a\$ and \$b\$.

E…·±↔η↔η

Loop \$p\$ over \$[-|b|,|b|]\$.

⟦ι⁻θι⟧

For each \$p\$ create a list \$(p,q)\$ where \$q=a-p\$.

I⊟Φ...⁼ηΠι

Output the one with the highest \$p\$ where \$pq=b\$.

\$\endgroup\$
6
\$\begingroup\$

Octave, 17 bytes

@(x)-roots([1 x])

Try it online!

You simply need to solve \$x^2 + ax + b = (x + p)(x + q) = 0\$, and \$x_1=-p\$, \$x_2=-q\$.

\$\endgroup\$
6
\$\begingroup\$

Python 3.8, 42 39 37 bytes

Saved 2 bytes thanks to Danis!!!

lambda a,b:[c:=a/2+(a*a/4-b)**.5,a-c]

Try it online!

Port of Arnauld's JavaScript answer.

\$\endgroup\$
2
  • \$\begingroup\$ you can save two bytes by removing the parentheses 37 bytes \$\endgroup\$
    – Danis
    Dec 13, 2020 at 20:42
  • \$\begingroup\$ @Danis Nice one - thanks! :-) \$\endgroup\$
    – Noodle9
    Dec 13, 2020 at 23:22
5
\$\begingroup\$

05AB1E, 17 16 bytes

(Dn4I*-t‚DOsÆ);(

Try it online!

Why oh why aren't there any built-ins for this? This solves the quadratic equation to get the two roots. -1 thanks to @ovs

\$\endgroup\$
3
  • \$\begingroup\$ D(sn can be (Dn or (¹n for -1 byte. \$\endgroup\$
    – ovs
    Dec 13, 2020 at 9:41
  • 4
    \$\begingroup\$ Wow, there is a winking sad face at the end. \$\endgroup\$
    – SunnyMoon
    Dec 13, 2020 at 9:51
  • \$\begingroup\$ Alternative 17-byter. Maybe someone sees a way to golf it further. If outputting an infinite list of pairs is valid (which contains a single pair most likely), I guess it could be 16 bytes. \$\endgroup\$ Dec 14, 2020 at 8:47
4
\$\begingroup\$

Brachylog, 8 bytes

~+ʰ⟨≜×⟩Ċ

Try it online!

Takes input as a list [a,b].

  ʰ         For the first element of the input,
~+          get a list of integers which sum to it
    ≜       (in order of least absolute value of the first element).
   ⟨ ×⟩     Its product is the second element,
       Ċ    its length is 2,
            and it's the output.

I'm not entirely sure why this needs , but it comes at no cost because the "sandwich" construct ⟨~+×⟩ won't parse without braces around ~+ anyhow (and both ⟨{~+}×⟩Ċ and ~+ʰ⟨≡×⟩Ċ would still come out to 8).

\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 28 bytes 24 bytes

thanks to att

#&@@Solve[#-b==a==#2/b]&

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ 24 bytes \$\endgroup\$
    – att
    Dec 13, 2020 at 1:39
4
\$\begingroup\$

dc, 24 bytes

Input is a line of two numbers from STDIN. Output is to STDOUT.

?rdsad*r4*-vla+2/dlar-rf

Try it online!

Explanation

?                        # Read a line of input
 r                       # Swap the two numbers
  dsa                    # Store to `a` w/o popping
     d*                  # Square the 1st input
       r                 # Swap up the second input
        4*               # Multiply by four
          -              # Second-to-top - TOS
           v             # Square root
            la+          # Add by `a`
               2/        # Halve
                 d       # Duplicate
                  lar-   # Push `a` - TOS
                      r  # Swap the top 2 items
                       f # Print entire stack
\$\endgroup\$
4
\$\begingroup\$

Python 3.8 (pre-release), 37 bytes

lambda a,b:[p:=a/2+(a*a/4-b)**.5,a-p]

Try it online!

Python 2, 42 bytes

def f(a,b):p=a/2+(a*a/4-b)**.5;print p,a-p

Try it online!

Takes input as float, and prints the output.

\$\endgroup\$
4
\$\begingroup\$

Husk, 12 bytes

ḟo=¹ΠmSe`-²ṡ

Try it online!

Port of user's Scala answer.

           ṡ    # range of integers from -arg1 to +arg1
     m          # map over each of them
      S         # combining itself
       e        # into a 2-element list with
        `-²     # arg2 minus this;
ḟ               # now find the first element that satisfies
 o              # combine 2 functions:
    Π           # product
  =¹            # equals arg1
\$\endgroup\$
4
\$\begingroup\$

R, 36 35 bytes

function(b,c)b/2+-.5:1*(b^2-4*c)^.5

Try it online!

Uses the Quadratic formula with a=1.

\$\endgroup\$
6
  • 2
    \$\begingroup\$ polyroot(c(b,a,1)) seems shorter. \$\endgroup\$ Dec 14, 2020 at 10:32
  • 1
    \$\begingroup\$ @Xi'an - Really nice! Thanks for introducing me to polyroot and you should post this as your own answer! You can shorten it even more by taking input as a 2-element vector, too: try it... \$\endgroup\$ Dec 14, 2020 at 10:58
  • 2
    \$\begingroup\$ @Xi'an i don't think it's acceptable, since you still have to specify a=1 \$\endgroup\$
    – ASCII-only
    Dec 14, 2020 at 11:34
  • 1
    \$\begingroup\$ @Xi'an - I agree with ASCII-only. You need to be able to 'call' or run your answer using only the input specified in the question. \$\endgroup\$ Dec 14, 2020 at 12:31
  • 1
    \$\begingroup\$ R 4.1 (r-devel) would allow lambda syntax \(x) polyroot(c(1,x)) \$\endgroup\$
    – AlexR
    Dec 15, 2020 at 21:42
4
\$\begingroup\$

C (gcc) -lm, 45 bytes

f(int*a){*a-=a[1]=(*a+sqrt(*a**a-4*a[1]))/2;}

Try it online!

Modifies an input array of 2 ints.


C (gcc), 53 bytes

i;f(int*a){for(i=*a/2;(*a-i)*i-a[1];i--);*a-=a[1]=i;}

Try it online!

Doesn't use sqrt.

\$\endgroup\$
4
\$\begingroup\$

APL (Dyalog Unicode), 28 26 bytes

-2 thanks to Razetime.

{⍺-⎕←(⍺÷2)+.5*⍨⍵-⍨⍺×⍺÷4}

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ -2 \$\endgroup\$
    – Razetime
    Dec 14, 2020 at 7:35
3
\$\begingroup\$

APL (Dyalog Extended), 19 bytes

-2 thanks to @Bubbler

÷∘2⍛{⍺(+,-)√⍵-⍨⍺*2}

Try it online!

\$\endgroup\$
1
3
\$\begingroup\$

Haskell, 46 39 bytes

a!b=[(k,b-k)|k<-[-a*a..],k*b-k*k==a]!!0

Try it online!

Kind of boring, but short.

\$\endgroup\$
3
  • \$\begingroup\$ a!b=[(x,b-x)|x<-[-aa..aa],x*(b-x)==a]!!0 is shorter \$\endgroup\$
    – user100177
    Jan 3, 2021 at 20:41
  • \$\begingroup\$ @user100177 a!b=[(k,b-k)|k<-[-a*a..],k*b-k*k==a]!!0 is even shorter. \$\endgroup\$
    – Wheat Wizard
    Jan 4, 2021 at 0:09
  • \$\begingroup\$ Good find, I didn't think about an infinite list. It's just as short as mine now, actually. \$\endgroup\$
    – user100177
    Jan 7, 2021 at 15:16
3
\$\begingroup\$

convey, 113 bytes

v<1
>>>v 0
{?>*"-"v
4*  "vvv
 v  >*vv
v#<<<<vv
-<    vv
*%2   v>v
.1    v}>v
v     v%2v}%2
">>>>>-^>+>^
>>>>>>>>^

Try it online!

Ungolfed, mostly. Uses quadratic formula.

enter image description here

\$\endgroup\$
2
  • \$\begingroup\$ I managed to get this down to about half the size. \$\endgroup\$
    – Wheat Wizard
    Jan 23 at 19:21
  • \$\begingroup\$ @WheatWizard Nice! \$\endgroup\$
    – emanresu A
    Jan 23 at 19:22
2
\$\begingroup\$

Julia 1.0, 34 bytes

(a,b)->(d=(a*a-4b)^.5;[a+d,a-d]/2)

Try it online!

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

MathGolf, 13 bytes

_½\²¼k-√+`-αÞ

I/O as floats.

Port of @Arnauld's JavaScript answer.

Try it online.

I have the feeling this can be a byte shorter with some smart stack manipulations, but I've been unable to find anything yet. An equal-bytes alternative could be ²¼k-√`;½+`-αÞ.

Explanation:

_             # Duplicate the first (implicit) input-float
 ½            # Halve it
  \           # Swap so the first input is at the top of the stack again
   ²          # Square it
    ¼         # Divide it by 4
     k-       # Subtract the second input-float
       √      # Take the square-root of that
        +     # Add it to the halved first input that's still on the stack
         `    # Duplicate the top two values (since the stack only contains a single
              # item, this will first add the first input-float implicitly as leading
              # item, and then duplicate both items)
          -   # Subtract the top two items from one another
           α  # Pair the top two items
            Þ # Only leave the top item of the stack, and discard everything else
              # (after which the entire stack is output implicitly as result)
\$\endgroup\$
2
\$\begingroup\$

Ruby, 41 37 35 bytes

A port of Arnauld's answer in Ruby!

->a,b{[b=a/2r+(a*a/4r-b)**0.5,a-b]}

Try it online!

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

05AB1E, 10 9 bytes

D(Ÿʒ-y*¹Q

Try it online!

Takes input as

b
a

In case \$p=q\$ it returns only a single value. In case that's not allowed, it's +5 bytes for appending }Ðgi«

Explanation:

D              duplicate
)              negate
Ÿ              range, so [-b,.. , b]
ʒ              filter
 -             minus the implicit a
  y            the current number
   *           multiply
    ¹          the first item from the input history - b
     Q         is equals
\$\endgroup\$
2
\$\begingroup\$

Vyxal, 3 bytes

∆QN

Try it Online!

Solve for the roots and then negate

\$\endgroup\$
2
+50
\$\begingroup\$

Whispers v2, 110 92 bytes

Edit: -18 bytes (within less than 2 minutes of submission!) thanks to caird coinheringaahing and the ± operator

> Input
> Input
> 2
> 4
>> 1*3
>> 2⋅4
>> 5-6
>> √7
>> 8÷3
>> 1÷3
>> 10±9
>> Output 11

Try it online!

My first Whispers program.
Uses the Quadratic formula with a=1.

\$\endgroup\$
2
  • \$\begingroup\$ 92 bytes \$\endgroup\$ Feb 7, 2021 at 23:07
  • \$\begingroup\$ @cairdcoinheringaahing - Thanks! I should have guessed that ± would exist. That must be a contender for one of the fastest upgolfs yet... \$\endgroup\$ Feb 7, 2021 at 23:12
1
\$\begingroup\$

Pari/GP, 33 bytes

f(a,b)=round(polroots(x^2+a*x+b))

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Haskell, 39 bytes

f a b=let c=a/2+(a*a/4-b)**0.5in[c,a-c]

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Some simple improvements bring it down to 33: a!b|c<-a/2+(a*a/4-b)**0.5=[c,a-c] \$\endgroup\$
    – Wheat Wizard
    Jan 7, 2021 at 23:29

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