wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> CS: multiply without multiplying
        
(Message started by: Oliver Otte on Jul 24^th, 2002, 12:37am)

Title: CS: multiply without multiplying
Post by Oliver Otte on Jul 24^th, 2002, 12:37am

The task was to "Multiply by 8 without using multiplication or addition. Now do the same with 7."

multiply by 8:
1. convert the given number to a bitstring
2. since 8 is 2**3 do a left shift three times

multiply by 7:
1. take the octal value of the given number
2. do a left shift (equals multiply by 8)
3. take the decimal value of the result
4. subtract the given number

Since the task is about not using multiply and add, subtracting may be allowed ;)

Comments are appreciated.

--
Oliver

Title: Re: CS: multiply without multiplying
Post by Xactoguy on Jul 24^th, 2002, 12:44am

Well... I think that I'm missing something here, but doesn't it seem obvious that for multiplaying by 8 you just divide by 8 over 1, and do likewise for multiplying by 7? I hope that the riddle means no dividing either, because otherwise it is stupidly obvious. ( I think that you have gotten the correct answer using CS, btw :) )

Title: Re: CS: multiply without multiplying
Post by Rajiv Eranki on Jul 24^th, 2002, 1:58am

Hmm, Olive, I don't think you're allowed to subtract. Think about it... You could simply subtract x from 0 7 times and take the additive inverse.

Title: Where have your axioms gone to?
Post by cmdrdran on Jul 24^th, 2002, 2:11am

Well, you can not divide or subtract at all because of these two little things I can remember from Algebra 1 a few years ago.

Here's the definition of subtraction:
a - b = a + (-b)

and the definition of division:
a / b = a * (1 / b)

Therefore you can not divide or subtract, based on our favorite axioms. ;)

Unless you consider appending to a string adding (which it is, but it's not integer...), you can use this little perl script.
#####################################
my $number = 5; # or insert your favorite number
my $tally = "";

for (1..$number) {
for (1..8) {
$tally .= "I";
}
}

print length($tally), "\n";
#####################################
And it does output 40 (you know, 8 * 5).

Title: Re: Where have your axioms gone to?
Post by ootte on Jul 24^th, 2002, 2:33am

on 07/24/02 at 02:11:24, cmdrdran wrote:

Well, you can not divide or subtract at all because of these two little things I can remember from Algebra 1 a few years ago.
[...]
Unless you consider appending to a string adding (which it is, but it's not integer...), you can use this little perl script.

Appending to the string is pretty much the same like adding one. I don't want your neat perl script see multiplying 7 by 13113123 ;)

But I will add your answer to my solutions.

--
Oliver

Title: Re: CS: multiply without multiplying
Post by suid on Jul 25^th, 2002, 3:52am

Below is a longwinded solution (this version only works for
numbers below 256, even though that can easily be modified
by changing two if-statements). What it does is a binary
addition by hand (using AND, OR and XOR) on the
values X, X<<1 and X<<2 (X + X*2 + X*4 = X*7).

Even though Oliver's solution seems better, implementing it
might be a hassel. (Or whatever).

-------------
#include <stdio.h>

int main(int argc, char *argv[]){
unsigned char i;
unsigned char j;
unsigned char foo;
unsigned char count;
char rem;

i = atoi(argv[1]);
rem = j = 0;
for(count=1;;count<<=1){
j |= (i<<1 & count) ^ (i<<2 & count) ^ (rem ? count:0);
if( ((i<<1 & count) && (i<<2 & count)) || ((i<<1&count || i<<2&count) && rem))
rem = 1;
else
rem = 0;
if( count == 128 )
break;
}

rem = 0; foo = 0;
for(count=1;;count<<=1){
foo |= (i&count) ^ (j&count) ^ (rem ? count:0);
if( (j&count && i&count) || ((i&count || j&count) && rem))
rem = 1;
else
rem = 0;
if( count == 128 )
break;
}
printf("foo = %d\n",foo);
return 0;
}

Title: Re: CS: multiply without multiplying
Post by cnmne on Jul 28^th, 2002, 6:17pm

is this the best way to add two numbers? I just made this up, but it seems pretty optimal. the worst case is equal to checking every bit.

int add( int x , int y ) {
int a , b;

do {
a = x & y;
b = x ^ y;

x = a << 1;
y = b;
} while ( a );

return b;
}

int multiply( int x , int y ) {
int m = 1 , z = 0;

while ( x >= m && y ) {
if ( x & m ) z = add( y , z );

y <<= 1;
m <<= 1;
}

return z;
}

so to multiply a number, x, by 7 use either:

multiply( 7 , x );

or the optimized

add( x << 3 , -x );

multiply can be optimized more, if you actually need something like that.

Title: Re: CS: multiply without multiplying
Post by george campbell on Jul 29^th, 2002, 7:32pm

my smart ass answer to this question would be to use logs.

f(x) = e^(log(x)+log(8))

Title: Re: CS: multiply without multiplying
Post by AlexH on Jul 29^th, 2002, 10:49pm

You used an addition George :P

You could do ln((e^8)^x)) though I don't think this was really the intent of the question =)

Title: Re: CS: multiply without multiplying
Post by MattyDK23 on Aug 25^th, 2002, 11:42am

Guys...I don't think you're allowed to shift bits. Shifting right is really adding a bit, and there's no addition allowed ::) And since shifting left is subtracting a bit, by cmdrdran's argument, there's no left shifting either.

Therefore, I like AlexH's answer best: to multiply X by a factor of Y, use ln((e^Y)^X)

Title: Re: CS: multiply without multiplying
Post by Jimmy Hansen on Sep 11^th, 2002, 7:39pm

Is this the easiest solution so far?

Let's say 5 is my number that I want to multiply times 8. My answer is basically gonna be the absolute value of -5 -5 -5 -5 -5 -5 -5 -5 = abs(-40)

Multiply(5, 8)

Public int Multiply(int number, int times) {
int answer = 0;
for (int i = 0; i < times; )
answer = answer - number;
return answer;
}

So this would work with 7 by calling Multiply(5, 7)

Title: Re: CS: multiply without multiplying
Post by Jimmy Hansen on Sep 11^th, 2002, 7:42pm

oops, forgot absolute value, so this

return answer;

this be this:

return abs(answer);

Title: Re: CS: multiply without multiplying
Post by Jimmy Hansen on Sep 11^th, 2002, 7:44pm

Sorry, it's been a while since I've done C/Java. Here's the proper syntax

Public int Multiply(int number, int times) {
int answer = 0;
for (int i = 0; i < times; i++)
answer = answer - number;
return abs(answer);
}

Title: Re: CS: multiply without multiplying
Post by S. Owen on Sep 12^th, 2002, 7:40am

To be picky...
Public -> public
abs -> Math.abs

Title: Re: CS: multiply without multiplying
Post by Jonathan_the_Red on Sep 12^th, 2002, 2:21pm

To be pickier:

One doesn't have to be much of a purist to call your solution unacceptable. Subtraction and addition aren't really different, especially from the processor's point of view.

On the other hand, addition and bit shifting are very different from the processor's point of view.

More seriously, your solution fails for nonpositive integers. Replace abs(answer) with -answer to fix.