Compute a square root (with restrictions)

This is a discussion on Compute a square root (with restrictions) within the Contests Board forums, part of the Community Boards category; Originally Posted by Sang-drax brewbuck, you must be doing something wrong. 125 iterations for newton's method? If you implement it ...

  1. #31
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,263
    Quote Originally Posted by Sang-drax View Post
    brewbuck, you must be doing something wrong. 125 iterations for newton's method?
    If you implement it exactly as I did, and graph the number of iterations to achieve the accuracy I specified, that is what comes out. It is what it is.

  2. #32
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,263
    Quote Originally Posted by dwks View Post
    Code:
    index *= 0.5;
    I think that counts as a sneaky way to avoid using division . . .
    I disagree. What if it had read index *= 2? Is that a "sneaky way" to avoid dividing by 0.5? It's just a multiplication. The fact that the number is less than one doesn't really mean anything.

  3. #33
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Perhaps an even greater challenge is no division or multiplication operators

    But then I suppose you'd define some macros that multiply by addition... *sigh*

  4. #34
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    nah, if I couldnt use multiplication, Id use bit shifting
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  5. #35
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Quote Originally Posted by brewbuck View Post
    If you implement it exactly as I did, and graph the number of iterations to achieve the accuracy I specified, that is what comes out. It is what it is.
    Yeah, but a correctly implemented Newton's method should ceonverge much faster than that.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  6. #36
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    a solution that meets all the requirements of the rules, but perhaps not the spirit of the contest -

    Code:
    double sqrtfunc(double Input){
     
         __asm    FLD  Input
         __asm    FSQRT
         __asm    FSTP Input
     
         return Input;
         }
    hah, no division one iteration beat that
    Last edited by abachler; 06-07-2007 at 10:08 AM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  7. #37
    Massively Single Player AverageSoftware's Avatar
    Join Date
    May 2007
    Location
    Buffalo, NY
    Posts
    141
    Quote Originally Posted by abachler View Post
    hah, no division one iteration beat that
    Alas, since templates can't take doubles, I can't quite beat that, but...

    Code:
    template <int r, int x>
    struct SqRootCalc
    {
        const static int value = x * x == r ? x : SqRootCalc<r, x - 1>::value;
    };
    
    template <int r>
    struct SqRootCalc<r, 1>
    {
        const static int value = -1;
    };
    
    template <int r>
    struct SqRoot
    {
        const static int value = SqRootCalc<r, r / 2>::value;
    };
    
    template <>
    struct SqRoot<1>
    {
        const static int value = 1;
    };
    
    template <>
    struct SqRoot<0>
    {
        const static int value = 0;
    };
    This will find integer square roots at compile time, so I don't even need instructions.

    Usage:
    Code:
    cout << SqRoot<9>::value << endl;
    If you pick an integer that doesn't have an integer square root (5 for example) you'll get -1.
    There is no greater sign that a computing technology is worthless than the association of the word "solution" with it.

  8. #38
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Quote Originally Posted by AverageSoftware View Post
    This will find integer square roots at compile time, so I don't even need instructions.
    Wow, amazing, except that you are using division.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  9. #39
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    >> Wow, amazing, except that you are using division.

    But there are no calls to the division operator at runtime, so its close.

  10. #40
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    >> Wow, amazing, except that you are using division.

    But there are no calls to the division operator at runtime, so its close.
    Besides, you can just change it to *0.5 and you'll be just fine.

    That code's pretty amazing, though. I would never have thought of it.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  11. #41
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    >> Besides, you can just change it to *0.5 and you'll be just fine.
    Except that you can't unfortunately. I believe everything must be integral.

  12. #42
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    This doesn't work?
    Code:
    static_cast<int>(r * .5)
    I'm just guessing, I don't know much about that sort of thing.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  13. #43
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    It does, but that's different than AverageSoftware's template metaprogramming based solution. Yours is a run-time operation, but the templated stuff is compile time, which I believe must be integral (which is also why double can't be used instead of int).

  14. #44
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,048
    Oh, I see. Well, the r/2 could be just r or r-1; it would just be less efficient and involve more "recursion".
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  15. #45
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    True. And now that I look closer I see that it only does one division anyway, which is allowed in the rules.

Page 3 of 4 FirstFirst 1234 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. program to calculate the square root
    By saszew in forum C Programming
    Replies: 7
    Last Post: 10-28-2008, 01:53 PM
  2. Forced moves trouble!!
    By Zishaan in forum Game Programming
    Replies: 0
    Last Post: 03-27-2007, 07:57 PM
  3. Bisection Method function value at root incorrect
    By mr_glass in forum C Programming
    Replies: 3
    Last Post: 11-10-2005, 09:10 AM
  4. Square Root ?!?
    By Tm687 in forum C++ Programming
    Replies: 1
    Last Post: 02-29-2004, 04:38 PM
  5. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 02:24 AM

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