unsigned add( unsigned a, unsigned b )
{
return (unsigned)&((char*)a)[b]; // ignore compiler warnings
// (if pointers are bigger than unsigned). it still works.
}
unsigned umul( unsigned a, unsigned b )
{
unsigned res = 0;
while( a != 0 ){
if( a & 1) res = add( res, b );
b <<= 1;
a >>= 1;
}
return res;
}
int mul( int a, int b ){
return (int)umul( (unsigned)a, (unsigned)b );
}
If you consider the a[b] hack to be cheating (since it's really an add) then this works instead. But table lookups involve pointer adds too.
See http://en.wikipedia.org/wiki/IBM_1620 - a conputer that actually did addition using lookup tables...
Something satisfying about using a table mechanism to 'speed up' an operation that could actually be done in one instruction.
static unsigned sumtab[17][16]= {
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15},
{ 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16},
{ 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17},
{ 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18},
{ 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19},
{ 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20},
{ 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21},
{ 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22},
{ 8, 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23},
{ 9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24},
{10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25},
{11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26},
{12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27},
{13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28},
{14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29},
{15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30},
{16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31}
};
unsigned add( unsigned a, unsigned b )
{
static const int add4hack[8] = {4,8,12,16,20,24,28,32};
unsigned carry = 0;
unsigned (*sumtab0)[16] = &sumtab[0];
unsigned (*sumtab1)[16] = &sumtab[1];
unsigned result = 0;
int nshift = 0;
while( (a|b) != 0 ){
unsigned psum = (carry?sumtab1:sumtab0)[ a & 0xF ][ b & 0xF ];
result = result | ((psum & 0xF)<<nshift);
carry = psum >> 4;
a = a >> 4
b = b >> 4;
nshift= add4hack[nshift>>2]; // add 4 to nshift.
}
return result;
}
1Please be more specific about "numbers". – Paul R – 2014-01-11T17:03:15.303
2@PaulR use your fantasy – John Dvorak – 2014-01-11T17:03:42.697
I guess the original Q meant any numbers... – s3lph – 2014-01-11T17:04:51.520
The given example doesn't work with integers so I'm guessing it may be a floating point task? – Paul R – 2014-01-11T17:05:18.637
Why doesn't it work with ints? (except 0) – s3lph – 2014-01-11T17:10:33.420
1/n is 0 for n > 1 when n is an int. – Paul R – 2014-01-11T17:19:21.093
oh.. yes, you're right... doesn't matter for the question – s3lph – 2014-01-11T17:22:24.220
26Code-golf.SE should not be a place for you to mock questions you've seen on StackOverflow. – Gareth – 2014-01-11T19:40:05.483
17
@Gareth, are you sure? The first line of this suggests this may be quite appropriate.
– Darren Stone – 2014-01-11T20:27:17.590@DarrenStone I've enjoyed being a member of this site for a couple of years now and I'm seriously concerned that questions like this are mean and unpleasant. I don't want to see this site become reddit-like. – Gareth – 2014-01-11T22:42:55.727
1@Gareth, I certainly didn't intend to be mean with my comment. I wrestle with the spirit and noise that [tag:code-trolling] questions bring, but OP has tagged the question correctly and code-trolling is based on jest and mockery of real questions. – Darren Stone – 2014-01-11T22:50:37.057
1@DarrenStone I think you misunderstood me, I think this type of question which mocks an SO user is a bit mean. Your comment was a reasonable one (as they usually are). – Gareth – 2014-01-12T01:15:21.473
5I´m waiting for someone write an algorithm based on sleep – kb_sou – 2014-01-12T02:11:21.180
21This question isn't as ridiculous as it sounds. Actual computer hardware (transistors) don't have multiply and add operations -- they have basic logic operations like NOT, AND, OR, XOR. Figuring out how to answer this question can give you excellent insight into how a computer really works at the level of logic gates. – Gabe – 2014-01-12T06:12:24.757
1@Gabe yeah, but the O(bits^2) solution is inappropriate for a code-trolling challenge :-) – John Dvorak – 2014-01-12T07:47:36.880
@Gareth - I don't see that the OP is in any way being mean or "mocking" the SO user. – Kevin Fegan – 2014-01-13T03:02:02.097
@JanDvorak: Multiplying is O(digits^2). If your computer can do it faster than that, it's because it has O(digits^2) transistors that all operate simultaneously. – Gabe – 2014-01-13T06:43:03.070
last week I had an interview I was asked to multiply a number with
7
without using+
and*
I answeredresult = (number << 3) - number
. – Grijesh Chauhan – 2014-01-13T06:54:35.290@GrijeshChauhan: your solution does not work for the full valid range of possible input values (it overflows for part of the range). – Paul R – 2014-01-13T07:56:45.257
@PaulR Yes. You are correct, in-fact it can cause undefined behavior if left-shit sets sign-bit(msb). But fortunately interviewer was happy :) I guess because he asked question in Puzzle section(not in programming). Btw I now like @ MarkLakata trick. – Grijesh Chauhan – 2014-01-13T08:09:37.453
@GrijeshChauhan: I think you're confused between left shift and right shift of signed values - the only problem with the left shift in your solution is the potential for overflow in the intermediate result - otherwise it's fine. – Paul R – 2014-01-13T08:11:46.197
Since all computers are essentially adding machines, with flow control, comparators, and about every other operation including incrementing the program counter dependent on addition then no, in the strictest sense this program can't be written, at least not for any non-analogue computer. – user289251 – 2014-01-12T03:35:20.040
@GrijeshChauhan: To avoid overflow of the intermediate result, set
result = (number<<2) + (number <<1) + number
– Pieter Geerkens – 2014-01-13T11:57:29.233@PieterGeerkens yup, this kind of technique can be helpful, but you are using
+
!! – Grijesh Chauhan – 2014-01-13T12:19:46.2672@GrijeshChauhan: Oops! Time for a coffee I think. – Pieter Geerkens – 2014-01-13T12:21:53.123
1Unless you are compiling with
-Ofast
(which is gcc mode that doesn't calculate accurately, like C standard says),a/(1/((float)b))
is not identical toa*b
. This is because floating point math is special, and most optimizations cannot be done. – Konrad Borowski – 2014-01-13T19:37:06.6431What about solutions that use
a - -b
to substitute fora + b
? – Joe Z. – 2014-01-13T20:25:43.9872"c = a * b" doesn't use "the * and + operators", it only uses one of them :p (how do you make 35 cents with two coins, where one of them isn't a quarter?) – neminem – 2014-01-13T21:13:07.343
(oops, it hates left-arrows so I replaced it with {) Note that on some level, logic gates are in fact related to addition, comparison, and tables. You can state (2 inputs) XOR as 0{A+B{2 or that the sum is equal to 1. A 3-input NAND gate can be stated as A+B+C=3 and so on. On some level, a (stateless) logic device is just asking "Does the sum of these inputs equal to some value in the following table?" and combining the answers recursively for many groups of inputs into yet more tables. This is in fact the idea behind Programmable Array Logic devices. This is getting into major number theory t – None – 2014-01-14T09:18:53.757
No one applied the seemingly obvious properties of natural logarithms? For shame? Oh someone did mention exp(x) though. In (roughly) algebraic form: ab=exp(log(a)+log(b)) So what to do since we can't use addition? I'll not cheat and assume "direct addition" is the only kind forbidden. You could use a table or slide rule (which is just an analog computer version of the table). You'd be imitating addition, though. Hmm, thinking of another angle of attack... OK, multiplying complex numbers adds the angles. angleof((1@ angle A)(1@ angle B)) = (A+B) mod 2Pi. LOL, going around in circles unless A= – None – 2014-01-14T09:14:46.367
1@GrijeshChauhan @PieterGeerkens Regarding
result = (number << 3) - number
: it does not have an overflow problem. It does overflow, of course, but the result is correct anyway, because (on all normal C machines) both the << and the '-' overflow as in modular arithmetic. So doesnumber*7
. So you get the proper result, overflow or not. It's common for C compilers to do such transforms when the shift/add is smaller than the multiply-by-constant. – greggo – 2014-01-20T02:52:56.890@greggo so I am pass :) – Grijesh Chauhan – 2014-01-20T04:54:14.950
Code-trolling is in the process of being removed, as per the official stance. This question receieved almost 50% "keep" votes on the poll, and is an outlier in that it has an extreme amount of votes, votes on the answers, and amount of answers, so I am locking it.
– Doorknob – 2014-05-10T16:49:17.210