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)))
}
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\$2**63
character inputs, well... one of those actually fills up the maximum addressable space of2**63
. Thus, you can't actually store the inputs in memory! Ouch. Set the limit to2**61
so we can store both the inputs and output in memory. \$\endgroup\$