Multiply two numbers without using any numbers

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

sed, 379 bytes

Credit for this brilliant answer goes to @LuigiTiburzi over on Unix&Linux.SE: https://unix.stackexchange.com/a/37213/34061. I just happened to stumble upon this a few days ago:

s/[0-9]/<&/g
s/0//g
s/1/|/g
s/2/||/g
s/3/|||/g
s/4/||||/g
s/5/|||||/g
s/6/||||||/g
s/7/|||||||/g
s/8/||||||||/g
s/9/|||||||||/g
:t
s/|</<||||||||||/g
tt
s/<//g
s/.*\*$/0/
s/^\*.*/0/
s/*|/*/
:m
s/\(|*\)\*|/\1<\1*/
tm
s/*//g
s/<//g
:b
s/||||||||||/</g
s/<\([0-9]*\)$/<0\1/
s/|||||||||/9/
s/||||||||/8/
s/|||||||/7/
s/||||||/6/
s/|||||/5/
s/||||/4/
s/|||/3/
s/||/2/
s/|/1/
s/</|/g
tb

Broad Explanation

  • Separate each digit. Thus 12*3 becomes <1<2*<3
  • Convert each digit to that number of | characters. Thus <1<2*<3 becomes <|<||*<|||
  • Repeatedly substitute |< with <|||||||||| in order to shift higher decimal places all down to the units position. Thus <|<||*<||| becomes <||||||||||||*<|||
  • Remove <. Thus <||||||||||||*<||| becomes ||||||||||||*|||
  • Remove 1 | from the RHS of the *. Thus ||||||||||||*||| becomes ||||||||||||*||
  • Repeatedly replace each | on the RHS with all the | on the LHS. This has the effect of multiplying the LHS and RHS number of | to give the product number of | Thus ||||||||||||*|| becomes ||||||||||||||||||||||||||||||||||||*
  • Remove *. Thus ||||||||||||||||||||||||||||||||||||* becomes ||||||||||||||||||||||||||||||||||||
  • convert number of | back to decimal by the reverse of the first few steps. Thus |||||||||||||||||||||||||||||||||||| becomes 36.

Output:

$ echo "04*3
4*3
40*3
42*32
150*20
1*3
3*1
0*3
3*0" | sed -f mult.sed
12
12
120
1344
3000
3
3
0
0
$

Unfortunately it fails miserably on the time requirement - 200*1000 takes 41 seconds on my Ubuntu VM, and runtime empirically seems to go up with the square of the final product.


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())

Tags:

Code Golf

Arithmetic

Restricted Source

Recent Posts