Pithagore-fast computation

This is a discussion on Pithagore-fast computation within the C Programming forums, part of the General Programming Boards category; Dear all. I'm doing the computation rectangle's edge using Pithagore theory. All 3 rectangle's edge are integer. Is there any ...

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    18

    Pithagore-fast computation

    Dear all.
    I'm doing the computation rectangle's edge using Pithagore theory.
    All 3 rectangle's edge are integer.
    Is there any algorithm for fast computation that don't use sqrt() function?
    Thanks.

  2. #2
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    c is less than a+b but greater than max(a,b)
    you can use some search algorithm in this range with test condition c*c == a*a +b*b
    to find c
    not guaranteed to be faster, but it uses only integer math
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Post the function in your current code that uses it and we'll show you an optimised version.
    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"

  4. #4
    Registered User
    Join Date
    Jan 2008
    Posts
    18
    just now I use this function:
    c=(int) sqrt(a*a+b*b);

  5. #5
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    Quote Originally Posted by invinciblevn View Post
    just now I use this function:
    c=(int) sqrt(a*a+b*b);
    that can be 1 less than the actual value
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  6. #6
    Registered User
    Join Date
    Jan 2008
    Posts
    18
    Quote Originally Posted by vart View Post
    that can be 1 less than the actual value
    I'm doing compute distant in an image which use pixel as unit.
    sqrt() require a lot resource.
    Last edited by invinciblevn; 01-14-2008 at 03:16 AM.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    So don't calculate the sqrt, just use the c * c value - for all intents and purposes, it's the same thing, just bigger.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Pythagorean. Pythagoras invented it.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Quote Originally Posted by invinciblevn View Post
    just now I use this function:
    c=(int) sqrt(a*a+b*b);
    That's not what I meant. I meant, post the whole function that includes this line of code. Assuming of course that it isn't longer than a couple dozen lines...

    It's extremely difficult to optimise 1 line of code, but if we can see the lines of code around it then it becomes quite easy.
    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"

  10. #10
    Registered User
    Join Date
    Jan 2008
    Posts
    18
    Quote Originally Posted by iMalc View Post
    That's not what I meant. I meant, post the whole function that includes this line of code. Assuming of course that it isn't longer than a couple dozen lines...

    It's extremely difficult to optimise 1 line of code, but if we can see the lines of code around it then it becomes quite easy.
    Thank you very much, iMalc.
    I'm doing the image rotation. I use this for point distance computation.
    This computation is used many times in my program, so that is require a lot resource.
    I wonder whether there is any other way of point distant computation that does not use pythagore?
    That is my problem.
    Thanks.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Your problem must be a common one in gaming forums. (as opposed to general purpose programming forums like this). I'd check the gaming forum, and also game.dev for more detailed answers.

    You can find the hypotenuse of a triangle by using it's two sides and the angle between them, but I have no idea if that is any faster, at all. The game programmers will know what's quick.

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Adak View Post
    Your problem must be a common one in gaming forums. (as opposed to general purpose programming forums like this). I'd check the gaming forum, and also game.dev for more detailed answers.

    You can find the hypotenuse of a triangle by using it's two sides and the angle between them, but I have no idea if that is any faster, at all. The game programmers will know what's quick.
    Most games use the trick I explained, by not using sqrt unless absolutely necessary.

    For image rotation, you could use the trick of Bresenham's circle algorithm: http://www.ecse.rpi.edu/Homepages/wr...bresenham.html

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 02-27-2009, 03:43 PM
  2. Very fast blurring algorithm
    By cfrost in forum Tech Board
    Replies: 1
    Last Post: 09-30-2005, 12:59 AM
  3. Saving a part of screen into a file fast!
    By Zap in forum C++ Programming
    Replies: 4
    Last Post: 06-28-2003, 10:56 AM
  4. Super fast bilinear interpolation
    By VirtualAce in forum Game Programming
    Replies: 2
    Last Post: 06-18-2002, 09:35 PM
  5. moving a bitmap, fast and smooth
    By werdy666 in forum Game Programming
    Replies: 1
    Last Post: 05-31-2002, 06:49 PM

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