How to delete single value in a list
Joskip (guest) 12 Jun 2013 18:20
It's for a sieve of erathosthenes-style program for calculating a row of very high primes very quickly.
How to delete single value in a list
Forum
» Programming & Design / TI-83/84 Programming
» How to delete single value in a list
Summary:
Is it possible on the TI-84 to remove a single value from a list, using a program?
Joskip (guest) 12 Jun 2013 18:20
An interesting way to create the sieve could be to use pixels on the graph screen. You have access to 63*95 pixels, so you can easily locate all of the primes in that range.
47%? Take a look and try to imagine how cool 100% will be. This has won zContest 2011 and made news on TICalc. This compromise between Assembly and BASIC parses like BASIC and is fast like assembly. Grammer 2
Could you elaborate on that? I can't think of a way to do it that way where you are still using the actual sieve of erathosthenes (I don't want to check per number).
The idea is to treat the grid of pixels as your number sieve. Start with the graph screen cleared and then an OFF pixel represents a prime number (excluding 0 and 1). Then your pixels are basically this (where 0 is the upper-left corner of the screen):
0 1 2 3 4 5 6 ... 93 94
95 96 97 98 99 100... .
190 .
285 .
.
.
.
Then just as you would with the regular sieve, start at 2 if the pixel is off (it should be!), then cross out every other pixel on the screen. Then move to the next pixel, if it is off, then turn every nth pixel ON to mark it as composite. You only need to check up to 73 since that is the largest prime less than or equal to sqrt(63*95).
Here is some code I came up with. When it is turning pixels ON, it converts a number to a coordinate using iPart(Ans/95) for the Y-coordinate, Ans-95iPart(Ans/95) (the remainder after dividing by 95) as the X-coordinate. If you are using an MP OS, you can just do remainder(Ans,95:
For(A,2,73
If not(pixelTest(0,A
Then
A
While Ans<5985
Ans+A
Pxl-On(iPart(Ans/95),Ans-95iPart(Ans/95
End
End
End
Then to test if a specific number is prime or composite, you can just perform a pixel-test:
Input "[2,5984]:",N
"PRIME
If pxl-Test(iPart(N/95),N-95iPart(N/95
"COMPOSITE
This would actually be a more memory efficient than using a list, too, since you could store whether each of the first 5985 positive integers are prime or composite in a 767 byte picture. A list cannot even be that large, and even if it could, it would be nearly 54000 bytes without any compression!
Anyways, I did just think of a method of using the Sieve of Eratosthenes on a list that might be useful. Say you have a list that is 200 elements containing the integers on [2,201]. Here is a quick way to do that:
1+cumSum(binomcdf(199,0→L1
Now use a For( loop and a similar procedure as with the pixels (without the need for converting a number to coordinates):
For(A,1,12 ;L1(12) = 13
If L1(A
Then
2A+1→B
While Ans≤200
0→L1(Ans
B+A+1→B
End
End
End
Now all of the composite numbers are turned into 0s, so use SortD( to put them at the end of the list:
SortD(L1
Now when you do L1≠0, all list elements that are not 0 result in "true" which is 1 and any that are 0 result in false (0). This means you should have a bunch of 1s in the beginning of the list and 0s at the end. If you find the sum of the 1s, you know how many non-zero elements there are and you can use this to resize your list:
sum(L1≠0→dim(L1
And now you have a list of prime numbers in descending order, less than 202. To make them ascending, just use SortA( :)
There are less memory-intensive ways of generating a list of prime numbers, too, and they can get decent speed.
47%? Take a look and try to imagine how cool 100% will be. This has won zContest 2011 and made news on TICalc. This compromise between Assembly and BASIC parses like BASIC and is fast like assembly. Grammer 2
Very interesting, I'll take this into consideration while making the program and be sure to post the results here (it might take a while as I'm in an my exam week).
Not to get off topic, but does anyone have prime searching program using the sieve of Atkin I can take a look at? I'm very interested in learning how such a program might work.
Since I was about to ask something else and refound is thread I decided to reply here after all this time, I hope that isn't a problem?
Anyway, I did later make my own prime listing program using Erathosthenes' sieve (for the primes in [1,2000] only at the moment):
For(A,1,199
0->L2(A
End
For(B,3,43,2
For(C,B^2/2-.5,999,B
1->L2(C
End
End
2->L1(1
3->L1(2
3->D
For(A,2,999
If 0=L2(A
Then
2A+1->L1(D
D+1->D
End
End
I did also follow your advice on using individual pixels (your code gives a dim error though, perhaps 95 was too wide?), which can store even more primes than you thought since we can omit all even numbers, even though that compromises the nice patterns you get when you include them. Thanks again for the great idea.
There was a topic for this exact problem quite a long time ago involving a disagreement between Weregoose and calcrypto. Unfortunately, I can't find it in the search, so I'll give you the best I've got until Weregoose comes along:
Where the location of the element of the list is in Ans, the list is L₁, Ans is not 1, and Ans<dim(L₁) (because you can remove the first and last elements with the ΔList() and cumsum() command chaining trick).
:augment(seq(L₁(A),A,1,A-1),seq(L₁(A),A,A+1,dim(L₁→L₁
I hope Weregoose finds this thread soon.
Wow, I hadn't expected it to be so much of a hassle, this kind of programming is still a little over my head.
Thanks for the quick replies though you guys.
Explanation:
You're putting together two lists with augment() - one will all elements before the number you want to remove, and another with all the elements after that number.
seq() simply just makes the lists.
It's rather inefficient, having an O(n) computational big O…
Quite a feature to forget to implement while designing a calculator. You can actually acess a list and delete single values easily, but implementing it in a program (which seems rather crucial to a lot of algorithms) takes a complicated and inefficient code…
Anyway, thanks a lot for your help.
The funny part is that TI included rom call that deletes a given number of elements from a list at a given location, and they never implemented it as a BASIC function. They also have a rom call for computing gamma of a number which is really useful in the sciences and engineering, but no built-in function was given for that.
47%? Take a look and try to imagine how cool 100% will be. This has won zContest 2011 and made news on TICalc. This compromise between Assembly and BASIC parses like BASIC and is fast like assembly. Grammer 2
seq(L1((X>N)+X-1),X,2,dim(L1→L1 deletes the Nth element.
Would you advise using that or just replacing all variables you want to delete with 0's, putting them at the end of the list and shorting the list to the position of its last value>0? Which would be faster?
That probably depends on how many numbers there are to delete in the list. If there were only one or two, Weregoose's way would be faster. If you have 10, and if the list itself is pretty large, Xeda's way will be significantly faster.
/forum/t-661155/how-to-delete-single-value-in-a-list#post-
