6
\$\begingroup\$

I was originally going to write this intro as just being the bare-bones "here's my problem, here are some ideas, what do you recommend" format (which I am still going to follow, mind you), but I've decided to also add some backstory to it.

In high school I would write inefficient programs that generated mathematically significant results, at least to me, and then have hours of fun optimizing and revising the code until it was as clean and fast as I could make it. While I was writing this sieve, I was exploring the generation of primes.


Currently, the code will generate a range of natural numbers from \$1\$ to \$N\$ and store it in a list. Then the program will iterate through that list, marking each multiple of a prime as \$0\$ and storing each prime in a secondary list.

While this solution works just fine, one of the optimizations that I could never wrap my head around writing the code for was removing the multiples of primes instead of simply marking them as \$0\$.

The benefits of doing this are as follows:

  • Faster execution
  • Less memory usage
  • No need for cleanup
  • No if statements required

The problem is that I'm having a hard time wrapping my head around how I could perform this optimization and still remove multiples of each prime efficiently. If anyone has any ideas on how to do this in TI-Basic, please mention it.

What other optimizations could I make to the code as it is now?

Note: I do use an indentation system here because I loved the readability that indentation provides to languages like Python. Could this have any noticeable impact on the performance of the program?

:ClrList L2
:Input "END: ",E
:E->dim(L1:Fill(1,L1:cumSum(L1->L1
:For(A,2,E)
::If L1(A:Then
:::L1(A->L2(dim(L2)+1
:::For(B,2A,E,A
::::0->L1(B
:::End
::End
:End
:L2

Clarification:

E->dim(L1:Fill(1,L1:cumSum(L1->L1 generates the range from \$1\$ to \$N\$.

\$\endgroup\$
3
\$\begingroup\$

Removing a single number from a TI-BASIC list takes O(N) time where N is the size of the list. It's simply not practical. Here is the fastest idiom for removing the Xth element:

seq(L₁(A+(A≥X)),A,1,dim(L₁)-1→L₁

As for the indentation, the TI-BASIC interpreter needs to step through one colon at a time, which is relatively fast but not instantaneous. I expect each extra colon to take a TI-84 series calc about 0.1 ms each time through. If you want to maximize speed, get rid of the indentation.

As for other optimizations:

Rather than using E->dim(L1:Fill(1,L1:cumSum(L1->L1 to generate the list, use

cumSum(binomcdf(E-1,0→L₁

which has the same effect.

You can prescan for numbers not divisible by 2, etc; try this:

augment({2},1+2cumSum(binomcdf(int(.5E),0

to generate only the odd numbers.

As a different approach, you can generate prime numbers by adding to, not removing from, a list:

{2
For(𝑛,3,E,2)       ;close parenthesis to fix parser bug; step by 2 to catch odd numbers
If min(fPart(𝑛/L₁
n→L₁(1+dim(L₁
End
L₁

It should be of comparable speed or faster.

As a small tip, use the sequence variable n instead of a loop index. It takes as much as 0.5 milliseconds less to access (depending on how many other variables are in your VAT).

\$\endgroup\$
  • \$\begingroup\$ The odd number generator you provided raises a DATA TYPE error. The calculator I use has an older OS, so I am unsure about any syntactic differences between the languages of your calculator and mine that would be causing problems. I am aware of the O(N) problem and cumSum(binomcdf(. Thanks for the suggestions, I'll use what I can and learn from it. \$\endgroup\$ – Zenohm Sep 13 '15 at 23:56
  • \$\begingroup\$ I forgot a bracket there; try it now. My calculator is an 84+ with OS 2.55; almost everything is compatible except randIntNoRep( and remainder(. \$\endgroup\$ – lirtosiast Sep 14 '15 at 0:02
  • \$\begingroup\$ Alright, everything works perfectly now, thanks. \$\endgroup\$ – Zenohm Sep 14 '15 at 0:12
  • \$\begingroup\$ I usually use seq(X, X, 1, N), but it might be slower. \$\endgroup\$ – Solomon Ucko Mar 16 '18 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.