Square Root Recursive Problem

This is a discussion on Square Root Recursive Problem within the C Programming forums, part of the General Programming Boards category; I am trying to write a function to express this but I keep confusing myself. Maybe I am thinking about ...

  1. #1
    Registered User
    Join Date
    Jun 2010
    Posts
    36

    Square Root Recursive Problem

    I am trying to write a function to express this but I keep confusing myself. Maybe I am thinking about it too hard?

    4.5 is halfway between 1 and 8. 4.52 = 20.25, so the square root of 8 must be less than 4.5.
    2.75 is halfway between 1 and 4.5. 2.752 = 7.5625, so the square root of 8 must be greater than 2.75.
    3.625 is halfway between 2.75 and 4.5. 3.6252 = 13.140625, so the square root of 8 must be less than 3.625.
    (and so onů)
    Continuing this process long enough reveals that the square root of 8 is about 2.828.

    My code is messed up somewhere because I keep getting back the same number that I scanned in. This is what I have so far:

    Code:
    #include <stdio.h>
    #include <math.h>
    
    double recursive_square (double n);
    
    int main (void)
    {
        double num = 0;
        double result = 0;
        
        
        printf("Enter a number to compute the square root of:\n");
        scanf("%lf", &num);
        
        result = recursive_square(num);
        
        printf("The square root of %lf is about %.3lf \n", num, result);
        
        system ("PAUSE");
        return 0;   
    }
    
    double recursive_square (double n)
    {
        double tempval = n/2;
        
        do
        {
            // If x2 is bigger than n, then we know that the square 
            //root of n must be between 1 and x,
            if ((tempval*tempval) > n)
            {
                tempval /= 2;
            }
            //otherwise it's between x and n
            if (tempval * tempval < n)
            {
                tempval += (n - tempval);
            }
        } while (((n - tempval) >= .001) || ((tempval - n) >= .001));
        
        return tempval;
    }
    Last edited by lostandconfused; 06-16-2010 at 09:18 PM.

  2. #2
    Registered User
    Join Date
    Jun 2010
    Posts
    45
    my gut feeling is that you need 3 pieces of information. the number you want to square root, a lower bound and an upper bound. so for example

    1^2 < 8 < 8^2

    so you could pass these into a recursive function eg

    Code:
    recursiveFunction(8, 1, 8)
    that function could then perform this logic

    Code:
    4.5 is halfway between 1 and 8. 4.52 = 20.25, so the square root of 8 must be less than 4.5.
    and then it could perform this call

    Code:
    recursiveFunction(8, 1, 4.5)
    so now the upper bound has been reduced

    right now your using a loop which works fine but so its not quite recursive since you dont call the same function from within itself.

  3. #3
    Registered User
    Join Date
    Jun 2009
    Posts
    457
    You need a base case, to return when you decide your apprimation is good enough. In this case, you return that approximation and you are done. Then you need two branches - if the approximation is too low, return the function called with the upper half of your interval. If the approximation is too high, return the function called with the lower half of your interval.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    A better way to revise your estimate is to use the value half way between tempval and n/tempval
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with recursive function
    By Posto2012 in forum C Programming
    Replies: 5
    Last Post: 12-05-2009, 03:32 AM
  2. Problem in accessing root home folder....
    By Bargi in forum Linux Programming
    Replies: 1
    Last Post: 02-13-2008, 05:50 AM
  3. Forced moves trouble!!
    By Zishaan in forum Game Programming
    Replies: 0
    Last Post: 03-27-2007, 07:57 PM
  4. Really basic string operation
    By bobthebullet990 in forum C Programming
    Replies: 6
    Last Post: 11-28-2005, 05:18 PM
  5. Square Root
    By Kyoto Oshiro in forum C++ Programming
    Replies: 5
    Last Post: 09-05-2002, 02:22 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21