From: Didier Simoneau <didier.simoneau_at_tni-valiosys.com>
Date: Mon, 3 May 2004 16:23:41 +0200

The algorithme is the application of the Newton method to the equation:
    x^2 = V

If V is n digits long, sqrt(V) is approximatly n/2 digits long. So a good
initial guess can be obtained by stripping the last n/2 digits of V.

Didier
  Rockbox enthusiast

----- Original Message -----
From: <tinousus_at_yahoo.com>
To: "rockbox" <rockbox_at_cool.haxx.se>
Sent: Monday, May 03, 2004 12:06 PM
Subject: Re: math function for calculator


| Woo, really thanks. I use your algorithm and it works like a charm.
|
| Your algorithm is very efficient especially for my program.
| I am using scientific number format, the number needed to
| find root is always between 0 and 10. I take the midpoint of
| operand and 1 as the initial guess. Most of time, it takes less
| than 10 repeat. Average is about 5 times! Math is beautiful!
|
| Can you tell me the name of the algorithm?
|
| And do you know the algorithms for other functions like sin,cos,
| especially log?
|
| Isaac
|
| ------------------ Original Message ------------------
|
| >Try this:
| >
| >
| >V/G = N ... (G+N)/2 = G
| >repeat until G=N
| >
| >
| >V = Value (for which we are seeking the root)
| >G = most recent Guess
| >N = New guess
| >
| >
| >Example for root of V=12 with an arbitrary intial guess of 2
| >
| >
| >find _/12 ... guess 2.000
| >12/2.000 = 6.000 ... (2.000+6.000)/2 = 4.000
| >12/4.000 = 3.000 ... (4.000+3.000)/2 = 3.500
| >12/3.500 = 3.429 ... (3.500+3.429)/2 = 3.465
| >12/3.465 = 3.463 ... (3.465+3.463)/2 = 3.464
| >12/3.464 = 3.464
| >
| >
| >3.464^2 = 11.999
| >
| >
| >_/12 is irrational, so to get 12 back out of the other end you will need
an
| >infinite number of digits after the decimal place, hence the result above
| >being 11.999, that is because I decided to offer a result to only 3
decimal
| >places.
| >
| >
| >Obviously faster methods can be found, but generally you will need to
rely
| >on the existence of other mathematical functions (such as log-n) or big
| >memory-hungry lookup tables - Although for this application where our app
| >is 32K end-of-story, a lookup table of 1..2K would not be harmful.
| >
| >
| >One use of a lookup table might be to get a good initial guess...
| >With a table of all known integer squares:
| >
| >
| >_/105 lies somewhere between _/100 (=10) and _/121 (=11)
| >121 - 100 = 21
| >21 / (105-100) = 4.200
| >(1) / 4.200 = .238
| >
| >
| >So an initial guess of 10.238 would be reasonable
| >The answer is actually 10.247
| >
| >
| >If you need clarification on any of that, please ask.
| >
| >
| >ChipBleu
|
| _______________________________________________
| http://cool.haxx.se/mailman/listinfo/rockbox

_______________________________________________
http://cool.haxx.se/mailman/listinfo/rockbox
Received on 2004-05-03