11
\$\begingroup\$

Preamble

We've already proven we're good at adding two numbers, but many solutions only operate on tiny numbers like 2³²-1, honestly we can do a lot better.

The Challenge

Given two unsigned, non-negative integers, add them together and return the output.

Input may be taken in any convenient format (String, Array of bytes/characters, BigInteger, etc.), and output may be in any convenient format as well. Inputs may optionally be padded with any character of choice to any length of choice.

Output must support at minimum all numbers in the range of [0,10²⁵⁶), Inputs will always be in this range as well.

Test Cases

1168 + 0112 = 1280
23101333 + 01858948 = 24960281
242942454044 + 167399412843 = 410341866887
9398246489431885 + 9300974969097437 = 18699221458529322
83508256200399982092 + 74143141689424507179 = 157651397889824489271
173163993911325730809741 + 291008926332631922055629 = 464172920243957652865370

Rules

  • Standard IO Applies
  • Standard Loopholes Apply
  • You may not output as Scientific Notation. All digits must be included in the output.
  • Solutions do not need to finish in any reasonable time, they only must provably work.
  • Use of built-in BigInteger implementations is allowed, though I encourage you to include a non-built-in solution.
  • This is so fewest bytes wins!
  • I/O may not be taken as Unary.
  • Have Fun!
\$\endgroup\$
10
  • 1
    \$\begingroup\$ Can I assume the two input numbers are padded to the same length? Or that they are padded to the length of the expected output? \$\endgroup\$
    – Bubbler
    Sep 3, 2023 at 23:54
  • 5
    \$\begingroup\$ By standard I/O rules (see here or here), input and output can be in unary, which may trivialize the challenge. Would you like to ban that (it seems no answer uses it so far), or can you confirm that they are allowed? \$\endgroup\$
    – Luis Mendo
    Sep 4, 2023 at 10:55
  • 1
    \$\begingroup\$ @LuisMendo I've explicitly forbidden Unary, good catch. \$\endgroup\$
    – ATaco
    Sep 4, 2023 at 23:43
  • 1
    \$\begingroup\$ @noodleman Output may also be in reverse, I can't imagine that causing much trivialization. \$\endgroup\$
    – ATaco
    Sep 4, 2023 at 23:43
  • 1
    \$\begingroup\$ @noodleman Taking individual digits as Unary is fine. \$\endgroup\$
    – ATaco
    Sep 5, 2023 at 22:25

20 Answers 20

10
\$\begingroup\$

Trivial Built-in Answers

For languages where bignum addition is already supported.

05AB1E, Brachylog, Factor, J, Jelly, Julia, Nekomata, RProgN 2, Vyxal, 1 byte

+

Try it online! (05AB1E)

Try it online! (Brachylog)

Try it online! (Factor)

Attempt This Online! (J)

Try it online! (Jelly)

Try it online! (Julia)

Attempt This Online! (Nekomata)

Try it online! (RProgN 2)

Try it Online! (Vyxal)


Haskell, Python, Raku, 3 bytes

sum

Attempt This Online! (Haskell)

Attempt This Online! (Python)

Attempt This Online! (Raku)

Takes input as a list.


Charcoal, 2 bytes

I⁺

Try it online! Requires input in JSON format. 4 bytes for string input:

I⁺NN

Try it online!


Java, 14 bytes

a->b->a.add(b)

I/O as java.math.BigIntegers.

Try it online.


JavaScript (ES11), 9 bytes

With BigInts as I/O.

a=>b=>a+b

Try it online!


PARI/GP, 9 bytes

a->b->a+b

Attempt This Online!


Ruby, 8 bytes

proc &:+

Attempt This Online!

\$\endgroup\$
3
  • \$\begingroup\$ Why is this the top voted answer? Clearly this should be near the bottom, no? If each of those builtins was separate they wouldn't be nearly this high. -1 from me, not because this is bad but because all of the cooler answers are below it. This is by definition a collection of all the least interesting answers \$\endgroup\$
    – noodle man
    Sep 6, 2023 at 17:00
  • 1
    \$\begingroup\$ @noodleman I guess this is just an answer everyone understands. \$\endgroup\$ Sep 6, 2023 at 22:07
  • \$\begingroup\$ PHP has it as well, since PHP 4, with the function bcadd() (php.net/manual/en/function.bcadd.php) or with the function gmp_add() since PHP 4.0.4 (php.net/manual/en/function.gmp-add.php). \$\endgroup\$ Sep 6, 2023 at 22:23
8
\$\begingroup\$

05AB1E, 13 9 bytes

Dv+T‰Áø`À

Try it online!

No bigints. Takes both inputs as a reversed list of digits, padded to at least the length of the output, and outputs in the same way.

Uses a + b = (list(a)+list(b))%10 + right_rotate((list(a)+list(b))//10). Once we do that length(output) times the second addend will become zero.

Explanation

      # implicit input a, b
D     # duplicate b, stack is a,b,b
v     # for x in b (x isn't used)
 +    # add a+b digit-wise
 T    # push 10
 ‰    # divmod, so we now have a list of ((a[i]+b[i])//10, (a[i]+b[i])%10)
 Á    # rotate right
 ø    # transpose
 `    # dump, the stack has right_rotate((a[i]+b[i])//10), right_rotate((a[i]+b[i])%10)
 À    # left rotate
      # stack is right_rotate((a[i]+b[i])//10), (a[i]+b[i])%10
# implicit output
\$\endgroup\$
7
\$\begingroup\$

K (ngn/k), 13 bytes

10!(_0.1/,)\+

Try it online!

Takes two lists of digits in reverse order padded to an equal length that is at least as long as the result.

10!(_0.1/,)\+
            +   Add two numbers digit-by-digit
   (      )\    Handle carry using scan:
                  left = 10 * carry + digit value, right = next digit value
    _0.1/,        add carry to the next digit
10!             Remove carry information
\$\endgroup\$
6
\$\begingroup\$

TypeScript's Type System, 211 193 bytes

//@ts-ignore
type F<A,C=[]>=A extends[[...infer G,infer X],[...infer H,infer Y]]?[...X,...Y,...C]extends[1,1,1,1,1,1,1,1,1,1,...infer R]?[...F<[G,H],[1]>,R]:[...F<[G,H],[]>,[...X,...Y,...C]]:[]

Try it at the TypeScript Playground!

This is a generic type F taking type A which is a tuple of two lists of unary numbers (using unary not for the numbers themselves but for the individual digits, as allowed by OP) padded with leading zeroes ([]s) to the length of the output.

For example: F<[[[1],[1],[1,1,1,1,1,1],[1,1,1,1,1,1,1,1]],[[],[1],[1],[1,1]]]> (1168 + 0112) = [[1],[1,1],[1,1,1,1,1,1,1,1],[]] (1280)

Explanation

//@ts-ignore                    Ignore any compilation errors in
type F<                      // Recursive main type F
  A,                         //   A is tuple of two lists of unary digits
  C=[]                       //   C is the digit to carry, default 0
>=
  // Match A to get the last and other digits of each number
  // X and Y are the current digits of each, G and H are the rest
  A extends[[...infer G,infer X],[...infer H,infer Y]]
    ?[...X,...Y,...C]extends // If it matched: Merge X,Y,C and match against
      [/* ... */,...infer R] //   ten 1s, storing what's left in R
        ?[...F<[G,H],[1]>,   //     If it matched, recurse with [G,H], C=[1]
          R]                 //       And append R
        :[...F<[G,H],[]>,    //     Otherwise, recurse with [G,H], C=[]
          [...X,...Y,...C]]  //       And append X,Y,C merged
    :[]                      // If the match failed, return the empty tuple
\$\endgroup\$
2
  • \$\begingroup\$ Fixed your test harness so you don't need the @ts-expect-error: tsplay.dev/mZJDam \$\endgroup\$
    – Bbrk24
    Sep 6, 2023 at 14:50
  • \$\begingroup\$ @Bbrk24 Thanks lol. Mapped tuple types suck \$\endgroup\$
    – noodle man
    Sep 6, 2023 at 14:55
5
\$\begingroup\$

C (gcc), 62 bytes

f(a,b)char*a,*b;{*a=*a?48+(*b+=f(a+1,b+1)+*a-96)%10:0;b=*b>9;}

Try it online!

Input two char* strings. They must be padded with leading 0s so they have same length and enough to contain the output. Modify the first array in-place for output.

\$\endgroup\$
3
  • \$\begingroup\$ @AZTECCO Yes, it assumed the input must be padded with one more zero, or in the other word, have same length and enough to contain the output. \$\endgroup\$
    – tsh
    Sep 5, 2023 at 1:52
  • \$\begingroup\$ If I understand this correctly, you recurse down to the ends of the strings where you find the least-significant digits, and the carry-propagation happens as you unwind back out? So the strings are in printing order. \$\endgroup\$ Sep 11, 2023 at 11:26
  • \$\begingroup\$ @PeterCordes Yes. The string is in printing order, aka. most significant digit first, which I would expected as the default behavior of string i/o, since it is nature to user. \$\endgroup\$
    – tsh
    Sep 11, 2023 at 11:35
5
\$\begingroup\$

Lua, 121 119 bytes

load"A,B=...m=math.floor o=''c=0 for i=1,#A do L=#A-i+1O=A:sub(L,L)+c+B:sub(L,L)c=O/10 o=m(O%10)..o end return m(c)..o"

Try it online!

Ungolfed

function add(A,B)
    floor=math.floor
    output=""
    carry=0
    for i=1,#A do
        L=#A-i+1
        sumResult=A:sub(L,L)+carry+B:sub(L,L)
        carry=sumResult/10
        output=floor(sumResult%10)..output
    end
    return floor(carry)..output
end

Inputs must be 0 padded to equal length.

\$\endgroup\$
3
  • \$\begingroup\$ math.floor can be replaced with //10 and |0s. I don't really understand why O ends up a float anyway though \$\endgroup\$
    – Jo King
    Sep 4, 2023 at 4:35
  • \$\begingroup\$ @JoKing I was doing testing on a funny version of Lua to write it, O becomes a float because Lua overzealously demotes Integer types to Doubles, and in this case the addition of strings demotes it. \$\endgroup\$
    – ATaco
    Sep 4, 2023 at 5:57
  • \$\begingroup\$ Maybe worth noting that padding with zeros to identical length is mandatory. \$\endgroup\$ Sep 6, 2023 at 14:06
4
\$\begingroup\$

Vyxal, 35 bitsv2, 4.375 bytes

02(?(›

Try it Online!

Doesn't use +, but does use addition of some sort (incrementing the top of the stack). Takes inputs as two numbers.

Vyxal, 47 bitsv2, 5.875 bytes

2(?(1}!

Try it Online!

No addition used, but still requires bignums to be inputted.

Vyxal, 133 bitsv2, 16.625 bytes

ZEṠṘ0$(n+₀ḋ÷⅛)¾ṘJṅ⌊

Try it Online!

A version that takes both numbers as strings, and never has any values that could be a bignum on the stack (except at the end to remove a leading 0 from a string and to implicitly print - this could be done with string methods but it's shorter to use number conversion).

Explained

02(?(›­⁡​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏⁠‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁡​‎‏​⁢⁠⁡‌­
0       # ‎⁡Push a 0 to the stack to act as a register
 2(     # ‎⁢Twice:
   ?(   # ‎⁣  For each number in the range(1, input() + 1):
     ›  # ‎⁤    Increment that 0
# ‎⁢⁡The "register" value is then implicitly printed
💎

Created with the help of Luminespire.

2(?(1}!­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁣‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌­
2(       # ‎⁡Twice:
  ?(     # ‎⁢  Number of input times:
    1    # ‎⁣    push a 1 to the stack
     }!  # ‎⁤Close all loops and push the length of the stack
💎

Created with the help of Luminespire.

ZEṠṘ0$(n+₀ḋ÷⅛)¾ṘJṅ⌊­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁢‏⁠‎⁡⁠⁣‏⁠‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏⁠‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁤⁢‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁣⁤‏⁠‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁤⁣‏⁠‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁢⁡⁢‏⁠‎⁡⁠⁢⁡⁣‏‏​⁡⁠⁡‌­
ZEṠ                  # ‎⁡Zip the input strings together, evaluate the digits in each pair, and vectorise sums
   Ṙ0$               # ‎⁢Reverse it, and push a 0 underneath it. This will act as the carry.
      (      )       # ‎⁣For each digit in that list,
       n+            # ‎⁤  Add the carry to that digit, consuming the carry
         ₀ḋ          # ‎⁢⁡  Divmod by 10
           ÷⅛        # ‎⁢⁢  And add the mod value to the global array, leaving the div value on the stack as the new carry.
              ¾ṘJ    # ‎⁢⁣Push the global array, reverse it, and prepend the carry
                 ṅ⌊  # ‎⁢⁤Convert to a single string and cast to int, removing any leading 0s.
💎

Created with the help of Luminespire.

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

Factor, 39 31 43 bytes

[ 0 -rot [ + + 10 /mod ] 2map swap suffix ]

Try it online!

Non-builtin counterpart to the + answer. Takes two reversed, padded lists of digits as input and outputs the reversed answer as a list of digits.

\$\endgroup\$
2
  • \$\begingroup\$ The output of this seems to lack the initial digit, which may not always be zero (simple example, although your own TIO link also exhibits this...). Of course, you can insist that the input should be padded with at least one additional zero to solve this, but you should probably mention that this is required... \$\endgroup\$ Sep 7, 2023 at 10:35
  • \$\begingroup\$ @DominicvanEssen Thanks. Fixed for +12 bytes. \$\endgroup\$
    – chunes
    Sep 7, 2023 at 12:44
4
\$\begingroup\$

ISO C23 (clang 16), 42 bytes

_BitInt(constant) is a new C23 feature for fixed-width integers, wide or small. Implementations can have limits (BITINT_MAXWIDTH) on how wide they support, but clang 16 is wide enough for the problem's stated range of [0, 10256). log2(10^256) rounds up to 851 bits required. 960 is the largest 3-digit number that's a multiple of 64 (not required, I just chose for efficiency); you can use unsigned _BitInt(999) if you want.

typedef _BitInt(960)T;T f(T*a,T b){*a+=b;}

Updates the caller's a by reference. Using the return value would be undefined behaviour (and in practice isn't useful even in a debug build.)

Works in practice with clang 16 (Godbolt shows it compiles to a sequence of add/adc instructions for x86-64, with some wasted loads/stores). But not GCC 13.2 or 14-trunk: error: '_BitInt' argument '960' is larger than 'BITINT_MAXWIDTH' '575'. (The Godbolt link also includes a simple test caller in main, but AFAIK there isn't convenient support for printf of big _BitInt values, and I didn't bother writing a hexdump.)

C23 doesn't allow implicit-int return values, and T is a shorter type-name than explicit void or int. But in C (unlike C++) it's not UB for execution to fall off the end of a non-void function, so we can declare it with a short type-name as the return type and still not actually return anything, if implicit-int isn't an option. void f(...) would cost 3 extra bytes. Or actually returning by value like T f(T a,T b){return a+b;} costs an extra 5.

typedef _BitInt(960)T; is one byte shorter than #define T _BitInt(960)+newline. The more readable version is 43 bytes:

#define T _BitInt(960)
T f(T*a,T b){*a+=b;}

Related: https://stackoverflow.com/questions/61411865/how-do-you-use-clangs-new-custom-size-int-feature


Clang provides _BitInt as an extension in older C modes, and in C++ mode.

C89 (clang 16), 40 bytes

typedef _BitInt(960)T;f(T*a,T b){*a+=b;}

Attempt This Online!

With default options (I think -std=gnu11), clang 16 requires -Wno-implicit-int, otherwise we get an error: source.c:2:1: error: type specifier missing, defaults to 'int'; ISO C99 and later do not support implicit int [-Wimplicit-int]. (And yes, in clang it's an error, not a warning, even without -Werror.)

But -std=gnu89 or c89 is allowed "for free" without having to count those compiler command-line options as part of the size of the answer. (I think? I can't find the relevant meta Q&A.) This feels like bending the rules because I'm using a very recent clang extension, but is arguably not breaking them. It compiles to the same asm on Godbolt.

C++ (clang 16), 43 bytes

using T=_BitInt(960);void g(T&a,T&b){a+=b;}

C++ using is shorter than C typedef or #define, but falling off the end of a non-void function is UB in C++, not just if the caller uses the result. (void didn't exist in the early days of C, but existed from the start for C++.)

With T as the return type but no return statement, clang -Os emits zero instructions (not even ret) for the function. With optimization disabled, clang emits a ud2 (illegal instruction) at the end instead of ret. (Godbolt)

using T=_BitInt(960);T g(T&a,T&b){return a+b;} is 46 bytes.

Taking both args by reference is probably better for efficiency in the caller. In the callee, clang still saves enough call-preserved registers to load a whole arg into registers, instead of working on a couple chunks at a time. And that's just addition; things get really hairy with division or multiplication. (But unlike Clang 14, division is supported for big _BitInt types, both by small constants and by other variables. Clang 15 dropped the max bit width to 128; Clang 16 widened it again.)

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

Retina 0.8.2, 49 44 bytes

O#$`.
$.%`
¶

M!`..
.
$*
+`¶1{10}
1¶
%M`1
¶

Try it online! Takes input on separate lines but link is to test suite that splits on . for convenience. Requires both inputs to be 0-padded to the same length. Explanation:

O#$`.
$.%`
¶

M!`..

Transpose the inputs.

.
$*

Convert to unary, summing each pair of digits.

+`¶1{10}
1¶

Perform any necessary carries.

%M`1

Convert to decimal.

Join all of the digits together.

Retina 1.0 has some support for bignums which does include addition so here's how it would be done:

L$`¶
$.($`*_$'*

Try it online! Takes input on separate lines but link is to test suite that splits on . for convenience. Explanation: matches the newline between the numbers, but the numbers themselves can be retrieved via $` and $'. The * operator notionally converts them to unary and the $.( then converts the sum to decimal, although the underlying code simply sums the two bignums directly.

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

Ruby, 78 67 59 49 bytes

->a,b{c=0;a.zip(b).map{s=_1+_2+c;c=s>9?1:0;s%10}}

Attempt This Online!

My first Ruby submission! This is probably a little golfable but I'm pretty happy with it considering I have almost zero Ruby experience. Suggestions are welcome!

Implements long addition on two lists of digits in reverse order padded to the length of the output with zeroes, and outputs a list of digits in reverse order. Explanation:

  • ->a,b{...} Proc (anonymous function) taking parameters a and b

    • c=0; Set the c (the carried digit) to 0

    • a.zip(b) Zip a with b to get a list of pairs of digits

    • .map{...} Map each pair of digits to

      • s=_1+_2+c; Set s to the sum of the two digits and the carry

      • c=s>9?1:0; Set c to 1 if s is greater than 9, or 0 otherwise

      • s%10 Return the ones place of s by taking it modulo 10

\$\endgroup\$
2
  • \$\begingroup\$ Ruby has arbitrary precision integers, surely there's no need to implement it by hand? \$\endgroup\$ Sep 4, 2023 at 21:23
  • 3
    \$\begingroup\$ @ShadowRanger I added a built-in version to the Community Wiki, but I wanted to write one that didn’t use the built in. There are answers in a lot of other languages that have built in big integers \$\endgroup\$
    – noodle man
    Sep 4, 2023 at 21:26
3
\$\begingroup\$

JavaScript (Node.js), 63 bytes

f=(a,b,c=0)=>(c-=~a.pop()+~b.pop()+2)||a+b?f(a,b,c/10|0)+c%10:a

Try it online!

no bigint

\$\endgroup\$
2
  • \$\begingroup\$ f=(a,b,c=0)=>(c-=-a.pop()-b.pop())?f(a,b,c/10|0)+c%10:a \$\endgroup\$
    – tsh
    Sep 6, 2023 at 5:23
  • \$\begingroup\$ @tsh Deleted temporary for failure 100000+100000 \$\endgroup\$
    – l4m2
    Sep 6, 2023 at 6:06
3
\$\begingroup\$

C (clang), 73 69 58 bytes

c;f(*a,*b,n){for(;n--;c/=10)a[n]=(c+=a[n]+b[n]-96)%10+48;}

Try it online!

Saved 4 bytes thanks to tsh
Saved 11 bytes thanks to Peter Cordes

Inputs two wide-charater strings, padded to the length of the expected output.
Returns the sum in the first input string.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ I believe you do not need the c=0, as long as we can assume that user input are always valid, aka. padded to the length of the expected output. Since the carry bit would always be 0 after last f invoke. \$\endgroup\$
    – tsh
    Sep 4, 2023 at 11:46
  • \$\begingroup\$ @tsh Nice one - thanks! :D Also great C answer - you can probably save a few byte by switching to wide-charater strings! :))) \$\endgroup\$
    – Noodle9
    Sep 4, 2023 at 12:14
  • \$\begingroup\$ @AZTECCO Yes: Inputs two wide-charater strings, padded to the length of the expected output. As allowed, see the comments. \$\endgroup\$
    – Noodle9
    Sep 4, 2023 at 22:52
  • \$\begingroup\$ Could you take the length as a 3rd arg, instead of using implicit-length strings? I don't think your code depends on there being a 0 terminator. \$\endgroup\$ Sep 9, 2023 at 4:37
  • \$\begingroup\$ @PeterCordes Great idea - thanks! :D \$\endgroup\$
    – Noodle9
    Sep 9, 2023 at 19:36
2
\$\begingroup\$

Charcoal, 21 bytes

PS¶S¶Wⅈ«←P←⮌IΣEKD³↑Σκ

Try it online! Link is to verbose version of code. Takes input as two strings of equal length but spaces can be used for padding and outputs the input strings and their sum. Explanation:

PS

Write the first string to the canvas without moving the cursor.

Move down a line.

Write the second string to the canvas.

Move down another line.

Wⅈ«

Repeat until the cursor reaches the left column.

Move left.

P←⮌IΣEKD³↑Σκ

Overwrite the current character with the sum of the column, overflowing any carry to the left.

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

Perl 5, 84 bytes

sub f{($x,$y,$c,$s)=@_;$x|$y?f((map{s/.?$/$c+=$&;''/er}$x,$y),$c>9,$c%10 .$s):$c.$s}

Try it online!

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

R, 30 bytes

\(x,y)c(0,z<-x+y)%%10+c(z>9,0)

Attempt This Online!

Input as vectors of decimal digits, padded to the same length with leading zeros (or 27 bytes if the padding always contains at least one leading zero).
Automatic vectorization of (most) functions in R makes this pretty easy.


R, 41 bytes

\(x,y)c(0,z<-c(y&0,x)+c(x&0,y))%%10+(z>9)

Attempt This Online!

Input as vectors of decimal digits, no padding required. Output can contain (possibly many) leading zeros.


R, 90 58 bytes

\(x,y,a=c(0,z<-c(y&0,x)+c(x&0,y))%%10+(z>9))a[cumsum(a)>0]

Attempt This Online!

Input as vectors of decimal digits, no padding required. Output has no leading zeros.

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

x86-64 machine code, 10 8 bytes

A function that adds two little-endian binary Bigintegers of the same (non-zero) length, updating the destination in-place, using add-with-carry as a building block as it was designed for this.

It takes 2 pointer args and a count of how many 32-bit chunks, like add_bignum(uint32_t *rdi_dst, uint32_t *rsi_src, size_t count_rcx). (That matches the x86-64 SysV calling convention if you use a dummy 3rd arg to fill the EDX slot.) The same machine code works in 32-bit mode, since lodsd and stosd work with whatever the native pointer size is.

It returns CF = carry-out from the top element. (If you want that to be part of the output, zero-extend the inputs with an extra 0 element at the top, and include that in the count.)

; NASM listing: machine code | source
               add_bignum:
 F8               clc                ; CF=0, no carry-in to the bottom.
                                     ; Peeling a first iteration using ADD would cost more bytes
               .loop:                ;do {
 AD               lodsd                ; eax = [rsi]; rsi+=4 without affecting FLAGS
 13 07            adc   eax, [rdi]
 AB               stosd                ; [rdi] = eax; rdi+=4 without affecting FLAGS
 E2 FA            loop  .loop        ; }while(--rcx);
 C3               ret   

Add-with-carry (adc) chains the carry-out from the top of one chunk into the carry-in for the next chunk. As the loop iterates, it's like one wide ripple-carry adder over the full width of the arrays. (With carry-lookahead or whatever optimizations exist inside the CPU's ALUs happening within each chunk to run it with single-cycle latency. But as far as the result is concerned, it's like one long chain of full-adders, with the same hardware reused by software feeding the carry-out of the last instruction to the carry-in of the next. Carry only propagates from low to high in both addition and subtraction. It doesn't matter what element-size you use for it, as long as you get all the bytes of your bigints and chain the carry correctly.)

Bigint performance notes: the loop instruction is slow except on recent AMD CPUs, where it's actually really handy for loops that want to preserve FLAGS. It's too bad Intel didn't make it fast. Normal bigint loops on Sandybridge and later use dec ecx / jnz which leaves only CF unmodified, because Sandybridge has cheap partial-flag merging instead of stalling. And Broadwell and later don't merge at all; uops that want both parts of FLAGS just read it as 2 separate inputs, which is why cmovbe and cmova are still 2 uops while others are down to 1 uop. So the bigint looping problem has been solved that way, unlike on older P6-family CPUs where partial-flag stalls are a real problem.

Also, for performance, memory source adc is better on Intel CPUs, with a separate mov store. (Fun fact: memory destination adc has an extra uop beyond what you'd expect because of arcane microarchitectural reasons involving lack of TLB coherency across the uops of one instruction, according to Andy Glew.)

Also obviously using 64-bit operand-size would go twice as fast as 32-bit, or 8x as fast as bytes, for the same number of bytes. (Instruction fetch/decode isn't the bottleneck on modern CPUs with a uop cache, so the code-size differences aren't very significant for a hot loop). That costs an extra REX prefix on most instructions so I didn't use it in the initial version with 32-bit elements.

TL:DR: un-golfing this code to something that performs well is more than just the obvious changes. (Especially before the last update.) Look at the hand-written asm in GMP for production-quality example. (e.g. https://github.com/sethtroisi/libgmp/blob/master/mpn/x86_64/coreisbr/aors_n.asm is the add-or-sub template for adc or sbb loops for Sandybridge-family. It uses some jrcxz instead of just dec/jnz at the bottoms of loops, but I think the main unrolled loop uses dec/jnz.)


A previous version of this answer used memory-destination adc [edi], al, having to use byte operand-size instead of dword so we could use 1-byte inc in 32-bit mode. Thanks @m90 for reminding me of the standard lods / stuff / stos pattern which has the added bonus of allowing memory-source adc! My comments below are about why that 1-byte version was so inefficient:

Normally you can use scasd to increment RDI by 4, as long as it's a valid pointer, but that does a compare as well as load which overwrite FLAGS, breaking the chain of carry propagation through CF. Some shenanigans like pointing ESP at this array and using 1-byte pop eax then adc [esi], eax and a dummy lodsd to increment ESI might work, but would probably cost more bytes than lea edi, [edi+4] (and a signal handler could clobber the array). Maybe we could expect our caller to pass one of the bigints by value on the stack. And we'd still have to push the return address back again.

So definitely the smallest (and lowest performing) is to use 1-byte "limbs", making the pointer increment a single-byte (in 32-bit mode) inc, which sets the other FLAGS (all of SPAZO), but not CF. Other code can process the same bigint in larger chunks; the limb size is only relevant to the count the caller passes, not anything else about the layout.

\$\endgroup\$
4
  • \$\begingroup\$ Presumably this would be only 8 bytes if you used byte operands - F8 AC 10 07 47 E2 FA C3. \$\endgroup\$
    – Neil
    Sep 6, 2023 at 5:27
  • \$\begingroup\$ @Neil: Oh right, then I could use inc edi. I had considered byte vs. dword at the start, but went dword since scasd exists, and forgot to reconsider that after running into the fact that scasd clobbers FLAGS. Thanks. \$\endgroup\$ Sep 6, 2023 at 6:24
  • 1
    \$\begingroup\$ I think it is in fact possible to handle 4-byte limbs with no increase in code length, by doing the addition into EAX and then using stosd. \$\endgroup\$
    – m90
    Sep 8, 2023 at 18:00
  • \$\begingroup\$ @m90: yup, thanks, obvious in hindsight. Updated my answer with that version which should be about 4x faster. \$\endgroup\$ Sep 8, 2023 at 21:41
2
\$\begingroup\$

C, 54 bytes

Binary bigint using 8 bits per int, in little-endian limb order. Carry-out still fits within an int where we can get it with a shift. void f(int *dst, int *src, int n). Updates the destination in place

x;f(*a,*b,n){for(x=0;n--;*a++&=255)x=*a+=x/256+*b++;}

Try it online!

Iterates over the arrays, a[i] += b[i] + carry_in, truncating dst elements to 8 bits. x = un-truncated addition result, so the carry-out is in its 9th bit. It's non-negative since int is at least 16-bit, so we can do x/256 = x>>8 to get it as a 0 / 1 integer that has the right place-value for the next limb.

9 bits per limb would still cost the same code size (&=511 and x/512), but more bits would need longer constants. I picked 8 because it's a round number, and easy to pack down to bytes to avoid the wasted space. (Making it a plausible format for larger code-golfed programs that want to use this.)

On a 64-bit machine with 32-bit int, this supports numbers up to 8*(2^31-1) bits wide. That's vastly larger than the required 10^256 which only requires 851 bits. I could have used just 4, 2 or even 1 bit per limb to make the constants even smaller. Or 3 bits per limb (&=7 and x/8); it doesn't have to be a power-of-2 number of bits. Using up 4x the amount of space seemed more reasonable than wasting 31x the amount, and more plausible for code converting to this format.


Real-life code uses this technique, but with 30 bits per uint32_t for example in CPython, since they avoid using hand-written asm for more efficient bigint on machines that have a carry flag. (See my codereview answer discussing BigInt implementation techniques, that using base 10 is highly inefficient, although base 10^9 in 32-bit chunks is good for efficient conversion to/from decimal strings, as in Extreme Fibonacci code golf.) Multiply uses stuff like a * (uint64_t)b as a widening multiply.

Partial-word bigint formats (not using all the bits per chunk) also allow deferring carry for SIMD implementations (as Mysticial explains), but that requires writing code that's aware of it.

C sucks at exposing add-with-carry or sub-with-borrow, especially carry-in to the same element where you want a carry-out. No portable functions for this, so it's up to compilers to recognize some idioms, such as carry = (a+b)<a for unsigned types. Or there are non-portable intrinsics such as for x86, but those often compile to poor asm for more than 2 limbs, or in a loop. But things have improved some recently, with a combination of some compilers getting better at keeping carry-out in the carry flag (instead of materializing a 0/1 integer in a register), and a way of writing portable ISO C source that actually gets clang to compile to a chain of adc instructions on ISAs that have a carry flag.

This version is of course optimizing for source size, not performance or storage density.

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

dc, 4 3 bytes

?+p

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Since you are inputting both numbers on one line, a single ? is enough to push both of them onto the stack: tio.run/##DcOxEYAwDAPAVehpLAnbUcUwMED2bwx/… \$\endgroup\$ Sep 5, 2023 at 3:25
  • \$\begingroup\$ @DigitalTrauma didn't know that, thanks! \$\endgroup\$
    – noname
    Sep 5, 2023 at 4:34
0
\$\begingroup\$

AWK, 12

{print$1+$2}

Try it online!

\$\endgroup\$
2
  • 4
    \$\begingroup\$ Shouldn't this be in the "Trivial Built-in Answers" answer? \$\endgroup\$ Sep 5, 2023 at 4:20
  • 2
    \$\begingroup\$ @CommandMaster It could be, though there's no requirement. Why don't you add it? \$\endgroup\$
    – Sneftel
    Sep 6, 2023 at 10:18

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.