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...@googlegro
@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++
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...@g
@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;
>
> }
>
>
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.
@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.
@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 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 ar
@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 wit
@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);
>
//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
@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)
{
@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 instru
@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
@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
@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.c
@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.goog
@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 Vishwana
@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
>
@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
@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 mul
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 di
@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 increme
@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 co
@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 be
@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
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
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)
> {
>in
@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 )
@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 t
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,
31 matches
Mail list logo
