Author Topic: Algorithm Optimising  (Read 3775 times)

0 Members and 1 Guest are viewing this topic.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Algorithm Optimising
« 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:

Code: [Select]
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:
Code: [Select]
;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

Offline harold

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 226
  • Rating: +41/-3
    • View Profile
Re: Algorithm Optimising
« Reply #1 on: September 27, 2013, 09:22:53 am »
Ok, maybe I get it now, if it's roughly similar to this:
Code: [Select]
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 carry
Do that thing for some number of times that has to do with b.
Right?
Blog about bitmath: bitmath.blogspot.nl
Check the haroldbot thread for the supported commands and syntax.
You can use haroldbot from this website.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Algorithm Optimising
« Reply #2 on: September 27, 2013, 10:03:23 am »
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:
Code: [Select]
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:
Code: [Select]
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

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55943
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Algorithm Optimising
« Reply #3 on: October 09, 2013, 12:40:46 am »
Hmm shouldn't this go in the TI-BASIC sub-forum? ???

Offline Jim Bauwens

  • Lua! Nspire! Linux!
  • Editor
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1881
  • Rating: +206/-7
  • Linux!
    • View Profile
    • nothing...
Re: Algorithm Optimising
« Reply #4 on: October 09, 2013, 03:28:25 pm »
Considering it's about the algorithm itself and not the language, I'd say no.