Re: [algogeeks] Re: calculate a/b without using ‘*’, ‘/’’ and ‘%’
yeah...right,...i understand nowthanks anyway. -- 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: Again, this solution is not O(log(quotient)), but
O(log(quotient)^2). Consider a = 15, b = 1. On the first call, the
while loop increments k 4 times. On the first recursive call, k is
incremented 3 times, then 2 times, and then 1 time. This is a total of
10 executions of the statement k++. Since loq_2(quotient) ~ 4, this is
log_2(quotient) * (log_2(quotient) + 1) / 2 = O(log(quotient)^2).
Dave
On Aug 27, 2:49 am, saurabh modi wrote:
> I think that this code can suffice.
>
> http://www.ideone.com/ESW8Z
>
> #include
>
> 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(a return quotient;
> while((1< {
> k++;
> }
> k--;
> quotient=(1< 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 ‘%’
@Saurabh: According to the statement of the problem using
multiplication is not allowed, but you can replace (1< wrote:
> I think that this code can suffice.
>
> http://www.ideone.com/ESW8Z
>
> #include
>
> 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(a return quotient;
> while((1< {
> k++;
> }
> k--;
> quotient=(1< 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 ‘%’
I think that this code can suffice.
http://www.ideone.com/ESW8Z
#include
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(ahttp://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 ‘%’
@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 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 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: 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 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
>
> #include
> 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 (p {
> 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:"; cin>>dividend;
> cout<<"\nEnter divisor:"; cin>>divisor;
> 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.
[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 wrote:
> //works only for ints
> #include
> 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 ‘%’
//works only for ints
#include
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 ‘%’
@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
#include
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 (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:"; cin>>dividend;
cout<<"\nEnter divisor:"; cin>>divisor;
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.
[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 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.
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 ‘%’
@Sanjay: Just think about doing long division with paper and pencil. Then implement it in binary. If you look at my code, which was posted and corrected earlier in this thread, you will see that both the while loop and the for loop iterate approximately log_2(quotient) times, log_2(quotient) being approximately the number of bits in the quotient. Dave On Aug 19, 11:10 am, Sanjay Rajpal wrote: > @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 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 inhttp://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 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 > >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.. 6<11 hence dividend is 11-6=5 and quotient =4+2=6 now > > only > > > > 3<5 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 ‘%’
@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 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 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 >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.. 6<11 hence dividend is 11-6=5 and quotient =4+2=6 now > only > > > 3<5 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 ‘%’
@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 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 > 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.. 6<11 hence dividend is 11-6=5 and quotient =4+2=6 now only > > 3<5 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.
[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 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 > 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 > > 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.. 6<11 hence dividend is 11-6=5 and quotient =4+2=6 now only > >> 3<5 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: 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 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 > 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.. 6<11 hence dividend is 11-6=5 and quotient =4+2=6 now only >> 3<5 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 ‘%’
@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 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.. 6<11 hence dividend is 11-6=5 and quotient =4+2=6 now only > 3<5 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 ‘%’
@Shashank : Nice solution :) *Regards Sanju Happy to Help :)* On Fri, Aug 19, 2011 at 2:36 AM, WgpShashank 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.. 6<11 hence dividend is 11-6=5 and quotient =4+2=6 now only > 3<5 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.
[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.. 6<11 hence dividend is 11-6=5 and quotient =4+2=6 now only 3<5 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.
[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 wrote:
> @dave: in your algorithm, I have a doubt in the second loop( for loop ).
> q=0 initially so the first q<<1 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 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
> > wrote:
> > > wat about shifting 'a' right by floar(log2(b)) and adding 1 to it..
>
> > > On Aug 18, 8:48 pm, aditya kumar 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 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
> > > > > 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.
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 q<<1 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 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
> wrote:
> > wat about shifting 'a' right by floar(log2(b)) and adding 1 to it..
> >
> > On Aug 18, 8:48 pm, aditya kumar 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 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
> > > > 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 ‘%’
@Dheeraj: What about it? It doesn't give the quotient. What is it
supposed to do?
Dave
On Aug 18, 11:06 am, DheerajSharma
wrote:
> wat about shifting 'a' right by floar(log2(b)) and adding 1 to it..
>
> On Aug 18, 8:48 pm, aditya kumar 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 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
> > > 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
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 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
> > 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 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 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
> > 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 ‘%’
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 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
> 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 ‘%’
@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
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 wrote: > exp(ln(a)-ln(b)) > > On Aug 18, 8:56 am, radha krishnan > 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 ‘%’
exp(ln(a)-ln(b)) On Aug 18, 8:56 am, radha krishnan 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.
