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)
Can we accept
"12345"
from STDIN rather than12345
? Or can we accept both numbers as"12345", "42"
? – Justin – 2014-10-24T05:35:05.397My first thought was to write a function taking string arguments of length
m
andn
and returning an argument of lengthm*n
. But as the strings have to literally contain the ASCII representation of the numbers, I guess that's against the rules. – Level River St – 2014-10-24T05:41:42.367@Quincunx yes, that sort of thing is fine. – Nathaniel – 2014-10-24T05:42:57.183
@steveverrill sorry, yes, it really does have to be the base-10 representation in ASCII format. – Nathaniel – 2014-10-24T05:43:22.223
Say I simply want to increment a char in
0123456789
to the next one. I presume I can't just increase the char code by one because that's a number? Or search for the char in string"0123456789"
and take the next one because the index is a number? So far, I'm not seeing a way to do this without writing out nine cases. – xnor – 2014-10-24T06:05:05.973@Quincunx yeah, I really wanted to post this with addition instead of multiplication (at least at first), but I thought it might get closed as a duplicate of http://codegolf.stackexchange.com/questions/20996/add-without-addition-or-any-of-the-4-basic-arithmetic-operators (although it would actually be quite a bit harder). Maybe I'll post the addition version later, depending on how this one goes.
– Nathaniel – 2014-10-24T06:41:55.7931@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'
– Nathaniel – 2014-10-24T06:47:19.0671or in Python 3,
a,b="0123456789x".split(x);c,*d=b
if c=='x':
c='0'
– Nathaniel – 2014-10-24T06:53:10.2302@Nathaniel
d='123456789';I=dict(zip('0'+d,d+'0'))
– Justin – 2014-10-24T07:03:21.010OP is adding rules to invalidate existing answers. On top of that, if we are not allowed to interpret the string input as integer in any way, then there is no difference in multiplying two string integers vs two strings of non integers. Thus, I am voting to close this question as unclear. – Optimizer – 2014-10-24T09:43:58.137
@Optimizer I'm not adding rules, I'm clarifying them. The rule is "you may not work around the restriction ... you must implement the multiplication yourself using only non-numeric types." The list in that paragraph is just a list of examples of workarounds. The point of the challenge is that you have to implement a multiplication algorithm, e.g. the long multiplication that you used in school, using string manipulations or other data structures. – Nathaniel – 2014-10-24T09:55:06.797
@Optimizer also note that even if you interpret adding to the list as changing the rules, no answer has been invalidated by it. millinon's answer and your Javascript answer were both invalid because they don't run in under a minute in the worst case, independently of the rules about workarounds, and that rule has not changed. – Nathaniel – 2014-10-24T09:58:01.897
The example "long multiplication that you used in school" is also invalid as we are not supposed to used int types in order to add the first argument second number of times. Also, "you may not work around the restrictions" is a very vague rule and that is why I voted to close as unclear what you are asking. – Optimizer – 2014-10-24T10:01:33.323
@Optimizer yes, you have to implement addition as well, e.g. also using the algorithm you used in school, and then you have to use that to implement long multiplication. It is a hard challenge. I want answers that actually take up the challenge to be able to compete on a fair playing field, and that is why all workarounds are banned. I do not think this is unreasonable. – Nathaniel – 2014-10-24T10:02:45.493
Can we lexicographically compare
char
s? Because that's basically comparing numbers, but might be necessary. – Martin Ender – 2014-10-24T10:40:57.797@MartinBüttner hmm, I think I'll somewhat arbitrarily say yes, that's allowed, on the basis that it's a lexicographical operation rather than an arithmetic one. It definitely isn't necessary, because you could always chain up a load of
if
s, but I can certainly see it helping. – Nathaniel – 2014-10-24T10:44:01.99312345
times42
=518490
, not51890
;) – COTO – 2014-10-24T14:38:25.397@COTO d'oh - that was left over from when I was deciding whether to make this challenge addition or multiplication. (Fixed.) – Nathaniel – 2014-10-24T14:40:26.113
@Nathaniel: Are
bool
s ok? I'd like to use them for indexing in Python, likeresult=(x,y)[a>b]
... – Falko – 2014-10-24T18:26:16.853Are languages with implicit type conversion allowed? in Lua you can multiply two strings and the interpreter will take care of interpreting them as number if possible – None – 2014-10-24T19:06:06.263
@Alessandro using such a feature would definitely be a workaround, I'm afraid. – Nathaniel – 2014-10-25T00:24:58.990
@Falko that's a tricky one, but I think I have to say no, because I think the
bool
is being implicitly converted to a numerical type in this case. (Usingbool
s in other contexts is fine though.) – Nathaniel – 2014-10-25T00:27:54.120is pointer arithmetics allowed? – phuclv – 2014-10-25T11:41:51.597
@LưuVĩnhPhúc no, that comes under "using numeric or bitwise operators on non-numeric types that support them". – Nathaniel – 2014-10-25T12:48:19.530
Unlambda seems like a great language for this challenge. – Aearnus – 2014-10-30T04:39:05.290