Most likely, you already have heard of the Koch curve or seen it. You basically replace the mid of each line with a triangle line. So I made a Ti Basic Version of it. Since Recursion is not possible in Basic, I programmed my own iterative solution. Basically its just saving all the lines as connection of two points and then it measures the length and angle of each line in the next iteration and inserts the new lines depending on the angle and the length as points. At the end, you can simply run a plot command to graphically show the fractal, since we already saved all the points, which I think is the fastest way to draw it in Ti Basic.
I already posted it on tibasicdev.wikidot.com, but noone could find a good optimization.
Maybe someone here can think of a better method in Ti Basic or optimize my code a bit. (Maybe it is faster using the Lindenmayer system?)
Since my algorithm slows down exponentially each iteration, because the number of points being stored equals 1+4^N at the Nth iteration, it becomes very slow after a few seconds, but the worst problem here is the max dim of a list (999), which limits it to 4 iterations. I would appreciate you commenting your opinion on that method or suggesting a better method. Here is the code btw:

Code:
```Program:Koch (515 Bytes) :Radian  :0→Xmin:0→Ymin:94→Xmax:62→Ymax:AxesOff  //friendly window settings :{0,31+1/3,47,62+2/3,94→L1 :{3,3,18+2/3,3,3→L2 :Plot1(xyLine,L1,L2,° //I used the thinest mark here :DispGraph :Repeat getKey :{0→L3:{3→L4 :For(I,2,1+int(.5dim(L1))) :L1(I)-L1(I-1 :If Ans:Then :tan-1((L2(I)-L2(I-1))/Ans→D //D = Angle of line relative to x axis :Else //prevents Zero Division if a line would go straight up or down :π/2(1-2(L2(I)<L2(I-1→D :End :√((L1(I)-L1(I-1))^2+(L2(I)-L2(I-1))^2→L //phythagorean theorem; use the shorter ^2 token (getkey ID=61) :√(2/36L^2→T //length of each of the two triangle lines; note, that only the L has to be squared, the 36 is already a 6 squared :L/3→P //length of each of the two outer lines :L1(I-1)+Pcos(D→L3(1+dim(L3 //now all line points are being calculated :L2(I-1)+Psin(D→L4(1+dim(L4 :L3(dim(L3))+Tcos(D+π/4→L3(1+dim(L3 :L4(dim(L4))+Tsin(D+π/4→L4(1+dim(L4 :L3(dim(L3))+Tcos(D-π/4→L3(1+dim(L3 :L4(dim(L4))+Tsin(D-π/4→L4(1+dim(L4 :L1(I→L3(1+dim(L3 :L2(I→L4(1+dim(L4 :End :augment(L3,seq(94-L3(dim(L3)-X),X,1,dim(L3)-1→L1 //seq creates the symmetry copy of the list :augment(L4,seq(L4(dim(L4)-X),X,1,dim(L4)-1→L2 :DispGraph :End :ZStandart //code after the end is optional, clears everything nice up :AxesOn :ClrAllLists :PlotsOff :ClrHome```

Edit: Oh, and of course I already optimized using the fact that the fractal is symmetrical, meaning you only have to calculate half of the points and then use a mirror algorithm to get the other points (maybe someone knows a better mirror algorithm, I use seq there)
MasterChief56 wrote:
Since Recursion is not possible in Basic, I programmed my own iterative solution.
Actually, recursion is quite doable in TI-BASIC using subprograms; check out Chapter 4: Control Structures in Programming the TI-83 Plus/TI-84 Plus if you want more details and a few examples, including a Fibonacci number program. Nevertheless, I'm sufficiently happy that you're familiar with the process of converting an iterative algorithm to a recursive algorithm and vice versa, and applied it correctly here.

I haven't looked at the Koch Snowflake algorithm in much detail before, but is it truly necessary to store the coordinates of the vertices for each iteration? Can those not be computed algorithmically?
Recursion is quite doable in TI-BASIC *without* subprograms, with only logarithmic overhead in the number of subroutines.
KermMartian wrote:
Actually, recursion is quite doable in TI-BASIC using subprograms; check out Chapter 4: Control Structures in Programming the TI-83 Plus/TI-84 Plus if you want more details and a few examples, including a Fibonacci number program.

Unfortunately, I do not own this book... Of course I know that you are able to create subprograms in Basic, however, local variables are crucial for recursion and since all variables in Basic are global there is no way to pass over a variable in a recursive call of a method.
KermMartian wrote:
I haven't looked at the Koch Snowflake algorithm in much detail before, but is it truly necessary to store the coordinates of the vertices for each iteration? Can those not be computed algorithmically?

Yeah, it would be possible, but again it would be slower mainly in terms of drawing since you cannot longer use the Plot#() command if you dont want to save the points. However, thank you for your feedback, I will definetely look into your suggestions. I think, the fractal would look nice if it draws slowly, but has a fast calculation time.

elfprince13 wrote:
Recursion is quite doable in TI-BASIC *without* subprograms, with only logarithmic overhead in the number of subroutines.

I dont really understand... How would recursion be possible without local variables AND without subprograms?
For basic patterns of recursion, local variables are syntactic sugar over use of a stack which can be pretty trivially implemented with lists. Then you just need a stack pointer to track your recursion depth. To implement calling you need some sort of jump table or subroutine table at the beginning of the program, which can be implemented fairly efficiently (logarithmic overhead) as a binary search, since TI-Basic, to my knowledge, offers no facility for indirected Gotos (which would give O(1) time).

At one point I planned on making a tutorial series out of this sort of thing, but never really got around to it.
elfprince13 wrote:
For basic patterns of recursion, local variables are syntactic sugar over use of a stack which can be pretty trivially implemented with lists. Then you just need a stack pointer to track your recursion depth. To implement calling you need some sort of jump table or subroutine table at the beginning of the program, which can be implemented fairly efficiently (logarithmic overhead) as a binary search, since TI-Basic, to my knowledge, offers no facility for indirected Gotos (which would give O(1) time).

At one point I planned on making a tutorial series out of this sort of thing, but never really got around to it.

Implementing a stack in Basic is indeed possible, but the only downside is how slow accessing it would be. If you get to recursion with 999 iterations, that is going to slow the program down by a ton. But it is definitely doable! And MasterChief, I give you two big thumbs up for figuring this one out! Basic was probably not the easiest language to figure this out in. looks pretty neat; I just tried it in SC.
MateoConLechuga wrote:
Implementing a stack in Basic is indeed possible, but the only downside is how slow accessing it would be. If you get to recursion with 999 iterations, that is going to slow the program down by a ton. But it is definitely doable!
Aha, you just reminded me about Doors CS's AnsStack feature. Merthsoft wanted it for recursion related purposes; it essentially provides 10 stacks for local variables of all kinds. Check out a short intro to the AnsStack.
KermMartian wrote:
MateoConLechuga wrote:
Implementing a stack in Basic is indeed possible, but the only downside is how slow accessing it would be. If you get to recursion with 999 iterations, that is going to slow the program down by a ton. But it is definitely doable!
Aha, you just reminded me about Doors CS's AnsStack feature. Merthsoft wanted it for recursion related purposes; it essentially provides 10 stacks for local variables of all kinds. Check out a short intro to the AnsStack.

Wow, that is pretty neat! I never even knew that existed! This might actually be very useful for some other ideas i've been bouncing around. EDIT: Funny, this is exactly how I feel:
KermMartian wrote:
... I think it's a powerful language feature, but unfortunately it hasn't gained that much exposure.
Really col, but I wish there was a more efficient way to do this! By the way, using an L-system after n iterations takes 7*4^n entries, so only a couple iterations are feasible :/ However, there is one trick I could think of for reducing memoy cost:

The starting state is F++F++F where F=move forward, +=rotate right 60 degrees, -=rotate left 60 degrees. The replacement is F-F++F-F.

On the very last iteration when you are drawing (from a string, probably) every time you come across an F, instead of moving forward, perform the whole F-F++F-F iteration. So if I read an "F", I would draw a line segment forward, then rotate left, draw a line segment forward, rotate right twice, draw a line segment forward, rotate left, draw a line segment forward. This basically reads each F as an extra iteration, without the cost of multiplying the string size by 4. For better effects, you can store several extra iterations this way!

As to the recursion bit, it is quite possible, you just have to think outside the box!

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.

»
» All times are UTC - 5 Hours

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum