This is an archived, read-only copy of the United-TI subforum , including posts and topic from May 2003 to April 2012. If you would like to discuss any of the topics in this forum, you can visit Cemetech's
Technology & Calculator Open Topic subforum. Some of these topics may also be directly-linked to active Cemetech topics. If you are a Cemetech member with a linked United-TI account, you can link United-TI topics here with your current Cemetech topics.
Math and Science =>
Technology & Calculator Open Topic
| Author |
Message |
|
Weregoose
Authentic INTJ
Super Elite (Last Title)
Joined: 25 Nov 2004
Posts: 3976
|
 Posted: 19 Jan 2008 12:50:07 pm Post subject: |
|
|
I thought this would be fun to share.
Looking through some of my old IRC logs, I happened upon a complaint regarding logarithms and exponents being difficult to carry out in ASM. I immediately decided to work out an approximation for the logarithm, just for the heck of it.
That turned out to be: log10(x) ≈ 14231(x1/32768-1)
In other words, take the square root 15 times, subtract one, and multiply by 14231.
The accuracy starts to drop below 99% at around 6.7446×1016.
But, how do we go about quickly computing all those square roots in binary?
I found Wolfram's Iteration, and then wrote code for it here:
[indent]DelVar BAns→A
For(C,2,31
4A→A
2B→B
A-2Ans-4
If Ans≥0
Then
Ans→A
B+4→B
End
End
int(2fPart(B.5^seq(A,A,C,1,-1→A[/indent]
A different approach:
[indent]Ans→u(nMin)
0→v(nMin)
0→nMin
"4(u(n-1)-1≥v(n-1→Str1
"4u(n-1)-(v(n-1)+1)"+Ans→u
"2v(n-1)+"+Str1→v
int(2fPart(v(30).5^seq(A,A,32,1,-1→A[/indent]
Both take Ans as their inputs and return 32 binary digits of √(Ans), but both work only so long as 1≤Ans<4 – plus, when there are more than a small number of digits in the fractional part, the result can become flawed. Sorry, no generating 100 digits of [font="times new roman"]π out of this.
Lastly, to display the result as a string, add in the following:
[indent]"?
For(A,1,32
Ans+sub("01",1+LA(A),1
If A=1
Ans+".
End
Ans[/indent]
Last edited by Guest on 30 Aug 2010 08:30:12 pm; edited 1 time in total |
|
| Back to top |
|
|
elfprince13
Retired
Super Elite (Last Title)
Joined: 11 Apr 2005
Posts: 3500
|
| Posted: 22 Jan 2008 12:06:05 am Post subject: |
|
|
I wrote a program in Java a long time ago to calculate square roots that could be translated into asm assuming you already have somewhat functioning floating point math. there are probably faster algorithms, but it ran comparably fast to java's native Math.sqrt() function.
code went something like this:
Code:
public static double findSqrt(double value){
double cur = value;
double toOp = cur;
if(value < 0) return Double.NaN;
for(int i = 0; i < 128; i++){
toOp /= 2;
if(cur*cur < value) cur += toOp;
if(cur*cur > value) cur -= toOp;
if(cur*cur == value){return cur;}
}
return cur;
}
not as nifty as goose's, but it strikes me as a little more flexible than only finding squareroots 1<=r<4
I also remember seeing Basic code for Heron's method on Cemetech a couple years ago.
[quote name='"Chipmaster"']You probably used guess and check then. Heron's method is a much more intelligent, accurate, and quick way of obtaining it. The theory is as follows:
1. You take a random guess of the square root of a number and store that to A
2. (A + N/A)/2 will be closer and thus store this to A
3. Repeat this for a certain amount of iterations (you don't need many as it converges fast)
4. A becomes the square root of N
Here's how I make square roots (without using the square root key or similar cheats)
Code:
:Prompt N
:Rand->A
:While .00000001<abs(A-B ;I think that is enough accuracy
:A->B
:.5(A+N/A->A
:End
:A
Wow, its almost as fast as the OS and incredibly accurate. Come on, that's pretty 1337 :D
Another interesting point about Heron's formula is you can easily prove it. Let's say X is our square root.
(Sqr(X)+X/Sqr(X))/2 = Sqr(X) ;original
(X/Sqr(X) + X/Sqr(X))/2 = Sqr(X);lcm
(2X/Sqr(X))/2 = Sqr(X) ;combine like terms
2X/(2Sqr(X)) = Sqr(X) ;dividing is the same thing as multiply by the inverse
X/Sqr(X) = Sqr(X) ;Cancel the two's
XSqr(X)/X = Sqr(X) ;Rationalize that denominator
Sqr(X) = Sqr(X) ;Cancel the X's
0 = 0 ;Heh, I just like to do this to show that two formulas that equal each other always break down to this
Woot  [/quote] |
|
| Back to top |
|
|
simonzack
Advanced Newbie
Joined: 25 Dec 2007
Posts: 71
|
| Posted: 22 Jan 2008 01:09:36 am Post subject: |
|
|
There's one in the FAT raycasting engine that's nifty, uses some look-up tables, can go to unsigned long and gives a integer
No decimals  |
|
| Back to top |
|
|
thornahawk
μολών λαβέ
Active Member
Joined: 27 Mar 2005
Posts: 569
|
| Posted: 22 Jan 2008 02:34:41 am Post subject: |
|
|
@elfprince:
Heron's method, as you know, can also be thought of as applying Newton-Raphson to the equation x²−a==0 . It might interest you that using Halley's method, you can get a method with slightly faster convergence:
thornahawk |
|
| Back to top |
|
|
elfprince13
Retired
Super Elite (Last Title)
Joined: 11 Apr 2005
Posts: 3500
|
| Posted: 22 Jan 2008 08:31:10 am Post subject: |
|
|
simonzack wrote: There's one in the FAT raycasting engine that's nifty, uses some look-up tables, can go to unsigned long and gives a integer
No decimals
:P thats cheating
thornahawk wrote: @elfprince:
Heron's method, as you know, can also be thought of as applying Newton-Raphson to the equation x²−a==0 . It might interest you that using Halley's method, you can get a method with slightly faster convergence:
thornahawk
interesting I wonder how that would compare in terms of clock cycles on a calculator compared to Heron's Method since with Halley's Method there are obviously a few more operations taking place than with Heron.
a really good implementation would know the point at which the faster convergence made up for the increased number of operations to calculate each term and choose based on that  |
|
| Back to top |
|
|
CoBB
Active Member
Joined: 30 Jun 2003
Posts: 720
|
| Posted: 22 Jan 2008 09:54:44 am Post subject: |
|
|
elfprince13 wrote: a really good implementation would know the point at which the faster convergence made up for the increased number of operations to calculate each term and choose based on that
I’d say Heron is bound to be faster in every case, because it takes only about 1.5 times the iterations needed by Halley at the same precision, and its iterations are cheap enough to make up for that. |
|
| Back to top |
|
|
|
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.
»
Go to Registration page
