Omnimaga
General Discussion => Other Discussions => Math and Science => Topic started by: Xeda112358 on September 27, 2013, 08:57:19 am
-
I once wrote an algorithm that I originally generated from a fractal. It was a lot easier for me to come up with the rules for the fractal and then use the image for the algorithm than it was to solve the algorithm problem directly. However, yesterday, after nt touching this problem in almost a year, it randomly popped into my head with a solution, so I have the algorithm below in TI-BASIC (since I had my calculator nearby, I tested it on that). What I am wondering is how to optimise it. I tried to generate it with a binary expansion because ultimately, that is what I will be using it with, but it got too messy without the fractal I was using as a crutch:
Input A
Input B
"A must be odd
While not(remainder(a,2
.5A→A
B-1→B
End
2A/2^B→A
"constraints on A and B will always cause this to be on [0,1)
B-2→B
".→Str1
While B
B-1→B
2A→A
int(A→R
A-Ans→A
If not(R
1-A→A
Str1+sub("01",R+1,1→Str1
End
Except for the first character, Str1 will be a sequence of 0s and 1s. Any ideas? It essentially maps an odd binary number to another binary number and the map is 1-1.
EDIT:
;given a,b such that a/2^(b+1) is on [0,1) and a is odd
a/2^(b+1)→a
b-2→b
""→string
While b>0
b-1→b
2*a→a
string & str(int(a))→string ;int(a) will either be 1 or 0, so append this to the string
if a<1
1-a→a
a-int(a)→a
-
Ok, maybe I get it now, if it's roughly similar to this:
shl a, 1 ; a is a 0.k fixpoint number (where k is "big enough")
rol string,1 ; doesn't affect carry because I say so
neg.c a ; negate if carryDo that thing for some number of times that has to do with b.
Right?
-
That looks right except I messed up the pseudocode, sorry. The only change should be to negate if the carry flag is reset.
That looks really nice o.o The exit condition can then be made to be when a=0, if a is initialised properly. With that, I want to show the true diabolical nature of this algorithm (mwahahaha?):
Python code:
from math import *
print """
================================================================
Exact Sine
of the form sin(x*pi/2^y)
For x not a natural number, this provides an estimate.
================================================================
"""
a=eval(raw_input("x="))
b=32+eval(raw_input("y="))
a=a*(2**32)
if a==int(a):
print "Exact"
else:
print "Estimate"
a=int(a)
while a%2 ==0:
a=a>>1
b=b-1
str1=".5*sqrt(2"
str2=")"*(b-1)
a=2.0*a/(2**b)
b=b-2
while b>0:
b=b-1
a=a*2
str1=str1+"-+"[int(a)]+"sqrt(2"
if a<1:
a=1-a
a=a-int(a)
str1=str1+str2
print str1
print eval(str1)
TI-BASIC:
ClrHome
Disp "sin(Aπ/2^B)
Prompt A,B
While not(remainder(A,2
.5A→A
B-1→B
End
".5√(2→Str1
2A/2^B→A
B-2→B
While B
B-1→B
Str1+sub("-+",int(2A)+1,1)+"√(2→Str1
2A
If Ans<1
1-Ans
fPart(Ans→A
End
-
Hmm shouldn't this go in the TI-BASIC sub-forum? ???
-
Considering it's about the algorithm itself and not the language, I'd say no.