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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@Saurabh: According to the statement of the problem using
multiplication is not allowed, but you can replace (1k)*b by bk to
eliminate your multiplications.
Dave
On Aug 27, 2:49 am, saurabh modi saurabhmodi102...@gmail.com wrote:
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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@Dave Yup, but Overall Complexity Will remain O(log(Quotient)) as y=logn^k=klogn=O(logn) where k is constant isn't it ? Also case of -Ive Numbers Can be handled easily :) *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/-/MyURO-b4rEMJ. 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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@Shashank: Regarding the complexity, let's say that you are dividing 15 by 1. The on the original call, you will shift 4 times, on the first recursive call, 3 times, then 2 times, then 1 time. This is a total of ten shifts. This is log(quotient) * (log(quotient) - 1) / 2, which is O(log(quotient)^2). Dave On Aug 25, 7:23 am, WgpShashank shashank7andr...@gmail.com wrote: @Dave Yup, but Overall Complexity Will remain O(log(Quotient)) as y=logn^k=klogn=O(logn) where k is constant isn't it ? Also case of -Ive Numbers Can be handled easily :) *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 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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@Dave True :) *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/-/mSeEd-_wRcMJ. 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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@Dave , You are right , i mean to say we reduce the number of instruction or
comparisons executed by the program. ,Never Mind here is recursive code for
doing the same , Algorithm is already explained
#includeiostream
using namespace std;
int dividend,divisor,remainder;
int division(int p,int q)
{
int quotient=1;
/*if divisor and dividend are equal then quotient=1*/
if(p==q)
{
remainder=0;
return 1;
}
else if (pq) /*if dividend is smaller than divisor then remainder=dividend*/
{
remainder = p;
return 0;
}
while(p=q)
{
q=1;
quotient=1;
}
/*We have reached the point where divisor dividend so shift right for one
time so that divisor become smaller than dividend*/
q=1;
quotient=1;
/*again call division recursively*/
quotient+=division(p-q,divisor);
return quotient;
}
int main()
{
cout\nEnter dividend:; cindividend;
cout\nEnter divisor:; cindivisor;
cout\nQuotient: division(dividend,divisor);
return 0;
}
Time Complexity O(log Quotient)
*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/-/sm5aufNAdIQJ.
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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@Teja: The complexity of your code is O(quotient). Code has been
presented that is O(log(quotient)).
Dave
On Aug 23, 8:47 am, teja bala pawanjalsa.t...@gmail.com wrote:
//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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@Shashank: Hmmm. In the recursive call, you use the variable divisor,
but I don't see anything assigned to it.
Furthermore, you don't handle negatives, which accounted for almost
half of my code.
In addition, you have to shift the divisor left multiple times in each
recursive call to align it with the dividend. You have
O(log(quotient)) recursive calls, and within each one, you have
O(log(quotient)) shifts. Doesn't that make your code
O((log(quotient))^2)?
Dave
On Aug 23, 5:01 am, WgpShashank shashank7andr...@gmail.com wrote:
@Dave , You are right , i mean to say we reduce the number of instruction or
comparisons executed by the program. ,Never Mind here is recursive code for
doing the same , Algorithm is already explained
#includeiostream
using namespace std;
int dividend,divisor,remainder;
int division(int p,int q)
{
int quotient=1;
/*if divisor and dividend are equal then quotient=1*/
if(p==q)
{
remainder=0;
return 1;}
else if (pq) /*if dividend is smaller than divisor then remainder=dividend*/
{
remainder = p;
return 0;
}
while(p=q)
{
q=1;
quotient=1;
}
/*We have reached the point where divisor dividend so shift right for one
time so that divisor become smaller than dividend*/
q=1;
quotient=1;
/*again call division recursively*/
quotient+=division(p-q,divisor);
return quotient;
}
int main()
{
cout\nEnter dividend:; cindividend;
cout\nEnter divisor:; cindivisor;
cout\nQuotient: division(dividend,divisor);
return 0;
}
Time Complexity O(log Quotient)
*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 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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@Shashank: I didn't know that reducing the number of lines of source code was the goal. Often-times, efficiency demands more code rather than less. For example, back in the days of the Cray-1 supercomputer, which had vector registers and could do an operation on up to 64 operand pairs in one instruction, I wrote a vectorized routine in Cray assembly language to find the index of the element of a one- dimensional array that had the largest absolute value. A scalar version of the routine could be written in half-a-dozen lines of C or perhaps 25 lines of Cray assembly language, but the vectorized version was over 1000 lines long. The result as a routine that was about 100 times faster, though, so it was worth it. As an example that reducing the number of lines is not necessarily a universally-appreciated goal, I submitted a one-line-of-C routine that, given an unsigned integer, returns the next larger integer with the same number of one bits. The code is at http://groups.google.com/group/algogeeks/msg/2b64c4f96fa3598e. I received a comment stating @Dave: Thanks for the link. Just a point of discussion - this kind of code would probably never pass code-review (or would be heavily documented with references and warnings that say HANDS OFF ;) ) Dave On Aug 20, 9:31 am, WgpShashank shashank7andr...@gmail.com wrote: @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 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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
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.
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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@Arun: Just think about doing long division with paper and pencil. The q=1 statement is the same as bringing down a new digit. Doing so also expands the quotient by one digit. The q|=1 statement is the same as writing down a nonzero digit in the quotient. Dave On Aug 19, 10:31 am, Arun Vishwanathan aaron.nar...@gmail.com wrote: @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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@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.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 : 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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
exp(ln(a)-ln(b)) 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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@Don: Try it with a = b = -1. Dave On Aug 18, 9:45 am, Don dondod...@gmail.com wrote: exp(ln(a)-ln(b)) 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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@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.
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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@Aditya: Not wrong, but inefficient and inelegant. Repeated
subtraction has complexity O(quotient), while long division has
complexity O(log quotient).
Dave
On Aug 18, 10:48 am, 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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@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.
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.
[algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
@Arun: Oops. It looks like the while loop condition should be b = a
instead of b a, and the if condition within the for loop should be
a = b instead of a b. I'm glad I equivocated with the phrase
would look something like.
With a = 24 and b = 3, the while loop shifts b left and increments k
until b 24. In particular, the while loop exits with b = 48 and k =
4. Thus, the for loop is executed 4 times. The first time, q is
doubled to 0, b is right shifted 1 to 24. Since 24 = 24, a is reduced
to 0 and q is set to 0 | 1 = 1. In the next three loop iterations, q
is doubled each time, yielding q = 8. This eventually is the return
value.
Let me know if you find other problems.
Dave
On Aug 18, 1:09 pm, Arun Vishwanathan aaron.nar...@gmail.com wrote:
@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.
