Multiply two numbers without using any numbers 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 code-golf, so the shortest valid solution (in bytes) wins.
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&amp;/g
s/[5-9]/4&amp;/g
y/8/4/
s/9/4&amp;/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 &lt;&lt;&lt;)"12345 42" || echo fail
time test 99999999980000000001 = $(./40297.sed &lt;&lt;&lt;"9999999999 9999999999") || echo fail
time test 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 = $(./40297.sed &lt;&lt;&lt;"37975227936943673922808872755445627854565536638199 40094690950920881030683735292761468389214899724061") || echo fail
time test 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413 = $(./40297.sed &lt;&lt;&lt;"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 =&gt; _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&amp;/g
s/[5-9]/4&amp;/g
y/8/4/
s/9/4&amp;/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 =&gt; 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