9
\$\begingroup\$

Your challenge (if you choose to accept it) is to implement big integer multiplication in the shortest code possible.

Rules:

  • Take two integers (decimal form) as ASCII strings from the command line parameters of your program. If your language doesn't support command line parameters, I'll accept stdin or similar input mechanisms.
  • Output should be in ASCII decimal form, via a standard output mechanism (e.g. stdout)
  • Must support both positive and negative integers, as well as zero.
  • Must support any length integer integers up to 2**63 characters long, or at least the maximum you can store in memory.
  • You may not use any in-built classes or functionality that handles big integers.
  • The largest data type you may use is a 64-bit unsigned integer.
  • You may not use floating point operations.
  • You do not have to implement checks for valid inputs.

Example:

> multiply.exe 1234567890 987654321
1219326311126352690

Enjoy :)

\$\endgroup\$
10
  • \$\begingroup\$ If you say "must support any length integer" you should perhaps add something about performance. Multiplying integers with millions of digits will take really long, at least if we're not supposed to use sophisticated algorithms with FFT and suchlike. \$\endgroup\$ May 30, 2012 at 20:04
  • \$\begingroup\$ @leftaroundabout: What do you call really long? I guess integers, longer as what is common in many libraries - 64 bit for example - is sufficient. Multiplying 2 numbers of 100 digits each schould be 10000 multiplications and some additions - nothing taking longer than a second in a scripting language. \$\endgroup\$ May 31, 2012 at 0:02
  • \$\begingroup\$ Boothby is complaining in the comments, that intermediate results of mine will overflow if integers of 'any' length are allowed. Now my algorithm produces a list of intermediate results which exhausts the memory on my machine for a multiplication of about 2000 * 2000 digits. I can increase the RAM for the machine to reach 16.000 digits squared. And switch to a 64bit-System, and increase it further. However, the algorithm would - given no RAM limit - reach 25M digits squared - about 10 books of 500 pages of 60 rows of 60 digits each. With Long 20 billion such books. Isn't that enough? \$\endgroup\$ Jun 1, 2012 at 3:33
  • \$\begingroup\$ @userunknown, "any" length was specified. To me, that's an algorithmic requirement that says if you get a bigger, faster computer 100 years down the road, the implementation won't suddenly start overflowing somewhere. I mean, why else would that requirement be in there? \$\endgroup\$
    – boothby
    Jun 1, 2012 at 5:23
  • 2
    \$\begingroup\$ So... to be extremely pedantic (sorry guys, I'm a mathematician, this is what I think about day to day): if you require 2**63 character inputs, well... one of those actually fills up the maximum addressable space of 2**63. Thus, you can't actually store the inputs in memory! Ouch. Set the limit to 2**61 so we can store both the inputs and output in memory. \$\endgroup\$
    – boothby
    Jun 1, 2012 at 19:54

8 Answers 8

11
\$\begingroup\$

APL (124 120 116)

This is way too long. It does grade school multiplication.

N←{↓⌽↑⌽¨⍵}⋄S↓'-',A/⍨∨\×A←{∨/M←9<T←0,⍵:∇(1⌽M)+T-M×10⋄⍵}⊃+/N↑⍨⌿2L⍴E,(L-1)+⍳L←⊃⍴E←⌽Y∘ר⊃X Y←N⍎¨¨A~¨'-'⊣S←1≠+/'-'∊¨A←⍞⍞

Explanation:

  • N←{↓⌽↑⌽¨⍵}: N is a function that, given a vector of vectors, makes all the vectors the same length, padding with zeroes at the front. It does this by reversing all inner vectors (⌽¨), turning the vector of vectors into a matrix (), reversing this matrix (), and turning it back into a vector of vectors ().
  • S←1≠+/'-'∊¨A←⍞⍞: Read two lines of input, as characters (⍞⍞), store them in A, and count how many minuses there are in the input. S is zero or one depending on whether the result will be positive.
  • X Y←N⍎¨¨A~¨'-': In A (our input) without (~) the minuses, evaluate each separate character (⍎¨¨), run it through the N function and save the two vectors in X and Y. If the input was 123 32, we now have X=1 2 3 Y=0 3 2.
  • L←⊃⍴E←⌽Y∘ר⊃X Y: For each digit in the first vector, produce a vector with the digits from the second vector multiplied by that digit. Reverse this vector of vectors so that the least significant one is at the front. Store this vector in E and its length in L.
  • +/N↑⍨⌿2L⍴E,(L-1)+⍳L: Shift all of these vectors left, padding with zeroes on the right, by their index. Run them through N again so that they're all the same length. Then add all these vectors together. I.e.:
       1 2 3
         3 2
      ------
       2 4 6 (shift 0)
     3 6 9   (shift 1)
    --------
    3 8 13 6 (before carry)
     3 9 3 6 (after carry)
  • A←{∨/M←9<T←0,⍵:∇(1⌽M)+T-M×10⋄⍵}: Carry the ones. As long as there are still 'digits' higher than 10 (∨/M←9<T←0,⍵), add one to the next significant digit (∇(1⌽M)+T) and remove 10 from the offending digit (-M×10).
  • '-',A/⍨∨\×A: Remove any leading zeroes from the result vector, and add a minus in front.
  • S↓: Remove S characters from the front, i.e. if the result is supposed to be positive then remove the minus again.
\$\endgroup\$
1
  • 4
    \$\begingroup\$ Wow... An APL program that takes more than 80 characters. I don't know whether I should be impressed or dissatisfied... \$\endgroup\$
    – FUZxxl
    Jun 6, 2012 at 16:39
4
\$\begingroup\$

Javascript, 147 chars

a=prompt(b=prompt(j=c=[]))
for(i=a.length;j--||(j=b.length,n=0,i--);)c[i+j]=(n=~~c[i+j]+n/10+~~b[j-1]*~~a[i]|0)%10
" -"[10>a[0]^10>b[0]]+c.join("")
\$\endgroup\$
4
  • \$\begingroup\$ How does this output the result? I tried it on jsFiddle (jsfiddle.net/SnQ7G) but apparently it doesn't display anything \$\endgroup\$ May 31, 2012 at 19:48
  • \$\begingroup\$ @w0lf run in the console of your favorite webbrowser \$\endgroup\$
    – copy
    May 31, 2012 at 19:56
  • \$\begingroup\$ +1 yes, it works, and I learned something new today :). One thing you could fix though - get rid of the leading zeroes \$\endgroup\$ May 31, 2012 at 20:04
  • \$\begingroup\$ Isn't this invalid on its face because it uses floating-point math by the rules, given that JavaScript only supports floating-point scalars? \$\endgroup\$
    – Myria
    May 10, 2016 at 2:02
3
\$\begingroup\$

Scala 567 519

type I=List[Long]
type S=String
object C extends App{
def g(l:I,s:I=Nil,i:Long=0L):I=if(l.isEmpty)(i/10::i%10::s).dropWhile(_==0)else
g(l.tail,(l(0)+i)%10::s,(l(0)+i)/10)
def m(p:S,q:S)=g((p.reverse.zipWithIndex.map{a=>q.reverse.zipWithIndex.map(b=>((""+a._1).toLong*(""+ b._1).toLong,a._2+b._2))}.flatten.groupBy(_._2).map(m=>(m._1,m._2.map(_._1)sum))).toList.sortBy(_._1).map(_._2)).mkString
def f(s:S,t:S)=(if((s+t).matches("[^-]*-[^-]*"))"-"else"")+m(s.filter(_!='-'),t.filter(_!='-'))
println(f(args(0),args(1)))
}

updated: Use some Longs for intermediate values, while in fact long Ints passed as Strings can't exceed the length of Int.MaxValue.

Far away from the APL-range, this compilable Scala code multiplies 2 ints of 100digits in about a second on a 7 y'o machine.

I have an ungolfed version which doesn't work :) . Method m seemed to work with a loop, but only because for some map sizes, the map was sorted in the way the g-Method expected the values.

Of course I can sort it, but then I got problems with leading/trailing zeros, or 1-digit values. I tried with ("12345").map in the REPL, and it worked quickly, so I made a test how far I could golf the loop-version, and got nearly the same result - 143 chars here, 145 chars there, so I took my working solution.

So how does the code work: 3 methods:

  • f) evaluate sign with regex, to append it in the end, and remove the - when calling b)
  • m) zips both Strings with indexes, mupltiplies each digit with each and sums their indexes. Then groups by index sum, sorts by index sum, sums the values therein. Hands the List of values to c)
  • g) takes the number, and keeps the last digit. Divides the rest and adds it to the head of the rest of the list, which gets proceeded the same way until empty.

From the REPL, multiplying 1234567890 987654321 The first column from below shows the result digit calculated, except the leading digit which is the overflow from the last computation, and is in column 2.

Replaying:
sum((p.reverse.zipWithIndex.map{a=>q.reverse.zipWithIndex.map(b=>((""+a._1).toInt*(""+ b._1).toInt,a._2+b._2))}.flatten.groupBy(_._2).map(m=>(m._1,m._2.map(_._1)sum))).toList.sortBy(_._1).map(_._2)).mkString.reverse
    0  : 0  ::  List(9, 26, 50, 80, 115, 154, 196, 240, 285, 240, 196, 154, 115, 80, 50, 26, 9)
    9  : 0  ::  List(26, 50, 80, 115, 154, 196, 240, 285, 240, 196, 154, 115, 80, 50, 26, 9)
    6  : 2  ::  List(50, 80, 115, 154, 196, 240, 285, 240, 196, 154, 115, 80, 50, 26, 9)
    2  : 5  ::  List(80, 115, 154, 196, 240, 285, 240, 196, 154, 115, 80, 50, 26, 9)
    5  : 8  ::  List(115, 154, 196, 240, 285, 240, 196, 154, 115, 80, 50, 26, 9)
    3  : 12  ::  List(154, 196, 240, 285, 240, 196, 154, 115, 80, 50, 26, 9)
    6  : 16  ::  List(196, 240, 285, 240, 196, 154, 115, 80, 50, 26, 9)
    2  : 21  ::  List(240, 285, 240, 196, 154, 115, 80, 50, 26, 9)
    1  : 26  ::  List(285, 240, 196, 154, 115, 80, 50, 26, 9)
    1  : 31  ::  List(240, 196, 154, 115, 80, 50, 26, 9)
    1  : 27  ::  List(196, 154, 115, 80, 50, 26, 9)
    3  : 22  ::  List(154, 115, 80, 50, 26, 9)
    6  : 17  ::  List(115, 80, 50, 26, 9)
    2  : 13  ::  List(80, 50, 26, 9)
    3  : 9  ::  List(50, 26, 9)
    9  : 5  ::  List(26, 9)
    1  : 3  ::  List(9)
    2  : 1  ::  List()
    res45: String = 1219326311126352690

...321 * ...890 leads to

index   Product of 
sum     Digits
0 =>             1*0 =>      0 => 0 
1 =>       2*0 + 1*9 =>    0+9 => 9 
2 => 3*0 + 2*9 + 1*8 => 0+18+8 =>26 

Ungolfed version:

object BigMul extends App {
   // i is the overrun from the previous value 
  def oSum (l: List[Int], sofar: List[Int] = Nil, i: Int=0): List[Int] = {
    /*
    println (sofar + " <- " + (i/10) + "  : " + (({
        if (l.isEmpty) 0 else l.head} +i) %10) + "  ::  " + {
      if (l.isEmpty) "()" else l.tail} )
    */
    if (l.isEmpty) (i / 10 :: i%10 :: sofar).dropWhile (_==0)  else 
    oSum (l.tail, (l.head + i) % 10 :: sofar, (l.head + i) / 10) 
  }

  // works, but not really ungolfed:
  /* well, yes, this is mapple-di-map
  def mul (p:String,q:String)=
    osum ((p.reverse.zipWithIndex.map {a=>
          q.reverse.zipWithIndex.map (b=>
       (("" + a._1).toInt * ("" + b._1).toInt, a._2 + b._2))}.
       flatten.groupBy (_._2).map (m=>
         (m._1, m._2.map (_._1)sum))).
         toList.sortBy (_._1).map (_._2)).mkString
  */
  // buggy version, but nearly there:
  def mul (s: String, t: String) = {
    val li = for (i <- (s.size -1 to 0 by -1);
      j <- (t.size -1 to 0 by -1);
       a=("" + s(i)).toInt;
      b=("" + t(j)).toInt) 
        yield (a*b, i + j) 
    osum ((li groupBy (_._2)).toList.sortBy (_._1).
      map (_._2.map (_._1).sum)).
      init.mkString.reverse+"0"
  }

  def signedMul (s: String, t: String) = (s(0), t(0)) match {
    case ('-', '-') => mul (s.tail, t.tail)
    case ('-',   _) => "-"+ mul (s.tail, t) 
    case (  _, '-') => "-"+ mul (s, t.tail) 
    case (  _,   _) => mul (s, t) 
  }

  println (signedMul (args (0), args (1)))
}
\$\endgroup\$
9
  • \$\begingroup\$ looks like those central terms are growing... I'm betting you'll blow the 64-bit limit with long enough inputs. \$\endgroup\$
    – boothby
    May 31, 2012 at 23:25
  • \$\begingroup\$ @boothby: That's right. If I multiply "9'999'999'999" (10 digits) with itself, the maximum intermediate value is 810, for 100 nines it is 8100 and for 1k 9s 8'100. At around 50 million nines, which is about 10 books of 500 pages of 70 rows of 60 digits put into the product we reach 4G, the maxint value. To push the border away, I could change the Int to Long which would cost one character. This would allow for 10G of Books full of digits to multiply. Unfortunately, my machine complains already when using 5000*5000 digits about missing Heap to perform the operation, and this is far, far away... \$\endgroup\$ Jun 1, 2012 at 3:17
  • \$\begingroup\$ ... from the limits of intermediate results, represented as Int (which is 2^32 for Scala, not 64, btw.). \$\endgroup\$ Jun 1, 2012 at 3:24
  • \$\begingroup\$ ok, so this will overflow for '9'*(2**26) squared, which is about 67 gigs. I regularly use a machine with 128GB of RAM, and machines with 256GB (probably more) are available today. \$\endgroup\$
    – boothby
    Jun 1, 2012 at 20:04
  • \$\begingroup\$ No. My code produces a list of products, and this list is a(0).size * a(1).size in length, hence it can't produce a result for more than sqrt (Int.MaxValue) digits * 2. However, it finishes a test on 2 inputs, each over 200 digits of nines in less than a second, while your python solution already takes several hours to multiply two shorts. 25 s to multiply 999 by 9999 - that is what a 10 y'o child can reach with pen and paper. I beg I can verify every result you produce, but you can't - not even in 50 years or with your impressing machines. Now completed 9999² in nearly 5 minutes! :) \$\endgroup\$ Jun 2, 2012 at 1:18
2
\$\begingroup\$

C# 619 585

using System.Linq;class P{static void Main(string[] a){var p=new P();string m=p.S(a[0]),n=p.S(a[1]);var l=m.Length+n.Length;var r=p.s+p.C(Enumerable.Range(0,l).Reverse().Select(j=>n.Reverse().Select((y,i)=>(p.C(m.Reverse().Select(z=>(y-48)*(z-48)).ToArray())+new string('0',i)).PadLeft(l,'0')).Select(s=>s[j]-48).Sum()).ToArray()).TrimStart('0');System.Console.WriteLine(r!=""?r:"0");}string C(int[]e){var i=0;var r="";foreach(var z in e.Select(z=>z+i)){i=z/10;r=z%10+r;}return i+r;}string s="";string S(string a){if(!a.StartsWith("-"))return a;s=s==""?"-":"";return a.Substring(1);}}

Test link: http://ideone.com/ghY9G0 (with a small modification: in ideone the input is taken from stdin, as I don't think it's possible to pass command line args).

\$\endgroup\$
2
  • \$\begingroup\$ There is a space that can be removed at if (!a.StartsWith.... Also, I think that string m=p.S(a[0]) can use a var instead. \$\endgroup\$
    – Yytsi
    Jul 30, 2016 at 5:38
  • \$\begingroup\$ @TuukkaX You are right. There are also a lot of extra newlines. I will fix this when I have the time. Thanks! \$\endgroup\$ Jul 30, 2016 at 6:14
1
\$\begingroup\$

GolfScript, 117 chars

-1%" "/~0{1$)\;45={)2%\);\}*}:l~@\l@@""\{15&2$0\{15&2$*+@.!{"\0"+}*(@+@\.10/\10%}%[\](\+@;\;\0\+\}/\;{`+}*\{"-"+}*-1%

Two numbers (optional '-'-sign is supported) separated by space must be given on STDIN. Unfortunately the result printed to STDOUT may have leading zeros.

It is a direct approach implemented in golfscript so it should still be possible to golf this program further.

\$\endgroup\$
3
  • \$\begingroup\$ I think something is wrong - when I run it for 12 x 1 I get 21 (works fine for 1 x 12, though) \$\endgroup\$ May 31, 2012 at 20:07
  • \$\begingroup\$ Sorry, it was my mistake, I didn't pay attention to the input format. It works fine. \$\endgroup\$ Jun 1, 2012 at 7:29
  • \$\begingroup\$ Does this actually work? If so, it's the shortest solution. \$\endgroup\$
    – Polynomial
    Jun 7, 2012 at 13:27
1
\$\begingroup\$

Python, 327

This is utterly terrible. Utterly utterly terrible. I could probably tighten it up (performance- and golf-wise) by implementing proper addition. Instead, I use successive addition & subtraction, brainfuck style. UTTERLY. TERRIBLE. But I guarantee I never blow the 64-bit limit, unlike some other solutions I'm not going to mention. (only... I already commented on them, and I think I just mentioned them)

import sys
a,b=sys.argv[1:]
s=a[0]<'0'
t=b[0]<'0'
a=a[s:][::-1]
b=b[t:][::-1]
a,b=(map(int,x)for x in(a,b))
def x(c,y,r):
 k=0
 while not-1<c[k]-y<10:c[k]=r;k+=1
 c[k]-=y
 if c[-1]<1:c.pop()
e=[]
a*=1-([0]in(a,b))
while a:
 x(a,1,9);d=b[:]
 while d:x(d,1,9);e+=[0];x(e,-1,0)
print'-'*(s^t)+''.join(map(str,e[::-1]+[0]*(e==[])))
\$\endgroup\$
6
  • \$\begingroup\$ You can store Strings of arbitrary size in Python? \$\endgroup\$ Jun 1, 2012 at 19:02
  • \$\begingroup\$ @userunknown, the rules have been updated -- if Python limits string length, that isn't up to me. \$\endgroup\$
    – boothby
    Jun 1, 2012 at 19:48
  • \$\begingroup\$ Haha! You don't blow the 64-bit limit, but Python does? Wait ... \$\endgroup\$ Jun 1, 2012 at 19:51
  • \$\begingroup\$ lol, yup. This code will work for every possible input for which the input & output fit in memory. Being base 10, there's a fairly wide gulf between what you can do with your int accumulator and my carries-in-memory -- as I noted on ugoren's solution. \$\endgroup\$
    – boothby
    Jun 1, 2012 at 19:59
  • \$\begingroup\$ @userunknown: Nope, you can't, but the limit is very high, about 10 **8 \$\endgroup\$
    – univalence
    Jul 30, 2016 at 6:11
1
\$\begingroup\$

Python, 174 Chars (Positive Only)

import sys
a,b=sys.argv[1:]
l=len(a+b)
x=map(int,a[::-1]+'0'*l+b)
i=r=0
t=""
while i<l:r+=sum(x[i-j]*x[-1-j]for j in range(i+1));t=str(r%10)+t;r/=10;i+=1
print t.lstrip('0')
\$\endgroup\$
7
  • \$\begingroup\$ "Must support both positive and negative integers, as well as zero." - this also does not support zero (prints an empty string) \$\endgroup\$ May 31, 2012 at 19:56
  • \$\begingroup\$ @w0lf, Truth is, when I wrote "positive only", I meant that I don't support negative numbers. But as you point out, I was 100% accurate. Yes, I know, it means this isn't a valid answer. I put it in the title to make it clear. I may improve it later. \$\endgroup\$
    – ugoren
    May 31, 2012 at 20:17
  • 2
    \$\begingroup\$ I don't think this is quite kosher... sum(x[i-j]*x[-1-j]for... will likely overflow for i>2**64 \$\endgroup\$
    – boothby
    May 31, 2012 at 21:34
  • 1
    \$\begingroup\$ In ugoren's solution, i is approximately the length of the result of the multiplication. Due to constraints of the memory architecture on x86 (and ARM and most other architectures) no string can have a longer length than fits in a machine word. Therefore any implementation that handles multiplicands on the order of 2**64 must necessarily write to disk or run in multiple processes, which is a ridiculous requirement for a code golf question. Besides, there is a limit to the length of command line arguments to programs, meaning your own instructions dictate that i << 2**64 in all cases. \$\endgroup\$
    – Clueless
    Jun 1, 2012 at 7:51
  • 1
    \$\begingroup\$ My complaint stands, even with the changed rules: 81 > 2^6, so this will overflow on '9'*(2**58) squared. \$\endgroup\$
    – boothby
    Jun 1, 2012 at 19:46
1
\$\begingroup\$

Haskell, 240 bytes

[d]!n=0#map(*d)n;(d:r)!n=0#(zipWith(+)([d]!n++cycle[0])$0:r!n);0#[]=[];z#[]=[z];z#(x:r)=mod(z+x)10:div(z+x)10#r;r=reverse;l=r.map(read.pure).show.abs;a?b|(a<0)/=(b<0)='-'|0<1=' ';main=do[a,b]<-map read<$>getArgs;putStr$a?b:r(l a!l b>>=show)

Try it online!

Could probably be quite a bit shorter but for the rather inconvenient IO format. Implements the "elementary school" multiplication algorithm, storing and processing numbers as lists of ints, representing each digit of a number.

\$\endgroup\$

Your Answer

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

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