30
\$\begingroup\$

You are given as input two strings representing positive integers in base 10, such as "12345" and "42". Your task is to output a string containing their product, "518490" in this case.

The twist is that you may not use any numerical types in your code. No ints, floats, unsigned longs, etc., no built-in complex number types or arbitrary precision integers, or anything along those lines. You many not use literals of those types, nor any function, method, operator etc. that returns them.

You can use strings, booleans, arrays, or anything else that wouldn't normally be used to represent a number. (But note that neither indexing into an array nor getting its length are likely to be possible without invoking a numeric type.) chars are permitted, but you may not perform any arithmetic or bitwise operations on them or otherwise treat them as anything else other than a token representing part of a string. (Lexicographical comparison of chars is allowed.)

You may not work around the restriction. This includes (but is not limited to) using numeric types inside an eval type function, implicit type conversions into numerical types, using numeric or bitwise operators on non-numeric types that support them, using numerical types stored inside container types, or calling functions or external programs that return numerical results in string form. (I reserve the right to add to this list if other workarounds appear in the answers.) You must implement the multiplication yourself using only non-numeric types.

Input and output may be by any convenient method, as long as the data enters and exits your code in the form of a string. You may assume each of the two input arguments contains only the ASCII characters [0-9] and will not start with 0. Your output shouldn't have leading zeroes either.

One more thing: your code must correctly handle inputs up to at least 10 characters in length, and must run in under a minute on a modern computer for all inputs in that range. Before posting, please check that when given inputs 9999999999 and 9999999999, your program gives an output of 99999999980000000001, in less than a minute. This restriction exists specifically to prevent answers that work by allocating an array of size a*b and then iterating over it, so please bear in mind that answers of that form will not be eligible to win.

This is , so the shortest valid solution (in bytes) wins.

\$\endgroup\$
25
  • \$\begingroup\$ Can we accept "12345" from STDIN rather than 12345? Or can we accept both numbers as "12345", "42"? \$\endgroup\$
    – Justin
    Oct 24, 2014 at 5:35
  • \$\begingroup\$ My first thought was to write a function taking string arguments of length m and n and returning an argument of length m*n. But as the strings have to literally contain the ASCII representation of the numbers, I guess that's against the rules. \$\endgroup\$ Oct 24, 2014 at 5:41
  • 1
    \$\begingroup\$ @xnor in many languages it might be shorter to write out all the cases. But I did find this way in Python: a,b="0123456789x".split('0');c=iter(b).next() if c=='x': c='0' \$\endgroup\$
    – N. Virgo
    Oct 24, 2014 at 6:47
  • 1
    \$\begingroup\$ or in Python 3, a,b="0123456789x".split(x);c,*d=b if c=='x': c='0' \$\endgroup\$
    – N. Virgo
    Oct 24, 2014 at 6:53
  • 2
    \$\begingroup\$ @Nathaniel d='123456789';I=dict(zip('0'+d,d+'0')) \$\endgroup\$
    – Justin
    Oct 24, 2014 at 7:03

13 Answers 13

16
\$\begingroup\$

sed, 339 338 bytes

I know this is an old one, but I was browsing and this piqued my interest. Enough to actually register as a user! I guess I was swayed by "I would quite like to see a full sed solution – Nathaniel"...

s/[1-9]/0&/g
s/[5-9]/4&/g
y/8/4/
s/9/4&/g
s/4/22/g
s/[37]/2x/g
s/[26]/xx/g
s/[1-9]/x/g
:o
s/\( .*\)0$/0\1/
/x$/{
x
G
s/ .*/\n/
:a
s/\(.*\)0\(x*\)\n\(.*\)0\(x*\)\n/\1\n\3\n0\2\4/
ta
s/\n//g
:c
s/^x/0x/
s/0xxxxxxxxxx/x0/
tc
x
s/x$//
}
/ 0/bo
g
s/0x/-x/g
s/xx/2/g
y/x/1/
s/22/4/g
s/44/8/g
s/81/9/g
s/42/6/g
s/21/3/g
s/61/7/g
s/41/5/g
s/-//g

This sed script expects two decimal numbers as input, separated by one space

tests:

time test 518490 = $(./40297.sed <<<)"12345 42" || echo fail
time test 99999999980000000001 = $(./40297.sed <<<"9999999999 9999999999") || echo fail
time test 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 = $(./40297.sed <<<"37975227936943673922808872755445627854565536638199 40094690950920881030683735292761468389214899724061") || echo fail
time test 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413 = $(./40297.sed <<<"33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917") || echo fail

You might recognise last two as RSA-100 (50 x 50 digits) and RSA-768 (116 x 116 digits).

Using GNU sed on a not-very-modern (2007-era Intel Core 2), the last of those takes over a minute, but it comes faster on a newer processor:

  • Q6600: >1 minute
  • i7-3770: 26 seconds
  • i7-6700: 22 seconds

The puny 10-digit multiply specified in the question takes well under a second on any of these (despite being full of pathological nines).

I believe it's standard sed, with no extensions. POSIX guarantees hold space of 8192 bytes only, which limits us to multiplying 400x400 digit numbers, but implementations can provide more. GNU sed is limited only by available memory, so could manage something much bigger, if you're willing to wait.

And I'm confident that I have complied with the rules - that's almost a given in a language that has no numbers. :-)

Explanation

I use a unary/decimal hybrid, converting decimal numbers into a sequence of unary:

 42 => _xxxx_xx

In unary decimal, addition is easy. We iterate from least-significant to most-significant digit, concatenating the x's:

   X=965                   Y=106                                 SUM
   _xxxxxxxxx_xxxxxx_xxxxx _x__xxxxxx
   _xxxxxxxxx_xxxxxx       _x_                          _xxxxxxxxxxx
   _xxxxxxxxx              _x                    _xxxxxx_xxxxxxxxxxx
                                      _xxxxxxxxxx_xxxxxx_xxxxxxxxxxx

We then remove whitespace, and deal with carry by converting 10 consecutive x's to one of the next unit:

 _xxxxxxxxxx_xxxxxx_xxxxxxxxxxx       10.6.11
 _xxxxxxxxxx_xxxxxxx_x                10.7.1
 _x__xxxxxxx_x                        1.0.7.1 

Once we have addition, multiplication is possible. We multiply x*y by considering the last digit of y. Add x to the accumulator that many times, then move to the next digit and shift x one decimal place to the left. Repeat until y is zero.

Expanded code

#!/bin/sed -f

# Convert to unary decimal.  We save two or three bytes of code by
# reusing 0 as the digit separator.
s/[1-9]/0&/g
s/[5-9]/4&/g
y/8/4/
s/9/4&/g
s/4/22/g
s/[37]/2x/g
s/[26]/xx/g
s/[1-9]/x/g

# until y==0

:one

# y ends in zero => x *= 10 and y /= 10
s/\( .*\)0$/0\1/

# while y%10, acc += x, y -= 1
/x$/{
x
G
s/ .*/\n/
# Add x
:add
s/\(.*\)0\(x*\)\n\(.*\)0\(x*\)\n/\1\n\3\n0\2\4/
tadd
s/\n//g
:carry
s/^x/0x/
s/0xxxxxxxxxx/x0/
tcarry

# repeat for each unit of y
x
s/x$//
}

# y?
/ 0/bone


# convert hold space to decimal
g
s/0x/-x/g
s/xx/2/g
y/x/1/
s/22/4/g
s/44/8/g
s/81/9/g
s/42/6/g
s/21/3/g
s/61/7/g
s/41/5/g
s/-//g
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Very satisfying answer, thank you! \$\endgroup\$
    – N. Virgo
    Apr 29, 2015 at 14:05
9
\$\begingroup\$

Python – 312 286 273

D={}
e=t=""
N=[e]
for c in"0123456789":D[c]=t;D[t]=c;t+="I";N+=N
B=lambda s:[D[c]for c in reversed(s)]
Y=B(input())+N
for a in B(input())+N:
 for c in a:
    s=[];o=e
    for a,b in zip(N,Y):i=a+b+o;o=t<=i and"I"or e;s+=i.replace(t,e),;N=s
 Y=[e]+Y
print e.join(B(N)).lstrip("0")

If (lots of) leading zeroes are allowed, the last 12 characters are not needed.

This essentially performs the standard multiplication by hand. Digits are represented as strings of repeated Is (like primitive Roman numerals). Numbers are represented as lists of digits in reverse order. Addition of single digits is performed by cocatenating strings and removing ten Is if necessary.

Here is an ungolfed version:

N = [""] # zero object: list with a lot of empty strings
D = {}   # dictionary for conversion from and to digits
i = ""   # iterates over digits
for c in "0123456789":
    D[c] = i  # map digit to Roman digit
    D[i] = c  # and vice versa
    i += "I"  # increments Roman digit
    N += N    # add leading zeros to zero

ten = "IIIIIIIIII" # Roman digit ten

# Conversion function
B = lambda s: [D[c] for c in reversed(s)]

def Add(x,y):
    Sum = []
    carryover = ""
    for a,b in zip(x,y):
        increment = a+b+carryover
        carryover = "I" if ten in increment else ""
        increment = increment.replace(ten,"") # take increment modulo ten
        Sum += [increment]
    return Sum

def M(x,y):
    Sum = N[:] # Initiate Sum as zero
    X = B(x)+N # Convert and add leading zeros
    Y = B(y)+N
    for a in X:
        for c in a:
            Sum = Add(Sum,p+Y)
        Y = [""] + Y # multiply Y by 10
    return "".join(B(Sum)).lstrip("0") # Convert back and to string, remove leading zeros.

M(input(),input())
\$\endgroup\$
3
  • 1
    \$\begingroup\$ What is this sorcery! How does it work! Wow. Also, here's another golf you could do: def A(x,y):\n S=[];o="" -> def A(x,y,S=[],o=""):. Also, unfortunately, ["","1"][t in i] isn't allowed; it's using a bool to index, treating it as a number. I think that t in i and"1"or"" should work, though. \$\endgroup\$
    – Justin
    Oct 25, 2014 at 17:07
  • \$\begingroup\$ @Quincunx: Defining S as an argument with a default would not have worked, as it would always be the same list even for different calls of the function and thus not reset to []. You were right about ["","1"][t in i], I fixed that. I also added an explanation. \$\endgroup\$
    – Wrzlprmft
    Oct 25, 2014 at 18:42
  • \$\begingroup\$ This is pretty amazing. It gets the green tick for now. (I've edited the question to clarify that leading zeroes in the output aren't allowed - sorry!) \$\endgroup\$
    – N. Virgo
    Oct 26, 2014 at 0:33
7
\$\begingroup\$

Ruby: 752 698

This is just to get an answer out there, just done out of curiosity. Edited: now golfed a bit.

$F='0123456789'
$G="#{$F}abcdefghij"
def x(a,b);p(a=~/[13579]$/?b:"",a==""?"":x(Hash[*%w(b0 5 b1 6 b2 7 b3 8 b4 9)].to_a.inject(a.tr($F,'0011223344').chars.zip(a.tr($F,'ababababab').chars).flatten.join("")){|n,q|k,v=q;n.gsub(k,v)}.gsub(/[ab]/,'').sub(/^0*/,''),p(b,b)));end
def p(a,b);j,k=["0#{a}","0#{b}"].map{|c|c.gsub(/./,'0')};c="#{k}#{a}".chars.zip("#{j}#{b}".chars).drop_while{|z|z==%w(0 0)}.map{|m|$G.sub(/#{m.map{|n|"122333444455555666666777777788888888999999999".chars.select{|c|c==n}}.flatten.map{|c|'.'}.join("")}/,"").chars.first}.flatten.join("");d=nil;
while c!=d
 d=c;c="0#{d}".gsub(/[0-9][a-j]/) {|m| m.tr($G,"123456789a#{$F}")}.sub(/^0/,'')
end;c;end
puts x(ARGV.shift,ARGV.shift)

Usage: I had this in a file called peasant.rb:

$ time ruby peasant.rb 9999999999 9999999999
99999999980000000001

real    0m0.129s
user    0m0.096s
sys 0m0.027s

Explanation: it's peasant multiplication, so I repeatedly halve&double. Halving is done by halving digits & marking remainders like so: 1234 -> 0b1a1b2a; then find and replace on the b's: 06a17a; then cleaning up -> 617.

Addition is done like so... first of all, I pad both strings to the same length and make pairs from the digits. Then I add the digits by constructing a string that has the length of each digit and concatenating; I remove a string of that length from the start of '0123456789abcdefghij', and then keep the first char. So, eg, "9"+"9"->"i". NB I avoid actually using length functions here to avoid number types entirely; removing the prefix is done with a regexp instead.

So now I have a string containing a mix of digits and letters. The letters represent numbers with a carry digit; I prepend 0 to the number, then repeatedly replace digit-letter patterns with the result of the carry until the addition is complete.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Very clever answer, exactly the sort of thing I was hoping to see! \$\endgroup\$
    – N. Virgo
    Oct 24, 2014 at 13:31
  • 1
    \$\begingroup\$ I'm actually hoping someone will post one with Church numerals! \$\endgroup\$
    – bazzargh
    Oct 24, 2014 at 13:32
  • \$\begingroup\$ That would be cool, though I'm not sure if it would work with the efficiency requirement - I think converting between strings and Church numerals would effectively involve counting up to 99999999980000000001. \$\endgroup\$
    – N. Virgo
    Oct 24, 2014 at 13:44
7
\$\begingroup\$

Brainfuck (1328 bytes)

Considerations at first:

  • Not sure if brainfuck is a valid answer to this questions since I'm not sure whether you consider the cell values as 'numerical types' or not. I don't think so since bf doesn't know types, but that's my own opinion, please correct me if I'm wrong.
  • An implementation supporting (nearly) unlimited values is necessary.
  • It might be far too slow, based on the implementation.

I only tested the program with my own interpreter, you can find it here.

Input must be both numbers separated by a single ASCII space.

Golfed:

,>++++++[<----->-]<--[>,>++++++[<----->-]<--]>>>+<<<<[>>++++[<<---->>-]<<[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<,[>,]>>>+<<<<[>>+++++++[<<------->>-]<<+[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<<<<<[>>[>+>+<<-]>>[<<+>>-]<<<<-]>>[-]>[<+>-]<[>>+>+<<<-]>>>[<<<+>>>-]<[[-]<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<-]>[<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<->>[-]]+>-]<-]<<+>]<[>>+<<-]>>[<<<[>+>+<<-]>>[<<+>>-]>-]<<[<<->>-]<[-]<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>[>>]+[<<]>[>[>>]<+<[<<]>-]<<<<<<<<<<[>>+>+<<<-]>>>[<<<+>>>-]+[<+>-]<<<[-]>>[<<+>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+<<-]>>[<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<<->>>[-]]+>-]<-]<<<+>>]<[-]<<<<[-]>>>[<<<+>>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[<+>-]<]<[>+>+<<-]>>[<<+>>-]<[>+<[-]]+>[<[-]<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[[-]>>>>>>>>[>>]<[<[<<]<<<<<+>>>>>>>[>>]<-]<-<<[<<]<<<<<>++++++++++++++++++++++++++++++++++++++++++++++++[<+>-]<.[-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]+[<->-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<[<+>-]<]<[-]]<[>>++++++[<++++++++>-]<.[-]<[-]]<[-]<[-]>>>>>>>>>>>>[>[-]>]<<[-<<]<<<<<<<<<<<<<<<<<[-]<[-]

Ungolfed:

,
>++++++[<----->-]<--
[                                           # read input until space
    >,
    >++++++[<----->-]<--                    # decrease cell by 32 to check if it's a space
]
>>>+<<<<                                    # set multiplier to 1

[

    >>++++[<<---->>-]<<                     # decrease by 16 to get cell value of number

    [>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]        # multiply value by multiplier
    >>>>>[<<<<<+>>>>>-]                     # copy value back
    <[>++++++++++<-]>[<<+>>-]               # multiply multiplier by 10
    <<<<<                                   # go back to number

    [->+<]>[-<+>]                           # add value to next cell and move sum to previous cell

    <<                                      # go to next number
]

>>>>[-]<                                    # delete old multiplier

,[>,]                                       # read second number until end of input
>>>+<<<<                                    # set new multiplier

[

    >>+++++++[<<------->>-]<<+              # decrease by 48 to get cell value of number

    [>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]        # multiply value by multiplier
    >>>>>[<<<<<+>>>>>-]                     # copy value back
    <[>++++++++++<-]>[<<+>>-]               # multiply multiplier by 10
    <<<<<                                   # go back to number

    [->+<]>[-<+>]                           # add value to next cell and move sum to previous cell

    <<                                      # go to next number
]

>>>>[-]<<<<<                                # delete multiplier

[>>[>+>+<<-]>>[<<+>>-]<<<<-]>>[-]>          # multiply both values

# magical algorithm for printing cell value as number taken from Cedric Mamo's code from a previous question
[<+>-]<[>>+>+<<<-]>>>[<<<+>>>-]<[[-]<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<-]>[<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<->>[-]]+>-]<-]<<+>]<[>>+<<-]>>[<<<[>+>+<<-]>>[<<+>>-]>-]<<[<<->>-]<[-]<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>[>>]+[<<]>[>[>>]<+<[<<]>-]<<<<<<<<<<[>>+>+<<<-]>>>[<<<+>>>-]+[<+>-]<<<[-]>>[<<+>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+<<-]>>[<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<<->>>[-]]+>-]<-]<<<+>>]<[-]<<<<[-]>>>[<<<+>>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[<+>-]<]<[>+>+<<-]>>[<<+>>-]<[>+<[-]]+>[<[-]<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[[-]>>>>>>>>[>>]<[<[<<]<<<<<+>>>>>>>[>>]<-]<-<<[<<]<<<<<>++++++++++++++++++++++++++++++++++++++++++++++++[<+>-]<.[-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]+[<->-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<[<+>-]<]<[-]]<[>>++++++[<++++++++>-]<.[-]<[-]]<[-]<[-]>>>>>>>>>>>>[>[-]>]<<[-<<]<<<<<<<<<<<<<<<<<[-]<[-]

I've taken the code for the output of the value from this answer, thanks to the author for that!

The program might not be valid, but in either way I wanted to share it with you ^^

Update: You can now test it (only for small multiplications) here, thanks to @Sp3000's answer to this contest and SE's new Stack Snippets!

var NUM_CELLS = 30000;var ITERS_PER_SEC = 100000;var TIMEOUT_MILLISECS = 5000;function clear_output(){document.getElementById("output").value="";document.getElementById("stderr").innerHTML=""}function stop(){running=false;document.getElementById("run").disabled=false;document.getElementById("stop").disabled=true;document.getElementById("clear").disabled=false;document.getElementById("wrap").disabled=false;document.getElementById("timeout").disabled=false;document.getElementById("eof").disabled=false}function interrupt(){error(ERROR_INTERRUPT)}function error(e){document.getElementById("stderr").innerHTML=e;stop()}function run(){clear_output();document.getElementById("run").disabled=true;document.getElementById("stop").disabled=false;document.getElementById("clear").disabled=true;document.getElementById("wrap").disabled=true;document.getElementById("timeout").disabled=true;document.getElementById("eof").disabled=true;code=document.getElementById("code").value;input=document.getElementById("input").value;wrap=document.getElementById("wrap").value;timeout=document.getElementById("timeout").checked;eof=document.getElementById("eof").value;loop_stack=[];loop_map={};for(var e=0;e<code.length;++e){if(code[e]=="["){loop_stack.push(e)}else if(code[e]=="]"){if(loop_stack.length==0){error(ERROR_BRACKET);return}else{var t=loop_stack.pop();loop_map[t]=e;loop_map[e]=t}}}if(loop_stack.length>0){error(ERROR_BRACKET);return}running=true;start_time=Date.now();code_ptr=0;input_ptr=0;cell_ptr=Math.floor(NUM_CELLS/2);cells={};iterations=0;bf_iter(1)}function bf_iter(e){if(code_ptr>=code.length||!running){stop();return}var t=Date.now();for(var n=0;n<e;++n){if(cells[cell_ptr]==undefined){cells[cell_ptr]=0}switch(code[code_ptr]){case"+":if(wrap=="8"&&cells[cell_ptr]==255||wrap=="16"&&cells[cell_ptr]==65535||wrap=="32"&&cells[cell_ptr]==2147483647){cells[cell_ptr]=0}else{cells[cell_ptr]++}break;case"-":if(cells[cell_ptr]==0){if(wrap=="8"){cells[cell_ptr]=255}if(wrap=="16"){cells[cell_ptr]=65535}if(wrap=="32"){cells[cell_ptr]=2147483647}}else{cells[cell_ptr]--}break;case"<":cell_ptr--;break;case">":cell_ptr++;break;case".":document.getElementById("output").value+=String.fromCharCode(cells[cell_ptr]);break;case",":if(input_ptr>=input.length){if(eof!="nochange"){cells[cell_ptr]=parseInt(eof)}}else{cells[cell_ptr]=input.charCodeAt(input_ptr);input_ptr++}break;case"[":if(cells[cell_ptr]==0){code_ptr=loop_map[code_ptr]}break;case"]":if(cells[cell_ptr]!=0){code_ptr=loop_map[code_ptr]}break}code_ptr++;iterations++;if(timeout&&Date.now()-start_time>TIMEOUT_MILLISECS){error(ERROR_TIMEOUT);return}}setTimeout(function(){bf_iter(ITERS_PER_SEC*(Date.now()-t)/1e3)},0)}var ERROR_BRACKET="Mismatched brackets";var ERROR_TIMEOUT="Timeout";var ERROR_INTERRUPT="Interrupted by user";var code,input,wrap,timeout,eof,loop_stack,loop_map;var running,start_time,code_ptr,input_ptr,cell_ptr,cells,iterations
<div style="font-size:12px;font-family:Verdana, Geneva, sans-serif;"> <div style="float:left; width:50%;"> Code: <br> <textarea id="code" rows="4" style="overflow:scroll;overflow-x:hidden;width:90%;">,>++++++[<----->-]<--[>,>++++++[<----->-]<--]>>>+<<<<[>>++++[<<---->>-]<<[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<,[>,]>>>+<<<<[>>+++++++[<<------->>-]<<+[>>>>[>+>+<<-]>>[<<+>>-]<<<<<<-]>>>>>[<<<<<+>>>>>-]<[>++++++++++<-]>[<<+>>-]<<<<<[->+<]>[-<+>]<<]>>>>[-]<<<<<[>>[>+>+<<-]>>[<<+>>-]<<<<-]>>[-]>[<+>-]<[>>+>+<<<-]>>>[<<<+>>>-]<[[-]<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<-]>[<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<->>[-]]+>-]<-]<<+>]<[>>+<<-]>>[<<<[>+>+<<-]>>[<<+>>-]>-]<<[<<->>-]<[-]<[>>>>>>>>+<<<<<<<<-]>>>>>>>>>[>>]+[<<]>[>[>>]<+<[<<]>-]<<<<<<<<<<[>>+>+<<<-]>>>[<<<+>>>-]+[<+>-]<<<[-]>>[<<+>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]++++++++++<[>>+<<-]>>[<[>>+>+<<<-]>>>[<<<+>>>-]<[>+<<-[>>[-]>+<<<-]>>>[<<<+>>>-]<[<-[<<<->>>[-]]+>-]<-]<<<+>>]<[-]<<<<[-]>>>[<<<+>>>-]<<<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[<+>-]<]<[>+>+<<-]>>[<<+>>-]<[>+<[-]]+>[<[-]<[>>>+>+<<<<-]>>>>[<<<<+>>>>-]<[[-]>>>>>>>>[>>]<[<[<<]<<<<<+>>>>>>>[>>]<-]<-<<[<<]<<<<<>++++++++++++++++++++++++++++++++++++++++++++++++[<+>-]<.[-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]+[<->-]<<<<<[-]>>>>[<<<<+>>>>-]<<<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<[<+>-]<]<[-]]<[>>++++++[<++++++++>-]<.[-]<[-]]<[-]<[-]>>>>>>>>>>>>[>[-]>]<<[-<<]<<<<<<<<<<<<<<<<<[-]<[-]</textarea> <br>Input: <br> <textarea id="input" rows="2" style="overflow:scroll;overflow-x:hidden;width:90%;">7 6</textarea> <p> Wrap: <select id="wrap"> <option value="8">8-bit</option> <option value="16">16-bit</option> <option value="32" selected="selected">32-bit</option> </select> &nbsp; Timeout: <input id="timeout" type="checkbox"></input>&nbsp; EOF: <select id="eof"> <option value="nochange">Same</option> <option value="0" selected="selected">0</option> <option value="-1">-1</option> </select> </p> </div> <div style="float:left; width:50%;"> Output: <br> <textarea id="output" rows="6" style="overflow:scroll;width:90%;"></textarea> <p> <input id="run" type="button" value="Run" onclick="run()"></input> <input id="stop" type="button" value="Stop" onclick="interrupt()" disabled="true"></input> <input id="clear" type="button" value="Clear" onclick="clear_output()"></input> &nbsp; <span id="stderr" style="color:red"></span></p></div></div>

\$\endgroup\$
2
  • \$\begingroup\$ I don't know if it's valid either! I guess either everything's a number in Brainfuck, or nothing is. \$\endgroup\$
    – N. Virgo
    Oct 24, 2014 at 13:21
  • \$\begingroup\$ I like this answer. I ve been messing about with bf myself lately. it kind of sheds light on the fact that at the machine level, everything is just tokens anyway. Hard to say whether this really follows the rules or not. \$\endgroup\$
    – Octopus
    Oct 24, 2014 at 16:50
6
\$\begingroup\$

Haskell - 180 206 214

r=reverse
f=filter
z=['0'..'9']
a?f|f="1"!a
a?_=a
(a:b)!(c:d)=e:b!d?(e<a)where e=fst$last$zip(f(>=c)z++z)$f(<=a)z
a!c=a++c
a%(b:c)=foldr(!)('0':a%c)$f(<b)z>>[a]
_%b=b
a#b=r$r a%r b

Implements multiplication via repeated addition, and all kinds of digit magic are handled by shifting and filtering the ['0'..'9'] list. Defines an operator # of the type String -> String -> String:

*> :set +s
*> "9990123456789"#"9999876543210"
"99900001219316321126352690"
(0.02 secs, 9862288 bytes)
\$\endgroup\$
3
  • \$\begingroup\$ Looks like we have a new winner! (Though as before, I can't read Haskell of this degree of sophistication - can someone independently check it meets the spec?) \$\endgroup\$
    – N. Virgo
    Apr 30, 2015 at 10:16
  • \$\begingroup\$ (Also the ['0'..'9'] feels a bit like implicitly treating chars as numbers that can be iterated - is there a short way to generate that list from the string "0123456789" instead?) \$\endgroup\$
    – N. Virgo
    Apr 30, 2015 at 10:16
  • \$\begingroup\$ @Nathaniel Well first of all the string "0123456789" is the list ['0'..'9']. Second, in Haskell [a..b] is an enumeration, types that have declared instances of the Enum typeclass can be enumerated like that, and the declaration describes how the enumeration works. Bool, the boolean type also has an instance, and therefore you can also do [False..True]. There are barely any numbers involved. \$\endgroup\$
    – mniip
    Apr 30, 2015 at 18:07
6
\$\begingroup\$

Python, 394 349 340 chars

D='0123456789'
R=reversed
U=lambda x:[R for y in D if y<x]
T=U(':')
def A(a,b,r='',c=[]):
 for x,y in map(None,R(a),R(b)):
    d=U(x)+U(y)+c;t=T;c=[R]
    if d<T:t=c=[]
    r=min(k for k in D if U(k)+t>=d)+r
 if c:r='1'+r
 return r
a,b=input()
m=''
while b:
 if list(b).pop()in'13579':m=A(m,a)
 b=list(A(b,A(b,A(b,A(b,b)))));b.pop();a=A(a,a)
print m

Run like:

echo '"9999999999","9999999999"' | ./mulstr.py

Takes 50 milliseconds.

Uses Russian Peasant multiplication. When adding digits, we convert them to unary ('5' => [R,R,R,R,R]), concatenate the lists, then convert back. U converts to unary, using R as the unary digit. We compute b/=2 as b=b*5/10.

\$\endgroup\$
8
  • \$\begingroup\$ A couple golfs: def A(a,b):\n r='';c=[] -> def A(a,b,r='',c=[]):, similarly for def M. You might be able to change for z in D:d.pop()\n c=['X'] to [d.pop()for z in D];c=['X'], in which case you could even collapse it onto the previous if. Also, can if list(b).pop()in'13579' just be if b[:].pop()in'13579'? \$\endgroup\$
    – Justin
    Oct 25, 2014 at 2:53
  • \$\begingroup\$ @Quincunx: Thanks. The last one won't work because on the first iteration b is a string, not a list. \$\endgroup\$ Oct 25, 2014 at 5:27
  • \$\begingroup\$ You could skip M and write a complete program; a,b=input() is allowed. \$\endgroup\$
    – Justin
    Oct 25, 2014 at 6:05
  • 1
    \$\begingroup\$ b*5/10 is a nice trick. \$\endgroup\$
    – bazzargh
    Oct 25, 2014 at 13:33
  • \$\begingroup\$ I just stumbled upon reduce, which allows you to nicen A(b,A(b,A(b,A(b,b)))) to reduce(A,[b,b,b,b,b]). Sadly, this does not affect the character count. \$\endgroup\$
    – Wrzlprmft
    Oct 26, 2014 at 8:54
5
\$\begingroup\$

JavaScript (E6) 375 395 411 449

Edit Golfed
Edit Bug fixed: missing clearing a carry flag

It can be done with just symbol manipulation in near 0 time.
In this version you could use any char instead of the digits, as long as the symbol are in ascending order.

Notes: using strings, hashmap with string key, arrays used as list. No indexing, the arrays are traversed using 'map' or rotated using push & shift.
All '+' are string concatenation.

M=(x,y,S=a=>a.shift()||z,R=a=>[...a].reverse(),e=R('9876543210'),d=[...e])=>
  R(y)[T='map'](b=>
     R(x)[T](a=>(
       u=R[e[a+=b]+v],
       v=R[S[a]+(u<v?'1':z)],
       p[P](t=R[S(o)+u]),
       t<u?v=R[v+'1']:v
     ),o=p,p=[])
    +(v>z&&p[P](v),x+=v=z),
    d[T](a=>d[T](b=>e[P='push'](R[a+b]=S(e)))+e[P](S(e))),  
    d[T](a=>d[T](b=>e[d[T](c=>v=c<a?(u=R[u+b])<b?R[v+'1']:v:v,v=u=z='0'),S[a+b]=v,a+b]=u)),
    p=[v=z]
  )&&R(p).join(o)

Less Golfed (maybe I'll add an explanation tomorrow)

M=(x,y)=>(
  R=a=>[...a].reverse(),
  // Addition table s 
  s={},
  e=[...'9012345678'],
  [for(a of(d='0123456789'))for(b of(e.push(e.shift()),d))e.push(s[a+b]=c=e.shift())],
  // Multiplication table m,n
  m={},n={},
  [for(a of d)for(b of d)(
     [for(c of(z=u=v='0',d))
     c<a&&(t=s[u+b],t<u?v=s[v+'1']:v,u=t)
     ],m[a+b]=u,n[a+b]=v
  )],
  x=R(x),v=z,o=[],p=[],
  [for(b of R(y))(
     [for(a of x)(
       u=s[m[a+b]+v],v=s[n[a+b]+(u<v?'1':z)],
       p.push(t=s[(o.shift()||z)+u]),
       t<u?v=s[v+'1']:v
     )],
     v>z?p.push(v):o,o=p,p=[],x.unshift(v=z)
  )],
  R(o).join('')
)

Test In FireFox/FireBug console

t0=-new Date
r=M('9999999999','9999999999')
t1=-new Date
console.log("Result",r, "time ms", t0-t1)

Output

Result 99999999980000000001 time ms 14
\$\endgroup\$
4
  • \$\begingroup\$ Possibly there's a slight bug - the output from the 9999999999 case should be 99999999980000000001, not 99999999980000000081 \$\endgroup\$
    – N. Virgo
    Oct 24, 2014 at 14:30
  • \$\begingroup\$ :( going to check \$\endgroup\$
    – edc65
    Oct 24, 2014 at 14:35
  • \$\begingroup\$ If you're using multiplication tables, how are you getting around the fact that summation isn't allowed? \$\endgroup\$
    – COTO
    Oct 24, 2014 at 14:35
  • 1
    \$\begingroup\$ Summation IS allowed using a hashtable (s in the code). Ex. s['34'] --> '7'. Just symbols, not numbers. Could be s['cd'] -->'g' \$\endgroup\$
    – edc65
    Oct 24, 2014 at 14:50
5
\$\begingroup\$

Haskell, 231 bytes

This defines an operator # which multiplies two string representations of natural numbers. It works by defining an elementary increment/decrement operation on strings, then uses it to build up addition and multiplication. A little extra magic gives some exponential speedups that make it all possible..

r=reverse
n="9876543210"
t=True
c&(x:y)|c==x=head y|t=c&y
m%[]="1";m%(c:s)|c==last m=head m:m%s|t=c&m:s
[]!y=y;x![]=x;(x:a)!('0':b)=x:a!b;x!y=(r n%x)!(n%y)
"0"?_="0";x?('0':y)|all(=='0')y="0"|t=('0':x)?y;x?y=x?(n%y)!x
x#y=r$r x?r y

This approach is fast enough that even on a 2008 laptop in the unoptimized ghci REPL, the test case takes just a fraction of a second:

λ> :set +s
λ> let test = replicate 10 '9'
(0.00 secs, 0 bytes)
λ> test
"9999999999"
(0.00 secs, 1069784 bytes)
λ> test # test
"99999999980000000001"
(0.06 secs, 13451288 bytes)

Here's a check that all of the two-digit products are correct:

λ> and [ show (x * y) == (show x # show y) | x <- [0..100], y <- [0..100] ]
True
\$\endgroup\$
2
  • \$\begingroup\$ Looks like we have a new leader! (I can't read Haskell though - can someone independently confirm that it fits the spec?) \$\endgroup\$
    – N. Virgo
    Oct 29, 2014 at 5:15
  • 1
    \$\begingroup\$ Yes, that's perfectly cromulent haskell, it fits the spec, and works as advertised. Good job! \$\endgroup\$
    – bazzargh
    Oct 29, 2014 at 12:24
3
\$\begingroup\$

JavaScript: 3710 3604 bytes

  • Using string lookup tables with 1 digit multiplication and add with carry.
  • The multiplication is done by digit x digit instead of digit x line.

Golf:

var M={
'00':'0','01':'0','02':'0','03':'0','04':'0','05':'0','06':'0','07':'0','08':'0','09':'0',
'10':'0','11':'1','12':'2','13':'3','14':'4','15':'5','16':'6','17':'7','18':'8','19':'9',
'20':'0','21':'2','22':'4','23':'6','24':'8','25':'10','26':'12','27':'14','28':'16','29':'18',
'30':'0','31':'3','32':'6','33':'9','34':'12','35':'15','36':'28','37':'21','38':'24','39':'27',
'40':'0','41':'4','42':'8','43':'12','44':'16','45':'20','46':'24','47':'28','48':'32','49':'36',
'50':'0','51':'5','52':'10','53':'15','54':'20','55':'25','56':'30','57':'35','58':'40','59':'45',
'60':'0','61':'6','62':'12','63':'18','64':'24','65':'30','66':'36','67':'42','68':'48','69':'54',
'70':'0','71':'7','72':'14','73':'21','74':'28','75':'35','76':'42','77':'49','78':'56','79':'63',
'80':'0','81':'8','82':'16','83':'24','84':'32','85':'40','86':'48','87':'56','88':'64','89':'72',
'90':'0','91':'9','92':'18','93':'27','94':'36','95':'45','96':'54','97':'63','98':'72','99':'81'
};
var A={
'000':'0','001':'1','002':'2','003':'3','004':'4','005':'5','006':'6','007':'7','008':'8','009':'9',
'010':'1','011':'2','012':'3','013':'4','014':'5','015':'6','016':'7','017':'8','018':'9','019':'10',
'020':'2','021':'3','022':'4','023':'5','024':'6','025':'7','026':'8','027':'9','028':'10','029':'11',
'030':'3','031':'4','032':'5','033':'6','034':'7','035':'8','036':'9','037':'10','038':'11','039':'12',
'040':'4','041':'5','042':'6','043':'7','044':'8','045':'9','046':'10','047':'11','048':'12','049':'13',
'050':'5','051':'6','052':'7','053':'8','054':'9','055':'10','056':'11','057':'12','058':'13','059':'14',
'060':'6','061':'7','062':'8','063':'9','064':'10','065':'11','066':'12','067':'13','068':'14','069':'15',
'070':'7','071':'8','072':'9','073':'10','074':'11','075':'12','076':'13','077':'14','078':'15','079':'16',
'080':'8','081':'9','082':'10','083':'11','084':'12','085':'13','086':'14','087':'15','088':'16','089':'17',
'090':'9','091':'10','092':'11','093':'12','094':'13','095':'14','096':'15','097':'16','098':'17','099':'18',
'100':'1','101':'2','102':'3','103':'4','104':'5','105':'6','106':'7','107':'8','108':'9','109':'10',
'110':'2','111':'3','112':'4','113':'5','114':'6','115':'7','116':'8','117':'9','118':'10','119':'11',
'120':'3','121':'4','122':'5','123':'6','124':'7','125':'8','126':'9','127':'10','128':'11','129':'12',
'130':'4','131':'5','132':'6','133':'7','134':'8','135':'9','136':'10','137':'11','138':'12','139':'13',
'140':'5','141':'6','142':'7','143':'8','144':'9','145':'10','146':'11','147':'12','148':'13','149':'14',
'150':'6','151':'7','152':'8','153':'9','154':'10','155':'11','156':'12','157':'13','158':'14','159':'15',
'160':'7','161':'8','162':'9','163':'10','164':'11','165':'12','166':'13','167':'14','168':'15','169':'16',
'170':'8','171':'9','172':'10','173':'11','174':'12','175':'13','176':'14','177':'15','178':'16','179':'17',
'180':'9','181':'10','182':'11','183':'12','184':'13','185':'14','186':'15','187':'16','188':'17','189':'18',
'190':'10','191':'11','192':'12','193':'13','194':'14','195':'15','196':'16','197':'17','198':'18','199':'19'
} 
Array.prototype.e=function(){return(''+this)==='';}
String.prototype.s=function(){return this.split('').reverse();}
function B(a,b,c) {
var r='',s='';
a=a.s();
b=b.s();
while (!a.e()||!b.e()||c!=='0') {
x=a.e()?'0':a.shift();
y=b.e()?'0':b.shift();
s=A[c+x+y];
s=s.s();
r=s.shift()+r;
c=s.e()?'0':'1';
}
return r;
}
function m(a,b) {
var s='0',m='';
b.split('').reverse().forEach(function(e){
var z=m;
a.split('').reverse().forEach(function(f){s=B(s,M[e+f]+z,'0');z+='0';});
m+='0';
});
return s;
}

Ungolfed with tests:

var mul = {
'00':'0','01':'0','02':'0','03':'0','04':'0','05':'0','06':'0','07':'0','08':'0','09':'0',
'10':'0','11':'1','12':'2','13':'3','14':'4','15':'5','16':'6','17':'7','18':'8','19':'9',
'20':'0','21':'2','22':'4','23':'6','24':'8','25':'10','26':'12','27':'14','28':'16','29':'18',
'30':'0','31':'3','32':'6','33':'9','34':'12','35':'15','36':'28','37':'21','38':'24','39':'27',
'40':'0','41':'4','42':'8','43':'12','44':'16','45':'20','46':'24','47':'28','48':'32','49':'36',
'50':'0','51':'5','52':'10','53':'15','54':'20','55':'25','56':'30','57':'35','58':'40','59':'45',
'60':'0','61':'6','62':'12','63':'18','64':'24','65':'30','66':'36','67':'42','68':'48','69':'54',
'70':'0','71':'7','72':'14','73':'21','74':'28','75':'35','76':'42','77':'49','78':'56','79':'63',
'80':'0','81':'8','82':'16','83':'24','84':'32','85':'40','86':'48','87':'56','88':'64','89':'72',
'90':'0','91':'9','92':'18','93':'27','94':'36','95':'45','96':'54','97':'63','98':'72','99':'81'
};

var adc = {
'000':'0','001':'1','002':'2','003':'3','004':'4','005':'5','006':'6','007':'7','008':'8','009':'9',
'010':'1','011':'2','012':'3','013':'4','014':'5','015':'6','016':'7','017':'8','018':'9','019':'10',
'020':'2','021':'3','022':'4','023':'5','024':'6','025':'7','026':'8','027':'9','028':'10','029':'11',
'030':'3','031':'4','032':'5','033':'6','034':'7','035':'8','036':'9','037':'10','038':'11','039':'12',
'040':'4','041':'5','042':'6','043':'7','044':'8','045':'9','046':'10','047':'11','048':'12','049':'13',
'050':'5','051':'6','052':'7','053':'8','054':'9','055':'10','056':'11','057':'12','058':'13','059':'14',
'060':'6','061':'7','062':'8','063':'9','064':'10','065':'11','066':'12','067':'13','068':'14','069':'15',
'070':'7','071':'8','072':'9','073':'10','074':'11','075':'12','076':'13','077':'14','078':'15','079':'16',
'080':'8','081':'9','082':'10','083':'11','084':'12','085':'13','086':'14','087':'15','088':'16','089':'17',
'090':'9','091':'10','092':'11','093':'12','094':'13','095':'14','096':'15','097':'16','098':'17','099':'18',
'100':'1','101':'2','102':'3','103':'4','104':'5','105':'6','106':'7','107':'8','108':'9','109':'10',
'110':'2','111':'3','112':'4','113':'5','114':'6','115':'7','116':'8','117':'9','118':'10','119':'11',
'120':'3','121':'4','122':'5','123':'6','124':'7','125':'8','126':'9','127':'10','128':'11','129':'12',
'130':'4','131':'5','132':'6','133':'7','134':'8','135':'9','136':'10','137':'11','138':'12','139':'13',
'140':'5','141':'6','142':'7','143':'8','144':'9','145':'10','146':'11','147':'12','148':'13','149':'14',
'150':'6','151':'7','152':'8','153':'9','154':'10','155':'11','156':'12','157':'13','158':'14','159':'15',
'160':'7','161':'8','162':'9','163':'10','164':'11','165':'12','166':'13','167':'14','168':'15','169':'16',
'170':'8','171':'9','172':'10','173':'11','174':'12','175':'13','176':'14','177':'15','178':'16','179':'17',
'180':'9','181':'10','182':'11','183':'12','184':'13','185':'14','186':'15','187':'16','188':'17','189':'18',
'190':'10','191':'11','192':'12','193':'13','194':'14','195':'15','196':'16','197':'17','198':'18','199':'19'
} 

Array.prototype.isEmpty = function() {
  return (''+this) === '';
}

function add(a, b, c) {
  var r = '', s = '';
  a = a.split("").reverse();
  b = b.split("").reverse();
  while (!a.isEmpty() || !b.isEmpty() || c !== '0') {
    x = a.isEmpty() ? '0' : a.shift();
    y = b.isEmpty() ? '0' : b.shift();
    s = adc[c + x + y];
    s = s.split("").reverse();
    r = (s.shift()) + r;
    c = (s.isEmpty()) ? '0' : '1';
  }
  return r;
}

function mult(a, b) {
  var s = '0';
  var m = '';
  b.split('').reverse().forEach(function(e) {
    var z = m;
    a.split('').reverse().forEach(function(f) {
      s = add(s, mul[e + f] + z, '0');
      z = z + '0';
    });
    m = m + '0';
  } );
  return s;
}

function test(a, b) {
  var t0 = (new Date()).getTime();
  var r = mult(a,b);
  var t1 = (new Date()).getTime();
  var e = t1 - t0;
  console.log('mult ' + a + ' * ' + b + ' = ' + r + " (" + e + " ms)");
}

test('12345', '42');
test('9999999999', '9999999999');

This outputs:

mult 12345 * 42 = 518490 (3 ms) 
mult 9999999999 * 9999999999 = 99999999980000000001 (47 ms) 
\$\endgroup\$
2
\$\begingroup\$

Python 2 (555)

I wouldn't normally answer my own challenge so quickly (or at all), but I wanted to prove it could be done. (Luckily some other answers did that before this one, but I couldn't help wanting to finish it.) There's some more golfing that could be done, but I think this is reasonable. It handles the 9999999999x9999999999 case in under 0.03s on my machine.

d="123456789";I=dict(zip('0'+d,d+'0'))
def r(x):return reversed(x)
def s(x):return''.join(x)
def i(x):
    try:
        h=I[x.next()]
        if h!='0':h+=s(x)
        else:h+=i(x)
        return h
    except:return'1'
def b(x,y):
    for c in'0'+d:
        if c==y:break
        x=iter(i(x))
    return x
def a(x,y):
    z=''
    for c in y:
        x=b(x,c)
        try:z+=x.next()
        except:z+='0'
    return z+s(x)
def n(x,y):
    z='0'
    for c in'0'+d:
        if c==y:break
        z=a(iter(z),x)
    return z
def o(x,y):
    x=s(x)
    l='';z=''
    for c in y:
        z=a(iter(z),l+s(n(x,c)))
        l+='0'
    return z
def m(x,y):
    return s(r(o(r(x),r(y))))

Example use: m("12345","42")

It works by doing long multiplication using string manipulations. Sometimes the variables are strings and sometimes they're iterators over strings, which makes it possible to get the first element without using an integer literal. Everything's stored with the digits reversed, so that the first element is the least significant digit.

Here's a function-by-function explanation:

  • r and s are bookkeeping functions. (r is just an alias for reversed, which makes a reverse iterator, and s converts iterators into strings.)

  • i increments the number in a string by 1, including cases like 39+1=40 and 99+1=100.

  • b adds x and y, but y must be only one digit. It works by incrementing x y times.

  • a adds two numbers together that can both have multiple digits, by calling b for each digit in y.

  • n multiplies x and y, but y must be only one digit. It works by adding x to itself y times.

  • o multiplies x and y, where both arguments can have multiple digits. It uses classic long-multiplication

  • m just converts its string inputs into reverse iterators and hands them to o, then reverses the result and converts it into a string.

\$\endgroup\$
4
  • \$\begingroup\$ Couple golfs: def a(x,y): -> def a(x,y,z=''): and remove next line; similar tricks for other functions, in def o(x,y):, change the x=s(x) to x=s(x);l='';z='', in that for loop, similarly remove newline + paces; instead use ;. Also, I think the if h!='0':h+=s(x)\nelse:h+=i(x) can simply be h+=h!='0'and i(x)or s(x); maybe even h+=(h!='0'and i or s)(x); otherwise, simply change to if'0'!=h. Also things like def r(x):return reversed(x) -> r=reversed \$\endgroup\$
    – Justin
    Oct 24, 2014 at 19:35
  • \$\begingroup\$ Also, I forgot to mention for s, m: s=lambda x:''.join(x), m=lambda x,y:s(r(o(r(x),r(y)))) instead of the entire function declaration. With just the things that I know work, this brings your byte-count down to 521. \$\endgroup\$
    – Justin
    Oct 24, 2014 at 22:26
  • \$\begingroup\$ Oh, and one more: for your for loops: for c in'0'+d:\nif c==y:break\nz=a(iter(z),x) -> for c in'0'+d:\nif c!=y:z=a(iter(z),x), although this could significantly change the speed of your program. \$\endgroup\$
    – Justin
    Oct 24, 2014 at 22:32
  • \$\begingroup\$ @Quincunx thanks! I can see another few improvements as well this morning. (Mostly nesting the loops instead of defining functions.) I'll make these changes if some more competitive answers appear, which seems likely - currently they would put me in the lead, which seems a bit unfair since it was my question and I've had longer to think about it. \$\endgroup\$
    – N. Virgo
    Oct 25, 2014 at 0:22
2
\$\begingroup\$

Scala, 470 characters

(the are standard scala but can equivalently be replaced with => if we're counting bytes)

def p(a: String,b: String)={type D=List[Char]
val d="0123456789".toList
def v(s: String)=s.toList.map{c⇒d.takeWhile(c.!=)}
def u(l:D, a:D):(Char,D)=l match {
case _::_::_::_::_::_::_::_::_::_::m⇒u(m,'a'::a)
case _⇒(('a'::l).zip(d).last._2,a)}
val o=(("", List[Char]())/:v(a).tails.toList.init.map{l⇒(v(b) map {_.flatMap(_⇒l.head)})++l.tail.map(_⇒Nil) reverse}.reduce(_.zipAll(_, Nil, Nil).map{t⇒t._1++t._2}))({(t,e)⇒val s=u(t._2++e,Nil);(s._1+t._1,s._2)})
u(o._2, Nil)._1+o._1}

Here we're emulating digits using the length of lists, being careful not to use any numeric operations - only folds, maps, zips and the like. A number is a list of these digits (order strategically reversed halfway through the computation); we multiply individual digits with flatMap and our rows up with reduce. u handles figuring out the carry (by directly matching against a list of >10 elements, and recursing) and converting digits back to characters, and we use a /: to work our way through the stack with that. The required example completes in less than a second.

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

Haskell 507 496

This works for arbitrarily large integers. I define custom representations for the natural numbers from 0 to 18 (the largest natural number equal to the sum of two digits), and define little-endian multiplication in terms of digit*number multiplication, which I define in terms of number+number addition, which I define in terms of digit+digit addition. I have a reduction function that expands 10--18 values into their digital decomposition. This then just reads and reverses the two strings, translates to the custom bindings, multiplies, and translates back, reversing to get the right result.

Edit 2

I saved a few characters by creating short local aliases for multi-character commands I use more than once, as well as removing spaces and parentheses, and by replacing (-) pairs with $ when possible.

data S=Z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R deriving(Enum, Ord, Eq)
p Z=id
p x=succ.p(pred x)
s Z=id
s x=pred.s(pred x)
z=s J
r[]=[]
r(x:y)|x<J=x:r y
r(x:[])=z x:[A]
r(x:y)=z x:(r$p A a:b)where(a:b)=r y
a x y=r$w(r x)(r y)
m Z _=[]
m _[]=[]
m x y=r$a y(m(pred x)y)
t[]_=[Z]
t _[]=[Z]
t(x:z)y=r$a(m x y)(Z:r(t z y))
i '0'=Z
i x=succ.i.pred$x
b Z='0'
b x=succ.b.pred$x
w[]y=y
w x[]=x
w(x:c)(y:d)=p x y:(w c d)
o=map
v=reverse
f=(o i).v
g=v.o b
main=getLine>>=putStrLn.(\[x,y]->g$t(f x)(f y)).words

For reference, S is the custom integer-like data type, p is 'plus' (digit+digit addition), s is subtract (for reduction), r is reduce (expand into digital decomposition), a is addition (number+number addition), m is multiply (digit*number multiplication), t is times (number*number multiplication), i is 'interpret' (convert string to list of S), b is 'back' (list of S to string), and f and g are just shortenings for golfing purposes. I didn't use numbers, even implicitly; the closest I got was using successors and predecessors, which are much higher level mathematical concepts than addition and multiplication of natural numbers.

Edit

Forgot to include the time profile.

> time echo "9999999999 9999999999" | runhaskell multnonum.hs
99999999980000000001

real    0m0.246s
user    0m0.228s
sys     0m0.012s

Just for good measure:

> time echo "99999999980000000001 99999999980000000001" | runhaskell multnonum.hs
9999999996000000000599999999960000000001

real    0m0.244s
user    0m0.224s
sys     0m0.016s

Let's go insane!

> time echo "9999999996000000000599999999960000000001 9999999996000000000599999999960000000001" | runhaskell multnonum.hs
99999999920000000027999999994400000000699999999944000000002799999999920000000001

real    0m0.433s
user    0m0.424s
sys     0m0.004s

confirmation

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

Python 2 - 1165, 712, 668 664

I,T,V,N,X,J=raw_input,dict,reversed,None,zip,''.join
D='0123456789'
z,o='01'
A,B=I(),I()
r=i=""
K=map(J,X('666622222222911111551111555884444447773333333','678945672389954132987698765898967457989837654'))
P=T(X(K,map(J,X('344501110011800000440000332673322124652202211','628480244668154132507698505422648609367491852'))))
S=T(X(K,'cdef678945abi65243ed87a9cbaghcdab89egfcb6a987'))
for d in D:P[z+d]=z;S[z+d]=d
def Z(A,B,R=r):
 for a,b in V(map(N,V(z+A),V(z+B))):c=(a or z)+(b or z);s=S[min(c)+max(c)];R=Z(R,o)+T(X('abcdefghi',D))[s]if s>"?"else R+s
 return R
for a in V(A):
 j=""
 for b in V(B):r=Z(r,P[min(a+b)+max(a+b)]+i+j).lstrip(z);j+=z
 i+=z
print r if r else z

Note that I'm not using logical indexing like Z = [X, Y][N == "0"], because this could be interpreted as a boolean casted to a numeric index.

Ungolfed:

A = raw_input()
B = raw_input()

P = {'00':'00','01':'00','02':'00','03':'00','04':'00','05':'00','06':'00','07':'00','08':'00','09':'00',
     '10':'00','11':'01','12':'02','13':'03','14':'04','15':'05','16':'06','17':'07','18':'08','19':'09',
     '20':'00','21':'02','22':'04','23':'06','24':'08','25':'10','26':'12','27':'14','28':'16','29':'18',
     '30':'00','31':'03','32':'06','33':'09','34':'12','35':'15','36':'28','37':'21','38':'24','39':'27',
     '40':'00','41':'04','42':'08','43':'12','44':'16','45':'20','46':'24','47':'28','48':'32','49':'36',
     '50':'00','51':'05','52':'10','53':'15','54':'20','55':'25','56':'30','57':'35','58':'40','59':'45',
     '60':'00','61':'06','62':'12','63':'18','64':'24','65':'30','66':'36','67':'42','68':'48','69':'54',
     '70':'00','71':'07','72':'14','73':'21','74':'28','75':'35','76':'42','77':'49','78':'56','79':'63',
     '80':'00','81':'08','82':'16','83':'24','84':'32','85':'40','86':'48','87':'56','88':'64','89':'72',
     '90':'00','91':'09','92':'18','93':'27','94':'36','95':'45','96':'54','97':'63','98':'72','99':'81',
     }
S = {'00':'0','01':'1','02':'2','03':'3','04':'4','05':'5','06':'6','07':'7','08':'8','09':'9',
     '10':'1','11':'2','12':'3','13':'4','14':'5','15':'6','16':'7','17':'8','18':'9','19':'a',
     '20':'2','21':'3','22':'4','23':'5','24':'6','25':'7','26':'8','27':'9','28':'a','29':'b',
     '30':'3','31':'4','32':'5','33':'6','34':'7','35':'8','36':'9','37':'a','38':'b','39':'c',
     '40':'4','41':'5','42':'6','43':'7','44':'8','45':'9','46':'a','47':'b','48':'c','49':'d',
     '50':'5','51':'6','52':'7','53':'8','54':'9','55':'a','56':'b','57':'c','58':'d','59':'e',
     '60':'6','61':'7','62':'8','63':'9','64':'a','65':'b','66':'c','67':'d','68':'e','69':'f',
     '70':'7','71':'8','72':'9','73':'a','74':'b','75':'c','76':'d','77':'e','78':'f','79':'g',
     '80':'8','81':'9','82':'a','83':'b','84':'c','85':'d','86':'e','87':'f','88':'g','89':'h',
     '90':'9','91':'a','92':'b','93':'c','94':'d','95':'e','96':'f','97':'g','98':'h','99':'i',
     }
L = {'a':'0','b':'1','c':'2','d':'3','e':'4','f':'5','g':'6','h':'7','i':'8'}

def strSum(A, B):
    R = ""
    for a, b in reversed(map(None, reversed("0" + A), reversed("0" + B))):
        if a == None: a = '0'
        if b == None: b = '0'
        s = S[a + b]
        if s.isdigit():
            R += s
        else:
            R = strSum(R, "1") + L[s]
    return R

i = ""
r = "0"
for a in reversed(A):
    j = ""
    for b in reversed(B):
        p = P[a + b] + i + j
        r = strSum(r, p)
        j += "0"
    i += "0"

r = r.lstrip("0")
if r == "":
    r = "0"

print r
\$\endgroup\$
2
  • \$\begingroup\$ I would say that using min() and max() functions shouldn't be allowed because those are comparing actual integer values, aren't they? \$\endgroup\$ Oct 29, 2014 at 20:23
  • \$\begingroup\$ @WorldSEnder: I'd say they compare characters, which is allowed in this challenge. ("Lexicographical comparison of chars is allowed.") \$\endgroup\$
    – Falko
    Oct 29, 2014 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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