Re: [algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
I think that this code can suffice.
http://www.ideone.com/ESW8Z
#includestdio.h
int solve(int,int);
int main()
{
printf(%d,solve(100,10));
return 0;
}
int solve(int a,int b)
{
int quotient=0,k=0;
if(ab)
return quotient;
while((1k)*b=a)
{
k++;
}
k--;
quotient=(1k)+solve(a-(1k)*b,b);
return quotient;
}
It also gives correct answer.Plus,its easy to read and concise.it is
O(log(quotient)) solution.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
haha yeah okay..that can be done :-) i had forgotten abt * -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
//works only for ints
#includestdio.h
int div(int a,int b);
main()
{
int q,w,x;
scanf(%d %d,q,w);
x=div(q,w);
printf(%d,x);
}
int div(int x,int y)
{
int z=x,count=0;
while(z=y)
{
z-=y;
count++;
}
return count;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@Lucky sorry for delay, I am saying compelxity will be number if bits required to represent quioutent , i think you just try with exmple i have given @Dave I didn't See The Whole Code but i think Logic Will Remain The Same.i Think You forgot to give algorithm :P also we can reduce the line of source codes, i mean we merge some of the steps , will post later an recursive solution for the same *Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/6-7Rrl-UzdkJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@Shashank : Nice solution :) *Regards Sanju Happy to Help :)* On Fri, Aug 19, 2011 at 2:36 AM, WgpShashank shashank7andr...@gmail.comwrote: We can use bit logic to reduce the time complexity to O(logn) where n is Quotient Algorithm will be as follow as we know 1. Left shifting an unsigned number by 1 multiplies that number by 2. 2. Right shifting an unsigned number by 1 divides that number by 2. Therefore the procedure for the division algorithm, given a dividend and a divisor . core logic will be to left shift (multiply by 2) untill its greater then dividend , then continue this routine with the the difference between the dividend and divisor and divisor till the point where dividend is less than divisor or their difference is zero. Lets see one example: dividend=23 divisor=3 then left shift for 3 i.e 3 will converted to3, 6,12,24,… since 12 23 hence now dividend is 11 and quotient in 4(two time shift operation) now again 3,6,12.. 611 hence dividend is 11-6=5 and quotient =4+2=6 now only 35 hence remainder =2 quotient =6+1=7 so answer. Time Complexity O(logn) Number of bits in Quotient Correct me if anything wrong *Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/VszScC-sOfoJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@dave: actually how did u get the approach to this? I mean why did u have to do the q|=1 in the if(a=b) condition and q=1 always in the loop? On Fri, Aug 19, 2011 at 1:46 PM, Sanjay Rajpal tosanjayraj...@gmail.comwrote: @Shashank : Would you throw some light on how you determined the complexity ? *Regards Sanju Happy to Help :)* On Fri, Aug 19, 2011 at 2:36 AM, WgpShashank shashank7andr...@gmail.comwrote: We can use bit logic to reduce the time complexity to O(logn) where n is Quotient Algorithm will be as follow as we know 1. Left shifting an unsigned number by 1 multiplies that number by 2. 2. Right shifting an unsigned number by 1 divides that number by 2. Therefore the procedure for the division algorithm, given a dividend and a divisor . core logic will be to left shift (multiply by 2) untill its greater then dividend , then continue this routine with the the difference between the dividend and divisor and divisor till the point where dividend is less than divisor or their difference is zero. Lets see one example: dividend=23 divisor=3 then left shift for 3 i.e 3 will converted to3, 6,12,24,… since 12 23 hence now dividend is 11 and quotient in 4(two time shift operation) now again 3,6,12.. 611 hence dividend is 11-6=5 and quotient =4+2=6 now only 35 hence remainder =2 quotient =6+1=7 so answer. Time Complexity O(logn) Number of bits in Quotient Correct me if anything wrong *Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/VszScC-sOfoJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@Dave : How did you approach this solution to this problem ? and how you saw that th complexity is O(log_2(Quotient)) ? *Regards Sanju Happy to Help :)* On Fri, Aug 19, 2011 at 8:44 AM, Dave dave_and_da...@juno.com wrote: @Sanjay: Shashank was just reiterating what I said in http://groups.google.com/group/algogeeks/msg/8590f8a2a8408d93. The algorithm Shashank described is what I had previously provided code for in http://groups.google.com/group/algogeeks/msg/735671f6a1e16eec, with a correction in http://groups.google.com/group/algogeeks/msg/6b064081b7ba86f0. As far as determining the complexity, you can see that both the while loop and the for loop in my code iterate approximately log_2(quotient) times, which is what makes the code O(log(quotient)). Dave On Aug 19, 6:46 am, Sanjay Rajpal tosanjayraj...@gmail.com wrote: @Shashank : Would you throw some light on how you determined the complexity ? *Regards Sanju Happy to Help :)* On Fri, Aug 19, 2011 at 2:36 AM, WgpShashank shashank7andr...@gmail.com wrote: We can use bit logic to reduce the time complexity to O(logn) where n is Quotient Algorithm will be as follow as we know 1. Left shifting an unsigned number by 1 multiplies that number by 2. 2. Right shifting an unsigned number by 1 divides that number by 2. Therefore the procedure for the division algorithm, given a dividend and a divisor . core logic will be to left shift (multiply by 2) untill its greater then dividend , then continue this routine with the the difference between the dividend and divisor and divisor till the point where dividend is less than divisor or their difference is zero. Lets see one example: dividend=23 divisor=3 then left shift for 3 i.e 3 will converted to3, 6,12,24,… since 12 23 hence now dividend is 11 and quotient in 4(two time shift operation) now again 3,6,12.. 611 hence dividend is 11-6=5 and quotient =4+2=6 now only 35 hence remainder =2 quotient =6+1=7 so answer. Time Complexity O(logn) Number of bits in Quotient Correct me if anything wrong *Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/VszScC-sOfoJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
how abt subtracting . like a=a-b till a becomes zero . no of times
subtraction is done is the answer .
correct me if i am wrong !
On Thu, Aug 18, 2011 at 8:59 PM, Dave dave_and_da...@juno.com wrote:
@Radha: You could simulate long division. It would look something like
this:
int divide(int a, int b)
{
int i, k=0, q=0, s=1;
// error checking
if( b == 0 ) return 0 // return 0 for division by zero
// handle signs
if( a 0 )
{
a = -a;
s = -1;
}
if( b 0 )
{
b = -b;
s = -s;
}
// quick cases
if( a b )
return 0;
if( a == b )
return s;
// shift divisor to align with dividend
while( b a )
{
b = 1;
++k;
}
// perform k steps of long division in binary
for( i = 0 ; i k ; ++i )
{
q = 1;
b = 1;
if( a b )
{
a -= b;
q |= 1;
}
}
// apply sign to result
if( s 0 )
q = -q;
return q;
}
Dave
On Aug 18, 8:56 am, radha krishnan radhakrishnance...@gmail.com
wrote:
how to do using BIT manipulation ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@dave: in your algorithm, I have a doubt in the second loop( for loop ).
q=0 initially so the first q1 stays zero and then q|=1 makes q=1 now.
1 then becomes x 2 and then again with the OR 2 becomes 3.
3 becomes 6 and with the OR 6 becomes 7.
for example if i need to do 24/3, according to the code k=3 after while loop
and then the for loop terminates with q as 7 as i mentioned the steps
above.Have i got the understanding of the code wrong?
On Thu, Aug 18, 2011 at 7:18 PM, Dave dave_and_da...@juno.com wrote:
@Dheeraj: What about it? It doesn't give the quotient. What is it
supposed to do?
Dave
On Aug 18, 11:06 am, DheerajSharma dheerajsharma1...@gmail.com
wrote:
wat about shifting 'a' right by floar(log2(b)) and adding 1 to it..
On Aug 18, 8:48 pm, aditya kumar aditya.kumar130...@gmail.com wrote:
how abt subtracting . like a=a-b till a becomes zero . no of times
subtraction is done is the answer .
correct me if i am wrong !
On Thu, Aug 18, 2011 at 8:59 PM, Dave dave_and_da...@juno.com wrote:
@Radha: You could simulate long division. It would look something
like
this:
int divide(int a, int b)
{
int i, k=0, q=0, s=1;
// error checking
if( b == 0 ) return 0 // return 0 for division by zero
// handle signs
if( a 0 )
{
a = -a;
s = -1;
}
if( b 0 )
{
b = -b;
s = -s;
}
// quick cases
if( a b )
return 0;
if( a == b )
return s;
// shift divisor to align with dividend
while( b a )
{
b = 1;
++k;
}
// perform k steps of long division in binary
for( i = 0 ; i k ; ++i )
{
q = 1;
b = 1;
if( a b )
{
a -= b;
q |= 1;
}
}
// apply sign to result
if( s 0 )
q = -q;
return q;
}
Dave
On Aug 18, 8:56 am, radha krishnan radhakrishnance...@gmail.com
wrote:
how to do using BIT manipulation ?
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
People often say that motivation doesn't last. Well, neither does bathing
- that's why we recommend it daily.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
