Author |
Topic: CS: multiply without multiplying (Read 10551 times) |
|
Oliver Otte
Guest
|
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
|
|
 IP Logged |
|
|
|
Xactoguy
Guest
|
 |
Re: CS: multiply without multiplying
« Reply #1 on: Jul 24th, 2002, 12:44am » |
 Quote  Modify
 Remove
|
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  )
|
|
IP Logged |
|
|
|
Rajiv Eranki
Guest
|
|
Re: CS: multiply without multiplying
« Reply #2 on: Jul 24th, 2002, 1:58am » |
Quote Modify
Remove
|
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.
|
|
IP Logged |
|
|
|
cmdrdran
Newbie
Posts: 3
|
|
Where have your axioms gone to?
« Reply #3 on: Jul 24th, 2002, 2:11am » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
ootte
Newbie
Posts: 19
|
|
Re: Where have your axioms gone to?
« Reply #4 on: Jul 24th, 2002, 2:33am » |
Quote Modify
|
on Jul 24th, 2002, 2:11am, 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
|
|
IP Logged |
|
|
|
suid
Guest
|
|
Re: CS: multiply without multiplying
« Reply #5 on: Jul 25th, 2002, 3:52am » |
Quote Modify
Remove
|
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;
}
|
|
IP Logged |
|
|
|
cnmne
Guest
|
|
Re: CS: multiply without multiplying
« Reply #6 on: Jul 28th, 2002, 6:17pm » |
Quote Modify
Remove
|
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.
|
|
IP Logged |
|
|
|
george campbell
Guest
|
|
Re: CS: multiply without multiplying
« Reply #7 on: Jul 29th, 2002, 7:32pm » |
Quote Modify
Remove
|
my smart ass answer to this question would be to use logs.
f(x) = e^(log(x)+log(8))
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: CS: multiply without multiplying
« Reply #8 on: Jul 29th, 2002, 10:49pm » |
Quote Modify
|
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 =)
|
| « Last Edit: Jul 29th, 2002, 10:50pm by AlexH » |
IP Logged |
|
|
|
MattyDK23
Newbie
Gender: 
Posts: 46
|
|
Re: CS: multiply without multiplying
« Reply #9 on: Aug 25th, 2002, 11:42am » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
Jimmy Hansen
Guest
|
|
Re: CS: multiply without multiplying
« Reply #10 on: Sep 11th, 2002, 7:39pm » |
Quote Modify
Remove
|
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)
|
|
IP Logged |
|
|
|
Jimmy Hansen
Guest
|
|
Re: CS: multiply without multiplying
« Reply #11 on: Sep 11th, 2002, 7:42pm » |
Quote Modify
Remove
|
oops, forgot absolute value, so this
return answer;
this be this:
return abs(answer);
|
|
IP Logged |
|
|
|
Jimmy Hansen
Guest
|
|
Re: CS: multiply without multiplying
« Reply #12 on: Sep 11th, 2002, 7:44pm » |
Quote Modify
Remove
|
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);
}
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: CS: multiply without multiplying
« Reply #13 on: Sep 12th, 2002, 7:40am » |
Quote Modify
|
To be picky...
Public -> public
abs -> Math.abs
|
|
IP Logged |
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
|
Re: CS: multiply without multiplying
« Reply #14 on: Sep 12th, 2002, 2:21pm » |
Quote Modify
|
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.
|
|
IP Logged |
My arcade cabinet
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print