1. Computer problem? Tech Support Guy is completely free -- paid for by advertisers and donations. Click here to join today! If you're new to Tech Support Guy, we highly recommend that you visit our Guide for New Members.

Recursive Algorithm

Discussion in 'Software Development' started by zahrav, Feb 16, 2005.

Thread Status:
Not open for further replies.
Advertisement
  1. zahrav

    zahrav Thread Starter

    Joined:
    Dec 19, 2004
    Messages:
    55
    How would u go about writing a recursive algorithm to find the square root, without using */% in JAVA
     
  2. brendandonhu

    brendandonhu

    Joined:
    Jul 8, 2002
    Messages:
    14,681
    Homework?
     
  3. zahrav

    zahrav Thread Starter

    Joined:
    Dec 19, 2004
    Messages:
    55
    yup...but i dont get how u cant use any other operators.
    i know u need a base case and a recursive case in which the method would be called again
    so the structure would be like:
    if (...) //base case
    else ... //recursive case call the method in here
     
  4. Shadow2531

    Shadow2531

    Joined:
    Apr 30, 2001
    Messages:
    2,636
    Do you need to do something like in Task3 on this page, but with java instead?
     
  5. zahrav

    zahrav Thread Starter

    Joined:
    Dec 19, 2004
    Messages:
    55
    ya task 3 seems very similar...ne ideas how to go about it?
    public static int squareRoot (int value, int high, int low)
    .
    .
    .
    .
     
  6. Shadow2531

    Shadow2531

    Joined:
    Apr 30, 2001
    Messages:
    2,636
    In c++, without using */%, you could do it non-recursively like this.

    Code:
    #include <iostream>
    
    using namespace std;
    
    static unsigned sqrt(unsigned long val) {
        unsigned long temp, g=0, b = 0x8000, bshft = 15;
        do {
            if (val >= (temp = (((g<<1)+b)<<bshft--))) {
                g += b;
                val -= temp;
            }
        } while (b >>= 1);
        return g;
    }
    
    int main() {
        cout << sqrt(16) << endl;
    }
    
    If you can apply that method to java and then make it recursive, you might have it.
     
  7. zahrav

    zahrav Thread Starter

    Joined:
    Dec 19, 2004
    Messages:
    55
    ;) lol thanks a lot for ure help...but only if i understood C++ ;)

    i'll try to deduce some of it, and get some of the logic...possibly
     
  8. Shadow2531

    Shadow2531

    Joined:
    Apr 30, 2001
    Messages:
    2,636
    Yeh, I understand and I don't want to confuse the situation by throwing in the wrong language, but I don't think anything in the function is too far off from the way java does it, but I would focus more on the method than anything else.

    Now here's a c++ version that doesn't use */%, doesn't use any loops and uses recursion to get the square root. (looks a little sloppy since no loops were used.)

    Maybe someone can convert that to java and maybe even clean it up a little or a lot.

    Code:
    #include <iostream>
    
    using namespace std;
    
    void sqrt(unsigned long& g, unsigned long& b, unsigned long& bshft, unsigned long& val) {
        unsigned long temp;
        b >>= 1;
        if (val >= (temp = ( ( (g << 1 ) + b) << bshft-- ))     ) {
                g += b;
                val -= temp;
                
        } else {
            sqrt(g,b,bshft,val);
        }
    }
    
    unsigned long sqrt(const unsigned long& num) {
        unsigned long temp;
        unsigned long g = 0;
        unsigned long b = 32768;
        unsigned long bshft = 15;
        unsigned long val = num;
        if (val >= (temp = ( ( (g << 1 ) + b) << bshft-- )) ) {
            g += b;
            val -= temp;
        }
        sqrt(g,b,bshft,val);
        return g;
    }
    
    int main() {
        cout << sqrt(16) << endl;
    }
    
    I'll attempt to do that in java.
     
  9. Shadow2531

    Shadow2531

    Joined:
    Apr 30, 2001
    Messages:
    2,636
    O.K. I tried it in java and couldn't get it to work at first. Didn't know you couldn't pass by reference. I then created a class to do it.

    This is my first java program (besides hello world) so I'm not sure how evil the code is or if it's even proper.

    Also, I didn't use the the SUN sdk. I used MinGW's gcj compiler to create an executable from the java code, so I can't guarantee the following code will compile for you. At any rate it's something for you to go on.

    Code:
    public class Squareroot {  
        
        class GetSquareRoot {
            
            long temp, g, b, bshft, val;
            
            void sqrt() {
                b >>= 1;
                if (val >= (temp = ( ( (g << 1 ) + b) << bshft-- )) ) {
                    g += b;
                    val -= temp;
                        
                } else {
                    sqrt();
                }
            }  
            
            long sqrt(final long num) {
                g = 0;
                b = 32768;
                bshft = 15;
                val = num;
                if (val >= (temp = ( ( (g << 1 ) + b) << bshft-- )) ) {
                    g += b;
                    val -= temp;
                }
                sqrt();
                
                return g;
            }
        
        };
        
        public static void main(String args[]) {
            GetSquareRoot i = new GetSquareRoot();
            System.out.println( i.sqrt(16) );
        }
    }
    
     
  10. zahrav

    zahrav Thread Starter

    Joined:
    Dec 19, 2004
    Messages:
    55
    cool thanks for all ure help :)
     
  11. Shadow2531

    Shadow2531

    Joined:
    Apr 30, 2001
    Messages:
    2,636
    Just remember, you'll still have to disect it and explain how and why it works.
     
  12. Sponsor

As Seen On
As Seen On...

Welcome to Tech Support Guy!

Are you looking for the solution to your computer problem? Join our site today to ask your question. This site is completely free -- paid for by advertisers and donations.

If you're not already familiar with forums, watch our Welcome Guide to get started.

Join over 733,556 other people just like you!

Thread Status:
Not open for further replies.

Short URL to this thread: https://techguy.org/331395

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice